| 니앙팽이 - 컴퓨터 구조 | 캐시 Cache

Cache

주소가 키로 주어졌을 때 그 공간에 즉시 접근할 수 있다는 것은
캐시가 하드웨어로 구현한 해시 테이블(Hash table)과 같다는 의미다.

📄 1. 캐시가 생긴 이유.

1). 캐시 생성의 배경

프로세서(CPU)는 날마다 빨라지는데.. 메모리(DRAM)의 속도는 너무 더디다.

CPU와 Memory간 Read/Write에 생기는 병목이 Memory Wall 이라고 한다.

따라서, CPU내부에 L1, L2캐시를 두고 Memory에는 L3 캐시를 두어 속도를 개선하여
빠른 데이터 접근이 가능하다.

만약 어디있는지 모른다면 O(N)만큼 걸릴것이다.
하지만, 어디있는지 알기만 하면, 예측할 수 있다면 시간은 적게 걸릴것 이다.
또한 알고 있다 하더라도, 페이지라는 단위로 관리되어 
(SSD -> RAM)으로 적재할때 스왑-인 과정또한 시간이 걸리는 일이다.

하지만 캐시는 메모리보다 용량이 작고, 모든 내용을 저장할 수 없다.
따라서 참조 지역성 (Locality of Reference) 원리를 따라서
CPU가 자주 사용할 법한 내용을 예측하여 캐시에 저장해야 한다.
CPU

32/64 Bit 아키텍쳐를 가지고 있다.
메모리에서 데이터를 Word단위로 읽고
메모리에 Word단위로 데이터를 쓴다.
실제로는 데이터 버스 폭이나 내부 레지스터의 크기에 따라 달라질 수 있다는 점
Word

CPU 아키텍쳐에 대응되는 데이터 단위
32bit(4byte), 64bit(8byte)
Cache

CPU와 메인 메모리 사이의 고속 임시 저장소 전체 캐시 메모리 공간를 말한다.
데이터 접근의 지역성(Locality)을 이용해서 관리되는 모든 기억장치를 부른다.
복수의 Cache Block(또는 Cache Line)으로 이뤄져 있다.
Cache Block(또는 Cache Line)
Cache를 구성하는 기본 단위
데이터는 캐시에 저장될 때 캐시 블록을 단위로 저장한다.
1. 메모리에서 전송되는 고정적인 데이터 최소 단위(보통 32Byte, 64Byte)를 가진다.
2. 캐시 블럭의 내용물들은 연속된 데이터로 구성되어 있다.
3. 데이터가 캐시 내에 있는지, 데이터를 검색하기 위해 블럭 내부의 정보를 좀더 쪼개서
  캐시 블록은 데이터 외에도 태그, 유효 비트, (쓰기 정책에 따라) 더티 비트 등의 메타데이터를 포함한다.

2). Struct, Class Padding

구조체나 클래스의 크기 계산하기

그 내부를 이루는 멤버들의 타입 크기를 모두 합한것이라 생각하면 된다.
하지만 빌드시 실제 크기는 CPU 캐시 블럭의 크기에 따라 더 커질 수 있다.
바로 컴파일러가 판단해서 바이트 패딩를 채워준다고 하더라..
Byte Padding
CPU 아키텍쳐에 따라 Word 사이즈가 달라짐을 알 것이다.
고정적인 데이터 최소 단위(보통 32Byte, 64Byte) 에 맞춰주도록 한다.
Cache Read, Write 과정의 비효율을 없에 주는 최적화 기법이기도 하다.
1. 서로 다른 컴퓨터 시스템에서 엔디안(Big or Little) 차이때문에
  메모리 패딩이 다르게 적용되는 문제가 생길 수 있다.
2. 심지어 TCP/IP 모델에서 패킷은 Big 엔디안을 사용하고
  Intel Processor는 Little 엔디안을 사용한다고 하니..
  이걸 처리하는데 있어서 물론 $O(N/2)$ 어쨌든 비용이 약간이라도 드는 요소다.

왜 바이트 패딩을 사용하지 않으면 느린 것 일까?

CPU 프로세서는 오직 1개의 Word 단위만 읽는다고 했지?
그 단위는 CPU 아키텍쳐에 따라 다르지만, 32bit(4byte), 64bit(8byte) 단위로 읽는다. at a time!
그런데.. 만약 struct을 이루는 서로다른 타입을이 byte offset을 어긋나게 저장한다면? 이때 비효율이 생긴다.

바이트 패딩을 사용하지 않을때 : int c을 읽으려면 word를 두번 읽어야 한다.

struct abc {
    char a; // 1byte
    char b; // 1byte
    int  c;  // 4byte
} var
                    ✅               ✅
|   a   |   b   |   c   |   c   ||   c   |   c   |   -   |   -   |
|          WORD(4byte)          ||         WORD(4byte)           |

정렬만 잘 한다면 : int c을 읽때 한번만 읽어도 충분하게 만들 수 있다.
하지만 정렬을 최악으로 한다면 사이즈가 더 커질 수 있다.

struct abc {
    int  c;  // 4byte
    char a; // 1byte
    char b; // 1byte
} var
    ✅
|   c   |   c   |   c   |   c   ||   a   |   b   |   -   |   -   |
|          WORD(4byte)          ||         WORD(4byte)           |

바이트 패딩을 해준다면 : int c을 읽때 한번만 읽어도 충분하게 만들 수 있다.

struct abc {
    char a; // 1byte
    char b; // 1byte
    char garbege[2]; // 2byte
    int  c;  // 4byte
} var
                                     ✅
|   a   |   b   |garbege|garbege||   c   |   c   |   c   |   c   |
|          WORD(4byte)          ||         WORD(4byte)           |

📄 2. Cache Coherence, CPU Caching Policy

일명 캐시에 데이터를 덮어 씌울때, 기존에 저장한 데이터가 휘발되서 소멸하면 안되겠지?

그런 이유로 특정 캐시에 값을 덮어 씌울때, 기존 값을 저장해야 한다, 바로 한단계 낮은 속도의 캐시로
Write Cache1 to Cache2 when Cache1 is Replaced By another

1). 캐시 일관성 (Cache Coherence)

CPU 프로세서가 가진 캐시의 데이터와, RAM 메모리의 데이터간의 일관성을 유지해야한다.

쓰기의 경우에도 데이터를 데이터 캐시에만 쓰고, 메인 메모리에 쓰지 않는다면 메인 메모리는 캐시와 다른 값을 갖게 되는데.
이 경우에 캐시와 메모리가 불일치(inconsistent)하게 되고 메인 메모리와 캐시를 일치 시키는 방법이 필요하다.
멀티 스레딩 프로그래밍에서 주의해야 하는 요소다.

2). CPU Caching Policy

CPU가 Word 단위로 메모리에 데이터를 쓰는 방법이 여러가지가 있대~

① Write-Through

Write-Through : CPU Cahce (L1, L2)에 어떤 값을 쓰기를 할때, 연달아 Main Memory에도 값을 쓴다.
만약 Main Memory 입장에서 L3캐시에 있는 내용을 Main Memory에 복사하고(Write)하고 싶다.
MainMemory가 L3내용을 썼고, L3도 L2내용을 쓰고... 끝까지 내려가
이렇게 되는 것이 한 순간에 일어나면 방식을 사용한 것이다.
정확하지만 속도가 느리다.

② Write-Back (Lazy Write)

Write-Back : CPU Cahce (L1, L2)에 어떤 값을 쓰기를 할때,
Cache Line에 있는 Dirty Bit를 체크하고 Prev CPU Cahce Data만 Main Memory에 쓰고,
막상 현재 CPU Cahce에 들어간 값은 다음에 값을 또 쓸때 그제서야 Main Mermory에 쓰도록 지연된다.
속도가 매우 빠르다.

중요한 점은 반드시

쓰기 정책이 Wirte-Through이면 캐시 미스에 대한 반응은 No-Allocation방식이고,
쓰기 정책이 Write-Back이면 캐시 미스에 대한 반응은 Allocation이다.
Wirte-Through & Allocation일 수는 없고, 또한 반대로 Wirte-Back & No-Allocation일 수는 없다!

📄 3. Read/Write Cache Hit/Miss?

도데체 쓰기 캐시 미스가 뭐지? What is a cache write miss?

Read / Write 의 차이

Cache Hit & Miss

1). Read Hit/Miss : CPU가 한 Word단위의 데이터를 읽으려고 할 때.

Cache Read Hit
- Read할 Word가 이미 포함된 "Cache Block"이 있을때, 바로 데이터를 읽는다
Cache Read Miss
- Read할 Word가 이미 포함된 "Cache Block"에 없으면?
  순차적으로 캐시메모리(L1 -> L2 -> L3 -> RAM) 순으로 읽는 시도를한다.

캐시 히트의 확률이 곧 성능이라고 할 수 있다.

2). Write Hit/Miss : CPU가 한 Word 단위로 메모리에 데이터를 쓰려고 할때

Cache Write Hit
- Write 할 Word가 이미 포함된 "Cache Block"이 있을때,
Cache Write Miss
1. Write 할 Word가 이미 포함된 "Cache Block"이 없을때,
  그리고 Cache를 이루는 아무 "Cache Block"에도 Word요소로 구성되어 있지 않을때,
2. 혹은 "Cahce Block"이 있는데도 "배타적 상태"같은 쓰기 불가능한 상태일 때,
- 이때 Write하다 실패(Miss) 되었다는 것이다.

📄 4. Write Miss가 되었으면 실행되는 동작은?

쓰기 미스를 처리하는 두가지 방법

반드시 쓰기 정책이 Wirte-Through이면 캐시 미스에 대한 반응은 No-Allocation 방식이고,
반드시 쓰기 정책이 Write-Back이면 캐시 미스에 대한 반응은 Allocation 방식 이다.

1). No-Write Allocate

Wirte-Through 정책으로 Write 하는데, Cache Miss가 발생했을때.
그냥 바로 Main Memory에 값을 쓴다.

2). Write Allocate

Wirte-Back 정책으로 Write 하는데, Cache Miss가 발생했을때.
메인메모리에서 Cache로 Word 데이터를 가져온 뒤 Cache에 씀 쓰여진 Cache의 데이타는
Cache Buffer(이것도 Main Mamory에 위치)가 메모리에 씀
그래서 Current Word Data와 Previous Word Data가 버퍼에 공존할 수 있음.

📄 5. Locality of Reference

CPU가 메모리에 접근하는 경향은 다음과 같고, 이런점을 고려하고 캐시히트를 높일 수 있다.
1. 시간 지역성
  최근에 참조된 명령어나 데이터가 가까운 미래에 CPU에 의해 다시 참조되는 경향을 의미한다.
  시간 지역성은 효과적으로 활용하기 위해서 한번 참조된 데이터를 오래 저장하기 위해
  잘개 쪼개져도 상관 없으니 캐시 블록의 수가 많아야 한다.
  - Ex). Index in Loop
    for(int i = 0; i < 10; i++) {sum += arr[i] + weight;} 에서
    최근에 접근한 &i에 대한 데이터가 캐시에 남아있게 되어 성능을 향상시킴
    혹은 &weight 주소에 있는 데이터 또한 반복적으로 접근하게 되어 weight을 캐싱하여 캐시 히트를 높인다.
2. 공간 지역성
  최근에 참조된 명령어나 데이터의 "이웃"이 CPU에 의해 가까운 미래에 참조되는 경향을 의미한다.
  공간 지역성 효과적으로 활용하기 위해서 블록의 개수가 적어도 상관 없으니, 캐시 블록의 크기가 커야 한다.
  - Ex). Stack 메모리, Continues Structure( Array )'s Row-Major
    row-major한 접근의 예시로 arr[0][0]이 접근된다면,
    한번에 캐시에 로드되는 내용은 arr[0][1], arr[0][2], arr[0][3]이고
    행단위 연속된 메모리가 연속적으로 올라가서 루프를 돌리는 것은 캐시 히트율이 높아진다.
    만약 이중 포문의 행-열의 접근이 열접근이 된다면 arr[0][0] 다음 arr[1][0] 에 접근하려고 하니 캐시 미스율이 높아진다.
캐시 미스가 일어날 확률이 적으려면, 자주 사용되고 자주 접근할 데이터를 올리면 된다.

1. 데이터를 컴팩트(메모리상 인접하게) 올림으로
캐시쪽으로 저장되기 유리하고, 한번의 캐시 라인 로드로 여러 변수를 동시에 올리도록 할 수 있다.

2. 연속적인 데이터를 캐시에 올려 RowMajor한 루프를 돌릴때 공간 지역성을 유리하게 하자.

참조

저작자표시

'CS > OS' 카테고리의 다른 글

\| 니앙팽이 - 멀티스레딩 \| 7 \| Blocking I/O & NonBlocking I/O 그리고 Synchronous & Asynchronous (0)	2025.02.14
\| 니앙팽이 - 멀티스레딩 \| 6 \| 스레드 (0)	2025.01.18
\| 니앙팽이 - 멀티스레딩 \| 5 \| 성능 평가 척도 (0)	2025.01.18
\| 니앙팽이 - 멀티스레딩 \| 4 \| 프로세스 (0)	2025.01.18
\| 니앙팽이 - 멀티스레딩 \| 3 \| 프로그램을 처리하는 발전 흐름 (1)	2025.01.18

Cache

📄 1. 캐시가 생긴 이유.

1). 캐시 생성의 배경

프로세서(CPU)는 날마다 빨라지는데.. 메모리(DRAM)의 속도는 너무 더디다.

2). Struct, Class Padding

📄 2. Cache Coherence, CPU Caching Policy

일명 캐시에 데이터를 덮어 씌울때, 기존에 저장한 데이터가 휘발되서 소멸하면 안되겠지?

1). 캐시 일관성 (Cache Coherence)

CPU 프로세서가 가진 캐시의 데이터와, RAM 메모리의 데이터간의 일관성을 유지해야한다.

2). CPU Caching Policy

CPU가 Word 단위로 메모리에 데이터를 쓰는 방법이 여러가지가 있대~

① Write-Through

② Write-Back (Lazy Write)

중요한 점은 반드시

📄 3. Read/Write Cache Hit/Miss?

도데체 쓰기 캐시 미스가 뭐지? What is a cache write miss?

Read / Write 의 차이

Cache Hit & Miss

1). Read Hit/Miss : CPU가 한 Word단위의 데이터를 읽으려고 할 때.

2). Write Hit/Miss : CPU가 한 Word 단위로 메모리에 데이터를 쓰려고 할때

📄 4. Write Miss가 되었으면 실행되는 동작은?

쓰기 미스를 처리하는 두가지 방법

1). No-Write Allocate

2). Write Allocate

📄 5. Locality of Reference

캐시 미스가 일어날 확률이 적으려면, 자주 사용되고 자주 접근할 데이터를 올리면 된다.

참조

'CS > OS' 카테고리의 다른 글

티스토리툴바