시간지역성
for (i = 0; i < 10; i += 1) {
arr[i] = i;
}- 시간 지역성은 최근 접근한 데이터에 다시 접근하는 경향을 말한다. 가령 루프에서 인덱스 역할을 하는 변수 i에는 짧은 시간안에 여러 번 접근이 이뤄진다.
공간지역성
for (i = 0; i < 10; i += 1) {
arr[i] = i;
}- 공간 지역성은 최근 접근한 데이터의 주변 공간에 다시 접근하는 경향을 말한다. 위 루프의 경우 배열 arr의 각 요소를 참조하면서 가까운 메모리 공간에 연속적으로 접근하고 있다. 배열의 요소들이 메모리 공간에 연속적으로 할당되기 때문이다.
캐시레이어
- CPU 칩에는 여러 개의 캐시가 들어가며, 각각의 캐시는 각자의 목적과 역할을 가지고 있다.
L1 Cache
- 프로세서와 가장 가까운 캐시. 속도를 위해 I$와 D$로 나뉜다.
- Instruction Cache (I$): 메모리의 TEXT 영역 데이터를 다루는 캐시.
- Data Cache (D$): TEXT 영역을 제외한 모든 데이터를 다루는 캐시.
L2 Cache
- 용량이 큰 캐시. 크기를 위해 L1 캐시처럼 나누지 않는다.
L3 Cache
- 멀티 코어 시스템에서 여러 코어가 공유하는 캐시.
캐쉬레이어 구조
- 오늘날 CPU 칩의 면적 30~70%는 캐시가 차지한다. 1989년 생산된 싱글 코어 프로세서인 i486의 경우 8KB짜리 I/D 캐시 하나만 있었다. 한편 인텔 코어 i7 쿼드 코어 칩의 다이 맵(Die map)을 보면 4개의 코어에 각각 256KB L2 캐시가 있고, 모든 코어가 공유하는 8MB L3 캐시가 있는 것을 볼 수 있다. (L2 캐시 위에 있는 구역이 L1 캐시로 보이는데, 확실하지 않아서 따로 표시하지 않았다.)
캐시 레이턴시
히트 레이턴시
- CPU에서 요청한 데이터가 캐시에 존재하는 경우를 캐시 히트(Hit)라고 한다. 히트 레이턴시는 히트가 발생해 캐싱된 데이터를 가져올 때 소요되는 시간을 의미한다.
미스 레이턴시
- 반면 요청한 데이터가 캐시에 존재하지 않는 경우를 캐시 미스(Miss)라고 하며, 미스 레이턴시는 미스가 발생해 상위 캐시에서 데이터를 가져오거나(L1 캐시에 데이터가 없어서 L2 캐시에서 데이터를 찾는 경우) 메모리에서 데이터를 가져올 때 소요되는 시간을 말한다.
평균접근시간
캐시성능 개선
- 캐시의 성능을 높이기 위해서는 캐시의 크기를 줄여 히트 레이턴시를 줄이거나, 캐시의 크기를 늘려 미스 비율을 줄이거나, 더 빠른 캐시를 이용해 레이턴시를 줄이는 방법이 있다.
캐시구조
- 캐시는 반응 속도가 빠른 SRAM(Static Random Access Memory)으로, 주소가 키(Key)로 주어지면 해당 공간에 즉시 접근할 수 있다. 이러한 특성은 DRAM(Dynamic Random Access Meomry)에서도 동일하지만 하드웨어 설계상 DRAM은 SRAM보다 느리다. 통상적으로 '메인 메모리’라고 말할 때는 DRAM을 의미한다.
- 주소가 키로 주어졌을 때 그 공간에 즉시 접근할 수 있다는 것은 캐시가 하드웨어로 구현한 해시 테이블(Hash table)과 같다는 의미다. 캐시가 빠른 이유는 자주 사용하는 데이터만을 담아두기 때문이기도 하지만, 해시 테이블의 시간 복잡도가 O(1) 정도로 빠르기 때문이기도 하다.
- 캐시는 블록(Block)으로 구성되어 있다. 각각의 블록은 데이터를 담고 있으며, 주소값을 키로써 접근할 수 있다. 블록의 개수(Blocks)와 블록의 크기(Block size)가 캐시의 크기를 결정한다.
캐시 인덱싱
- 전체 주소에서 하위 5비트를 오프셋(Offset)으로 쓰고, 이후 10비트를 인덱스(Index)로 사용하여 블록에 접근했다. 인덱스가 10비트인 이유는 2^n개 블록의 모든 인덱스를 표현하기 위해서는 log2Nblocks 만큼의 비트가 필요하기 때문이다. 여기에선 블록 개수가 2^10 = 1024개이므로, log2 1024 = 이 되어 10비트가 인덱스 비트로 사용되었다.
- 그러나 이렇게만 하면 서로 다른 데이터의 인덱스가 중복될 위험이 너무 크다.
직접매핑 (Direct mapping)
- main memory 주소당 캐시의 자리는 딱 1곳으로 unique하게 정해진다.
- 위의 그림에서 보면 main memory의 00001, 01001 10001, 11001은 모두 캐시의 001에 매핑 됨을 볼 수 있다.(이들을 비교하기 위해 tag라는 추가 비트가 존재한다.) 이렇듯 공간은 확실하나 한 개의 데이터밖에 들어갈 수 없으므로 단점이 될 수 있다. 만약, 위 그림에서 00001과 01001이 번갈아 가면서 요구 된다면 매번 miss가 발생해 성능이 매우 저하될 것이다.
캐시 태그
- 인덱스의 충돌을 줄이기 위해 주소값의 일부를 태그(Tag)로 사용한다. 블록 개수가 1024개이고, 블록 사이즈가 32바이트일 때, 32비트 주소 0x000c14B8에 접근한다고 가정해보자:
- 먼저 인덱스(0010100101)에 대응하는 태그 배열(Tag array)의 필드에 접근한다.
- 이어서 해당 태그 필드의 유효 비트(Valid bit)를 확인한다.
- 유효 비트가 1이라면 태그 필드(00000000000011000)와 주소의 태그(00000000000011000)가 같은지 비교한다.
- 비교 결과(true, 1)를 유효 비트(1)와 AND 연산한다.
- 유효 비트가 1이라는 것은 해당 블록에 올바른 값이 존재한다는 의미다. 태그 필드와 주소의 태그가 같고, 유효 비트도 1이므로 위 예시의 결과는 히트다. 히트가 발생하면 데이터 배열(Data array)에서 해당 인덱스의 데이터를 참조한다. (참고로 데이터 배열과 태그 배열도 모두 하드웨어다.)
- 만약 유효 비트가 0이라면 블록에 값이 없거나 올바르지 않다는 뜻이므로 미스가 발생한다. 그러면 주소의 태그를 태그 필드에 작성하고, 데이터 필드에도 상위 캐시나 메모리에서 요청한 값을 가져와 작성한 뒤, 유효 비트를 1로 바꿔준다.
- 유효 비트가 1이라도 태그가 일치하지 않으면 미스가 발생한다. 이 경우 교체 정책(Replacement policy)에 따라 처리가 달라진다. 먼저 입력된 데이터가 먼저 교체되는 FIFO(First-In First-Out) 정책을 사용한다면 무조건 기존 블록를 교체한다. 태그 배열의 필드를 주소의 태그로 바꾸고, 상위 캐시나 메모리에서 요청한 데이터를 가져와 데이터 필드의 값도 새 데이터로 바꿔준다. (실제로는 요청한 데이터뿐 아니라 그 주변 데이터까지 가져온다.) 기존 데이터는 상위 캐시로 밀려난다.
- 주소의 상위 15비트가 태그 비트로 사용된 이유는 태그 비트가 Address bits - (Log2 BlockSize + Index bits) 로 결정되기 때문이다. 이 경우 32 - (5 + 10) = 17 비트가 태그 비트로 사용되었고, 남은 5비트는 오프셋 비트로 사용되었다.
워드 (Word)
- 워드(word)는 하나의 기계어 명령어나 연산을 통해 저장된 장치로부터 레지스터에 옮겨 놓을 수 있는 데이터 단위이다. 메모리에서 레지스터로 데이터를 옮기거나, ALU을 통해 데이터를 조작하거나 할 때, 하나의 명령어로 실행될 수 있는 데이터 처리 단위이다. 흔히 사용하는 32비트 CPU(ARM 등)라면 워드는 32비트가 된다.
블록 (Block)
- 참조의 지역성때문에, 메인메모리에서 캐시로 데이터를 저장할때 하나의 워드만 가지고 오는게 아니라 인접한 워드까지 여러개를 가지고오는데 이 단위를 블록이라고함
캐시라인
- 메모리부터 가져와 저장된 데이터 묶음을 캐시 라인이라고 한다.
캐시 슬롯
- 캐시기억장치에서 슬롯(Slot) : 한 블록이 저장되는 장소
- 따라서 블록은 캐시기억장치 각 슬롯에 저잗되는 데이터의 길이가 됨
태그 오버헤드
- 태그 배열이 추가되면서 더 많은 공간이 필요하게 되었다. 하지만 여전히 '32KB 캐시’는 32KB 데이터를 저장할 수 있는 캐시라는 의미다. 태그를 위한 공간은 블록 크기와 상관없는 오버헤드(Overhead)로 취급하기 때문이다.
- 1024개의 32B 블록으로 구성된 32KB 캐시의 태그 오버헤드를 구해보자
- 17bit tag + 1bit valid = 18bit
- 18bit X 1024 = 18Kb tags = 2.25KB
- 즉, 7%의 태그 오버헤드가 발생했다.
- 공간뿐 아니라 시간 비용도 발생한다. 태그 배열에 접근해 히트를 확인하고, 그 이후에 데이터 배열에 접근해 데이터를 가져오기 때문에 결과적으로 히트 레이턴시가 증가하게 된다.
- 그래서 두 과정을 병렬적으로 실행한다. 태그 배열에서 히트 여부를 확인하는 동시에 미리 데이터 배열에 접근하는 것이다. 이렇게 하면 히트 레이턴시가 줄어들지만, 미스가 발생했을 때의 리소스 낭비를 감수해야 한다.
Associative Cache
- 서로 다른 두 주소가 같은 인덱스를 가지면 충돌이 발생하고, 교체 정책에 따라 블록을 교체한다. 하지만 충돌이 발생할 때마다 캐시 내용을 바꾸면 더 많은 미스가 발생하게 되고, 한 자리의 내용을 끝없이 바꾸는 핑퐁 문제(Ping-pong problem)가 일어날 수 있다.
핑퐁문제 해결책
- 이 문제는 태그 배열과 데이터 배열을 여러 개 만드는 식으로 개선할 수 있다. 즉, 인덱스가 가리키는 블록이 여러 개가 되는 것이다. 인덱스가 가리키는 블록의 개수에 따라 캐시의 종류를 분류하면 아래와 같다:
- Direct mapped: 인덱스가 가리키는 공간이 하나인 경우. 처리가 빠르지만 충돌 발생이 잦다.
- Fully associative: 인덱스가 모든 공간을 가리키는 경우. 충돌이 적지만 모든 블록을 탐색해야 해서 속도가 느리다.
- Set associative: 인덱스가 가리키는 공간이 두 개 이상인 경우. n-way set associative 캐시라고 부른다.
- direct mapped 캐시와 fully associative 캐시 모두 장단점이 극단적이기 때문에 보통은 set associative 캐시를 사용한다.
간단하게 2-way set associative 캐시의 동작을 살펴보자:
- 주소의 인덱스를 통해 블록에 접근하는 것은 지금까지 본 direct mapped 캐시와 동일하다. 다만 2개의 웨이(Way)가 있기 때문에 데이터가 캐싱되어 있는지 확인하려면 하나의 블록만이 아닌 2개의 블록을 모두 확인해야 한다. 마지막으로 두 웨이의 결과를 OR 연산하면 최종 결과를 낼 수 있다. 모든 웨이에서 미스가 발생하면 교체 정책에 따라 2개의 블록 중 한 곳에 데이터를 작성한다.
- direct mapped 캐시와 비교해서 히트 레이턴시를 높이는 대신 충돌 가능성을 줄인 것이다.
캐시쓰기
- 데이터를 읽는 동작이 아니라 입력하는 동작이 발생하고, 데이터를 변경할 주소가 캐싱된 상태(Write hit)라면 메모리의 데이터가 업데이트되는 대신 캐시 블록의 데이터가 업데이트된다. 이제 '캐시에서 업데이트된 데이터를 언제 메모리에 쓸 것인가?'에 관한 문제가 생긴다. 여기 두 가지 쓰기 정책(Write policies)이 있다.
Write-through
- 캐시에 데이터가 작성될 때마다 메모리의 데이터를 업데이트하는 것이다. 이렇게 하면 많은 트래픽이 발생하지만, 메모리와 캐시의 데이터를 동일하게 유지할 수 있다.
Write-back
- 이 방식은 블록이 교체될 때만 메모리의 데이터를 업데이트한다. 데이터가 변경됐는지 확인하기 위해 캐시 블록마다 dirty 비트를 추가해야 하며, 데이터가 변경되었다면 1로 바꿔준다. 이후 해당 블록이 교체될 때 dirty 비트가 1이라면 메모리의 데이터를 변경하는 것이다.
Write-allocate
- 데이터를 변경할 주소가 캐싱된 상태가 아니라면(Write miss) Write-allocate 방식을 사용한다. 당연한 얘기지만, 미스가 발생하면 해당 데이터를 캐싱하는 것이다. write-allocate를 하지 않는다면 당장은 리소스를 아낄 수 있겠지만 캐시의 목적을 달성하지는 못할 것이다.
참조글