캐시

캐시

캐시 메모리(cache memory)란, 속도가 빠른 장치와 느린 장치 사이에서 버퍼 역할을 하며 속도 차에 따른 병목 현상을 줄여, 컴퓨터 시스템의 성능을 향상시키기 위해 별도로 탑재된 일종의 범용 메모리를 말하는 것이다.

ex1) CPU 코어와 메모리 사이의 병목 현상 완화
ex2) 웹 브라우저 캐시 파일은, 하드디스크와 웹페이지 사이의 병목 현상을 완화

램보다 훨씬 빠르고 작고 매우 비싼 메모리이며, 레지스터와 함께 메모리 계층 구조의 전통적인 핵심 계층 중 하나이다.

참고) 메모리 계층 구조

CPU가 주기억장치에서 저장된 데이터를 읽어올 때, 자주 사용하는 데이터를 캐시 메모리에 저장한 뒤, 다음에 이용할 때 주기억장치가 아닌 캐시 메모리에서 먼저 가져오면서 처리 속도를 향상시킨다.

지역성의 원리

'자주 사용하는 데이터’에 관한 판단은 지역성의 원리를 따르며, 지역성 원리는 시간 지역성(Temporal locality)과 공간 지역성(Spatial locality)으로 구분해서 볼 수 있다.

1. 시간 지역성 : 최근 접근한 데이터에 다시 접근하는 경향
   ex) 루프에서 인덱스 역할을 하는 변수 i에는 짧은 시간안에 여러 번 접근이 이뤄진다.

   for (i = 0; i < 10; i += 1) {
   arr[i] = i;
   }

2. 공간 지역성 : 최근 접근한 데이터의 주변 공간에 다시 접근하는 경향
   ex) 위 루프의 경우 배열 arr의 각 요소를 참조하면서 가까운 메모리 공간에 연속적으로 접근하고 있다. 배열의 요소들이 메모리 공간에 연속적으로 할당되기 때문이다.

캐시에 데이터를 저장할 때는, 이러한 참조 지역성(공간)을 최대한 활용하기 위해 해당 데이터뿐만 아니라, 옆 주소의 데이터도 같이 가져와 미래에 쓰일 것을 대비한다.

프로세스 실행 중 접근한 데이터의 접근 시점과 메모리 주소를 표시한 아래 그림은 시간 지역성과 공간 지역성의 특성을 잘 보여준다.

한 프로세스 안에도 자주 사용하는 부분과 그렇지 않은 부분이 있기 때문에 운영체제는 프로세스를 페이지(Page)라는 단위로 나눠 관리하며, 위 그림은 페이지를 참조한 기록이다. 가로 축은 실행 시간이고, 세로 축은 메모리 주소다. 즉, 수평으로 이어진 참조 기록은 긴 시간에 걸쳐 같은 메모리 주소를 참조한 것이고, 수직으로 이어진 참조 기록은 같은 시간에 밀접한 메모리 주소들을 참조한 것이다. 페이지에 접근할 때도 지역성 원리가 적용된다는 것을 알 수 있다.

Caches

시스템에 장착된 캐시의 용량과 성능이 점점 증가하면서 캐시의 캐시로 사용되는 메모리가 추가되며 CPU 칩에는 여러 개의 캐시가 들어갔는데, 이것을 적용된 순서대로 L(Level) 1, L2, L3 ... 라고 호칭한다. L1에 가장 고성능이자 고가인 작은 용량의 집적회로가 사용되고, L1캐시에서 데이터를 퍼가기 위한 캐시로 사용하기 위해 그보다는 용량이 크지만 그 대신 약간 더 느린 저장공간이 추가되었으며, L2캐시에서 데이터를 퍼가기 위한 캐시로 이후 L3 캐시가 추가되었고... 하는 식이다.
각각의 캐시는 각자의 목적과 역할을 가지고 있다.

+-------------+------+------+     +---------------+     +--------+
|             |  I$  |      | <-- |               | <-- |        |
+  Processor  +------+  L2  |     |  Main Memory  |     |  Disk  |
|             |  D$  |      | --> |               | --> |        |
+-------------+------+------+     +---------------+     +--------+

• L1 Cache: CPU 내부에 존재. 프로세서와 가장 가까운 캐시. 속도를 위해 I$와 D$로 나뉜다.
  • Instruction Cache (I$): 프로그램을 수행하는 명령어(Instruction)인 TEXT 영역 데이터를 다루는 캐시.
  • Data Cache (D$): TEXT 영역을 제외한, 그 명령이 실행되는 데이터(Data)를 다루는 캐시.
• L2 Cache: CPU와 RAM 사이에 존재. 용량이 큰 캐시. 크기를 위해 L1 캐시처럼 나누지 않는다.
• L3 Cache: 보통 메인보드에 존재한다고 함. 멀티 코어 시스템에서 여러 코어가 공유하는 캐시.

L2 캐시 위에 있는 구역이 L1 캐시로 보이는데, 확실하지 않아서 따로 표시하지 않았다.

Cache Metrics

캐시의 성능을 측정할 때는 히트 레이턴시(Hit latency)와 미스 레이턴시(Miss latency)가 중요한 요인으로 꼽힌다.

• 캐시 히트(Hit) : CPU에서 요청한 데이터가 캐시에 존재하는 경우.
  • 히트 레이턴시 : 히트가 발생해 캐싱된 데이터를 가져올 때, 소요되는 시간을 의미한다.
• 캐시 미스(Miss) : 요청한 데이터가 캐시에 존재하지 않는 경우.
  • 미스 레이턴시 : 미스가 발생해 상위 캐시에서 데이터를 가져오거나(L1 캐시에 데이터가 없어서 L2 캐시에서 데이터를 찾는 경우) 메모리에서 데이터를 가져올 때, 소요되는 시간

캐시의 성능을 높이기 위해서는 캐시의 크기를 줄여 히트 레이턴시를 줄이거나, 캐시의 크기를 늘려 미스 비율을 줄이거나, 더 빠른 캐시를 이용하여 레이턴시를 줄이는 방법이 있다.

Cache Organization

캐시는 반응 속도가 빠른 SRAM(Static Random Access Memory)으로, 주소가 키(Key)로 주어지면 해당 공간에 즉시 접근할 수 있다.

주소가 키로 주어졌을 때 그 공간에 즉시 접근할 수 있다는 것은 캐시가 하드웨어로 구현한 해시 테이블(Hash table)과 같다는 의미다. 캐시가 빠른 이유는 자주 사용하는 데이터만을 담아두기 때문이기도 하지만, 해시 테이블의 시간 복잡도가 O(1) 정도로 빠르기 때문이기도 하다.

캐시는 블록(Block)으로 구성되어 있다. 각각의 블록은 데이터를 담고 있으며, 주소값을 키로써 접근할 수 있다. 블록의 개수(Blocks)와 블록의 크기(Block size)가 캐시의 크기를 결정한다.

Indexing

주소값 전체를 키로 사용하지는 않고, 그 일부만을 사용한다.

전체 주소에서 하위 5비트를 오프셋(Offset)으로 쓰고, 이후 10비트를 인덱스(Index)로 사용하여 블록에 접근했다.

그러나 이렇게만 하면 서로 다른 데이터의 인덱스가 중복될 위험이 너무 크다.

Tag Matching

인덱스의 충돌을 줄이기 위해 주소값의 일부를 태그(Tag)로 사용한다.

그리하여 캐시는 아래와 같은 요소들을 포함한 블록이 된다.

블록  : 데이터의 기본 단위인 워드의 집합

• 데이터 메모리 : 메모리의 데이터들이 저장된 블록으로 구성되어 있다.
• 태그 메모리 : 데이터 메모리의 블록을 탐색할 정보를 포함한다.
  태그 메모리의 엔트리는 데이터 메모리 블록과 쌍을 이루면서 태그, 유효 비트, 갱신 비트를 포함한다. 또한 CPU 주소와 태그를 비교하는 비교기를 가지고 있다.
• 태그(tag) : CPU가 요청한 데이터를 탐색하는데 사용할 주소의 일부. 캐시 블록 주소에서 인덱스로 사용되지 않는 부분이다.
• 유효 비트(valid bit) : 캐시 블록이 유효한 데이터인지 나타낸다.
• 갱신 비트(dirty bit) : 캐시로 블록을 가져온 후 CPU가 블록을 수정했는지 나타낸다.

CPU와 캐시의 데이터 전송 방식 요약

1. CPU가 캐시 메모리에 주소를 전송한다.
2. 태그 메모리에서 탐색한다.
   • 일치하는 태그를 발견한다면 Cache Hit, 데이터 메모리에서 블록을 추출한다.
   • 일치하는 태그를 발견하지 못한다면 Cache Miss, 주소를 메인 메모리로 전송하여 대응하는 블록을 캐시에 저장한다.
3. 데이터를 선택한 후 CPU가 요청한 데이터를 캐시가 전송한다.

CPU와 캐시의 데이터 전송 방식 원본

1. CPU가 캐시 메모리에 주소를 전송한다.
2. 태그 메모리에서 탐색한다.
   1) 먼저 인덱스(0010100101)에 대응하는 태그 배열(Tag array)의 필드에 접근한다.
   2) 이어서 해당 태그 필드의 유효 비트(Valid bit)를 확인한다.
   3) 유효 비트가 1이라면 태그 필드(00000000000011000)와 주소의 태그(00000000000011000)가 같은지 비교한다.
   4) 비교 결과(true, 1)를 유효 비트(1)와 AND 연산한다.
3. 선택된 데이터를 캐시가 CPU에게 전송한다.

유효 비트가 1이라는 것은 해당 블록에 올바른 값이 존재한다는 의미다. 태그 필드와 주소의 태그가 같고, 유효 비트도 1이므로 위 예시의 결과는 히트다. 히트가 발생하면 데이터 배열(Data array)에서 해당 인덱스의 데이터를 참조한다.

만약 유효 비트가 0이라면 블록에 값이 없거나 올바르지 않다는 뜻이므로 미스가 발생한다. 그러면 주소의 태그를 태그 필드에 작성하고, 데이터 필드에도 상위 캐시나 메모리에서 요청한 값을 가져와 작성한 뒤, 유효 비트를 1로 바꿔준다.

유효 비트가 1이라도 태그가 일치하지 않으면 미스가 발생한다. 이 경우 교체 정책(Replacement policy)에 따라 처리가 달라진다.

캐시 교체 알고리즘

• LRU(Least Recently Used) - 캐시 내에서 가장 오랫동안 사용되지 않은 블록을 교체한다.
• FIFO(First In First Out) - 캐시 내에서 가장 오랫동안 존재한 블록을 교체한다.
• LFU(Least Frequency Used) - 가장 적게 참조된 블록을 교체한다.
• RR(Round Robin) - 공평하게 돌아가면서 블록을 교체한다.
• Random - 무작위로 블록을 교체한다.

LRU(Least Recently Used) 대체적으로 사용된다.

LRU(Least Recently Used) 알고리즘

각 교체 정책에 따라 태그 배열의 필드를 주소의 태그로 바꾸고, 상위 캐시나 메모리에서 요청한 데이터를 가져와 데이터 필드의 값도 새 데이터로 바꿔준다. (실제로는 요청한 데이터뿐 아니라 그 주변 데이터까지 가져온다.) 기존 데이터는 상위 캐시로 밀려난다.

Associative Cache

서로 다른 두 주소가 같은 인덱스를 가지면 충돌이 발생하고, 교체 정책에 따라 블록을 교체한다. 하지만 충돌이 발생할 때마다 캐시 내용을 바꾸면 더 많은 미스가 발생하게 되고, 한 자리의 내용을 끝없이 바꾸는 핑퐁 문제(Ping-pong problem)가 일어날 수 있다.

이 문제는 태그 배열과 데이터 배열을 여러 개 만드는 식으로 개선할 수 있다. 즉, 인덱스가 가리키는 블록이 여러 개가 되는 것이다. 그리고 이러한 태그들의 묶음을 캐싱 라인이라고 한다. 인덱스가 가리키는 블록의 개수에 따라 캐싱 라인의 종류를 분류하면 아래와 같다:

• Direct mapped: 인덱스가 가리키는 공간이 하나인 경우.
  • DRAM의 여러개 주소가 캐시메모리의 한 주소에 대응되는 다대일(n:1)방식.
  • 처리가 빠르지만 충돌 발생이 잦다.
• Fully associative: 인덱스가 모든 공간을 가리키는 경우.
  • 충돌이 적지만 모든 블록을 탐색해야 해서 속도가 느리다.
• Set associative: 인덱스가 가리키는 공간이 두 개 이상인 경우.
  • n-way set associative 캐시라고 부른다.

n-way는 결국 set associative에서, 몇개의 라인을 1개의 셋으로 했느냐를 알려준다. 1-way set associative는 결국 direct mapped 캐시와 동일한 셈이다. 캐시의 라인 수와 way수가 같다면 fully associative가 된다.

direct mapped 캐시와 fully associative 캐시 모두 장단점이 극단적이기 때문에 보통은 set associative 캐시를 사용한다.

Set Associative Cache Organization

간단하게 2-way set associative 캐시의 동작을 살펴보자:

주소의 인덱스를 통해 블록에 접근하는 것은 지금까지 본 direct mapped 캐시와 동일하다. 다만 2개의 웨이(Way)가 있기 때문에 데이터가 캐싱되어 있는지 확인하려면 하나의 블록만이 아닌 2개의 블록을 모두 확인해야 한다. 마지막으로 두 웨이의 결과를 OR 연산하면 최종 결과를 낼 수 있다. 모든 웨이에서 미스가 발생하면 교체 정책에 따라 2개의 블록 중 한 곳에 데이터를 작성한다.

direct mapped 캐시와 비교해서 히트 레이턴시를 높이는 대신 충돌 가능성을 줄인 것이다.

Reference

https://parksb.github.io/article/29.html
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Computer%20Architecture/%EC%BA%90%EC%8B%9C%20%EB%A9%94%EB%AA%A8%EB%A6%AC(Cache%20Memory).md
https://it.donga.com/215/
https://namu.moe/w/%EC%BA%90%EC%8B%9C%20%EB%A9%94%EB%AA%A8%EB%A6%AC
https://namu.moe/w/%EB%A9%94%EB%AA%A8%EB%A6%AC%20%EA%B3%84%EC%B8%B5%20%EA%B5%AC%EC%A1%B0#s-3.3
https://velog.io/@rnjsrntkd95/%EC%BA%90%EC%8B%9C-%EB%A9%94%EB%AA%A8%EB%A6%ACCache-Memory
https://aidanbae.github.io/code/devops/computer/cpucache/