[Parallel Computing] (12) Caches

가장 최근에 사용되었거나 근처의 데이터나 Instruction들은 다시 사용될 확률이 높다. 시간 관점에서 현재 접근했던 데이터는 가까운 시점에 다시 쓰일 수 있다. 이 부분을 Temporal locality라고 한다. 공간 관점에서 사용된 데이터가 저장된 공간 근처의 다른 데이터들은 가까운 시점에 다시 쓰일 수 있다. 이 부분을 Spatial locality라고 한다.
예를 들어, 아래와 같은 코드를 보면 알 수 있다.
sum = 0
for (i = 0; i < 10; i++)
    sum += A[i]
이 코드는 아래와 같이 iteration이 수행된다.
i = 0 -> sum = sum + A[0]
i = 1 -> sum = sum + A[1]
i = 2 -> sum = sum + A[2]
해당 Loop가 순차적으로 수행된다면, i=0에서 한번 접근 했던 sum은 가까운 시점인 i=1에서 다시 쓰인다. 이는 Temporal locality이다. A를 살펴보면 i=0에서 A[0]이고, 가까운 시점인 i=1에서 바로 옆 A[1]을 접근한다. 이는 Spatial locality 이다.
데이터는 물론 Instruction도 동일한 특성을 가지고 있다. For-loop을 수행하기 위해 특정 위치의 Instruction을 반복적으로 사용한다면, 시간적인 측면에서 가까운 시점 내에 다시 쓰이므로 Temporal locality를 갖는다. 기본적으로 Instruction은 순차적으로 수행되므로 Spatial locality를 가지고 있다.
이런 Locality에 관심을 갖는 이유는 다름 아닌 메모리 레이턴시 때문이다. 메인 메모리로 사용되는 DRAM의 경우, CPU의 연산 속도보다 많이 느리다. 어떤 연산을 수행할 때, 메인 메모리로부터 데이터를 가져와야 하는데, 이 시간이 너무 길어 CPU가 기다릴 수도 있다. 그래서 DRAM보다 빠른 메모리 SRAM을  사용하려고 하는데, SRAM은 DRAM에 비해 빠르지만, 매우 비싸고 고용량으로 만들기 어렵다. 따라서 SRAM을 작게 효율적으로 쓰기 위해 CPU 근처에 두었다.
CPU 근처에 둔 SRAM은 위의 Locality를 활용하기 위한 Cache로 사용된다. Cache는 현시점에 사용된 데이터를 올려 두거나(Temporal locality), 사용된 데이터 근처까지 포함하도록 큰 데이터를 올려두거나 근처의 데이터를 미리 올려둘 수도 있다.(Spatial locality)
Cache 저장의 기본 단위를 Cache block/line이라고 부르며, 보통 64B를 사용한다. Cache에 원하는 데이터가 있으면 Hit, 없으면 Miss라 표현한다. Miss일 경우, 다음 Level의 Cache나 메모리로부터 데이터를 가져온다. 물론 Cache 내 저장공간이 없으면, 기존 데이터를 제거하고 새로운 데이터로 변경하기도 한다.
Cache size는 [# of Sets per Cache] x [# of Cache line per Set] x [the size of data per line]
으로 계산가능하다.
Cache 내부에는 현재 해당 Line의 valid 여부를 나타 내는 bit, Address를 구분하는 Tag bit이 존재한다. 기본적으로 Cache의 접근은 Address를 부분별로 Tag, Set index, Offset으로 구분하여 수행된다.
Cache을 구성하는 방식에 따라 Direct-Mapped Caches/Set Associative Caches/Fully Associative Cache로 나눌 수 있다.
해당 구분은 Set 당 Line의 개수가 얼마나 되느냐로 알 수 있다.
만약 16개의 Line이 존재하면,  아래와 같이 표현될 수 있다.
> Direct-Mapped Caches  :: 16개 Set, 1개의 Line per Set  -> 16-Set 1-Way(Line)
> Set Associative Caches :: 4개 Set, 4개의 Line per Set -> 4-Set 4-Way(Line)
> Fully Associative Caches :: 1개 Set, 16개의 Line per Set -> 1-Set 16-Way(Line)

Direct-Mapped Caches는 Set마다 1개의 Cache line만 존재하기 때문에, 같은 Set일 때 처리방식이 간단하다. Cache에 접근할 때 있는 지 없는 지만 확인하면 되고 Cache에 추가할 때는 있으면 바꾸고 없으면 넣으면 된다. 간단해서 좋지만, 동일한 Set에 해당하는 데이터에 접근이 빈번히 발생하면 그 때마다 Cache replacement가 발생하므로 효율이 좋지 않다.
Fully Associatve Caches는 1개의 Set만 가지고 있다. 이 말은 모든 데이터가 1개의 Set에 저장된다. 다시 말하면, Cache 접근이 수행된 데이터 중 과거 Cache line만큼을 가지고 있다는 것이다. Cache 저장공간을 넘어서는 접근이 수행될 때 Cache replacement가 발생한다. 매우 효과적이지만, 데이터가 Cache에 있는지 확인하기 위해 모든 Cacheline의 Tag와 비교를 해야한다. 하드웨어 입장에서 이는 매우 복잡하다.
이 두 가지를 결합한 것이 Set Associative Caches이다. 여러 개의 Set이 존재하고, Set마다 여러 개의 Line을 가지고 있는 것이다. 동일한 Set에 해당하는 데이터에 접근은 한 Set마다 여러 개의 Line으로 효율을 높이고, Cache 검색은 1-Set 내부의 Line 수만큼의 Tag와 비교하면 된다.

Cache Miss 종류에는 아래와 같이 3가지가 있다.
1. Cold Miss       -> Cache가 비어있을 때 발생.
2. Conflict Miss -> Cache는 충분히 크나, 구조적으로 같은 Set에만 접근하여 발생
3. Capacity Miss -> Cache의 크기가 수행되는 working set에 비해 작을 경우 발생
                                     (working set :: 특정 시간 동안 사용되는 Blocks의 집합)

Cache miss가 발생하였고, 이를 메모리로 부터 읽어 왔는데 Cache 내에 자리가 없다면 어떤 Cache line을 대체 할 것인가? 대체하는 방법에는 여러 가지가 있다.
가장 쉽게 생각할 수 있는 것은 LRU(Least Recently Used) 방식이다. 가장 오래전에 접근한 Cacheline을 내보는 것이다. 앞서 이야기한 Locality 측면에서도 오래된 Cacheline을 제거하는 것이 좋다. 가장 오래전에 접근한 Cacheline을 알려면 접근 순서를 기록할 수 있어야 한다. 4개의 way만 가지고 있어도, Cacheline 4개를 순서대로 조합하면 4! = 24개의 상태가 존재한다. 하나의 set마다 이 상태를 다 알 수 있어야 한다. 이는 하드웨어입장에서 매우 큰 비용을 지불해야 한다. 그리고 이를 관리하기 위하여 소모되는 시간이 매우 크다. 그래서 정확하지 않더라도 이런 비용적인 측면을 완화한 방식이 Pseudo LRU이다.
Pseudo LRU는 Tree 구조를 사용한다. 각 Cacheline를 크게 두 개로 나눠 가면서 트리를 구성한다.
예를 들어 4개의 Cacheline, [A,B,C,D]가 존재한다면 Tree는 아래와 같이 구성가능하다.  
                       [A,B-->1] OR [C,D-->0]
[A-->1] OR [B-->0]         |        [C-->1] OR [D-->0]
특정 Cacheline에 접근하면 이 Tree에 따라 해당하는 bit을 기록한다. 위와 같은 경우 아래와 같이 3-bit이 필요하다.
[ AB OR CD] , [A OR B] , [C OR D]
초기값을 0으로 가정하자. A가 입력되었다고 하면 [1, 1, 0] 이 된다.
다음 입력으로 C가 입력되면, [0, 1, 1]이 된다.
그 다음 입력으로 D가 입력되면, [0, 1, 0]이 된다.
이 때의 LRU를 찾아보면, 입력 값을 알고 있는 상태로는 답은 B이다.
그럼 3-bit만으로 어떻게 찾아내는 지 알아보자. 첫번째 bit을 살펴보면 [AB OR CD]이다. 어떤 값이 오던지 해당 bit은 업데이트가 된다. 해당 bit은 0이므로 이전 값은 CD 중의 하나였으니 AB 중 하나가 LRU일 것이다.
AB에 해당하는 bit을 살펴보니 1이었고 AB 둘 중에는 A가 최근에 접근한 걸 알 수 있다. 그러므로 B를 선택한다.
위의 예시처럼 3-bit의 형태만으로 LRU를 알 수 있었다. 물론 아래의 예시 처럼 정확하지 않을 수 있다.
A -> C -> D -> B 인 경우, 정답은 A이다.
이를 적용해보면
[1, 1, 0] -> [0, 1, 1] -> [0, 1, 0] -> [1, 0, 0]이 된다.
첫번째 Bit에서 [CD], 3번째 BIT에서 [C]를 선택하게 된다.
따라서 Pseudo LRU는 C를 선택하였다. 조금 다르지만 성능에 영향을 주는 수준은 아니며, 하드웨어나 검색 속도 측면에서 월등히 좋기 때문에 사용한다.

또한, 가장 오랬동안 있었던 블록을 선택하는 FIFO(First In, First Out), Random으로 수행가능하다.

Cache Read의 경우, Cache 내의 Tag와의 비교를 통해서 찾아내서 읽어가면 된다. 읽는 동작과 Tag를 비교하는 동작을 동시에 수행한 후, 같으면 데이터를 취하고 아니면 무시하면 된다.
그런데 Cache Write의 경우, Tag를 무시하고 Write를 수행하면 안되기 때문에, 동시에 수행할 수 없다.

Cache Write를 수행하는 데, Hit이 발생할 경우 eviction이 발생할 때만 메모리만 쓸 것인가(write-back) 아니면 메모리에도 같이 업데이트 할 것(write through)에 따라 정책이 달라진다.
write through 방식은 Cache 뿐만아니라 메모리에도 데이터 업데이트를 수행한다. 이 경우에는 그냥 그대로 메모리에 적으면 되기때문에 구현이 쉽고, Cache와 메모리 간에 데이터가 항상 같으므로 Consistency가 유지되며, Read를 수행할 때 Cache eviction이 발생하더라도 write를 수행할 필요가 없다는 장점이 있다. 그러나 메모리에도 Write를 수행해야하므로 현저히 느려지며,  모든 Write를 수행할 때마다 메모리 write를 수행해야하므로 메모리 bandwidth를 더 필요로 한다는 단점이 있다.
write back 방식은 write가 cache에만 쓰여지며, 오직 eviciton이 발생할 때만 메모리에 write back을 수행한다. cache에 데이터가 메모리의 데이터와 다르다라는 dirty bit을 두고 관리한다.
이 경우에는 동일한 block 내의 여러 번의 write는 오직 한번의 메모리 write로 수행되므로 메모리 bandwidth를 적게 필요로 하며, write와 read 동작 속도가 비슷하다는 장점이 있다. 그러나 구현 난이도가 높고, Read로 인한 Cache eviction 동작이 발생할 경우, 해당 주소의 데이터가 메모리에 있는 데이터와 다르다면 Memory에도 업데이트를 수행해야 한다. 그리고 Cache와 메모리 간의 Consistency가 항상 유지 되지 않는다.

Cache Write를 수행하는 데, Miss가 발생하는 경우, Cache에 올릴 것인가(write allocate) 아니면 메모리에만 쓸 것인가(No write allocate)에 따라 정책이 달라진다.

앞 서 Cache Miss가 발생하면, 메모리로부터 접근하는 동작이 이뤄지고, 이 동작은 Cache 접근에 비해 느리다고 하였다. 연속된 Cache 접근이 발생했을 때, 앞 선 Cache 접근이 Miss로 인해 멈추면 다음 Cache 접근은 매우 오래 기다려야 한다. 이를 방지하고자 MISS 이후 Cache 접근이 HIt이라면 계속 진행 할 수 있도록 하는 방법이 Non-Blocking/Lockup-Free Cache 이다.
더 나아가 하나의 MISS 보다 더 많은 MISS를 처리할 수 있도록 하는 것이다. 더 많은 MISS를 처리하기 위해서는 MISS에 대한 정보들을 담아두고 처리하는 장치가 필요하다 이를 MSHRs(Miss Status/Information Holding Registers)라 한다.

Cache의 성능은 Miss Rate, Hit Time, Miss Penalty로 결정된다.
평균 성능은 아래와 같이 계산 될 수 있다.
(1-Miss_Rate) * Hit_Time + Miss_Rate * Miss_Penalty