CS 지식/컴퓨터구조

[컴퓨터구조] 16-3. Cache Coherence

2023.10.10

Cache Summary

캐시에는 어떤 데이터를 가지는가?
- Recently used data (temporal locality)
- Nearby data (spatial locality)
데이터를 어떻게 찾는가?
- Set은 데이터의 주소에 의해 결정된다.
- block내 word도 주소에 의해 결정된다.
- associative cache에서 데이터는 여러 way 중 하나로 저장될 수 있다.
데이터는 어떻게 교체되는가?
- Least-recently used(LRU) way in the set

Miss Rate Trends

Compulsory는 처음에 일어났다가 그 이후는 거의 안생긴다.
conflict도 cache size에 따라 줄어든다.

더 큰 block은 compulsory miss를 감소시킨다.
더 큰 block은 conflict miss를 증가시킨다.
block을 무작정 키우면 set의 갯수가 줄어들 것이다.
- 그래서 결국 conflict miss가 늘어날 수 밖에 없음.

Cache Design Trade-offs

각각의 miss rate을 줄이기 위한 design change

capacity miss
- cache size의 증가
- 단점: access time가 증가될 수 있다
conflict miss
- associativity 증가
- 단점: access time가 증가될 수 있다.
compulsory miss
- block size의 증가
- 단점: miss penalty가 증가한다. 매우 큰 block size의 경우, pollution 때문에 miss rate이 증가할 수 있다.

Multilevel Caches

여러 개의 cache를 두는데 CPU와 가까운 cache는 최대한 빨라야 함.
그치만 miss rate도 줄여야 하기 때문에 L2 cache를 두어서 memory까지 안 가도록 함.
더 큰 caches는 더 낮은 miss rate과 더 긴 access time을 갖는다.
메모리 계층을 multiple level of caches로 확장한다.
Level 1 (Primary): CPU에 붙어있는 캐시
- small and fast (e.g. 16 KB, 1 cycle)
- CPU와 가까이 있기 때문에 빨라야 함
Level 2: L1 cache로부터 misses를 service한다
- 더 크고 더 느리지만, 여전히 main memory보다는 빠르다.(e.g. 256 KB, 2-6 cycles)
- memory까지 안가기 위해서 용량이 어느 정도 커야함
대부분 현대 PC는 L1, L2, and L3 cache를 갖는다.
(see Google.com for example CPUs)

Multilevel Cache Example

다음과 같이 주어졌을 때,
- CPU base CPI = 1, clock rate = 4GHz
- Miss rate/instruction = 2%
- Main memory access time = 100ns
With just primary cache
- Miss penalty = 100ns/0.25ns = 400 cycles
- Effective CPI = 1 + 0.02 × 400 = 9
  - hit이면 CPI=1, miss이면 miss rate에 해당하는 CPI( 0.02 × 400)
- 9 clock에 하나씩 instruction이 들어오는 것이므로 굉장히 성능이 안 좋다.
Now add L-2 cache
- Access time = 5ns
- Global miss rate to main memory = 0.5%
- Primary miss with L-2 hit: Miss Penalty = 5ns/0.25ns = 20 cycles
- Primary miss with L-2 miss: Extra penalty = 400 cycles
- CPI = 1 + 0.02 × 20 + 0.005 × 400 = 3.4
Performance ratio = 9/3.4 = 2.6

Multilevel Cache Considerations

Primary cache
- 최소의 hit time에 집중한다.
L-2 cache
- main memory 접근을 피하기 위해 낮은 miss rate에 집중한다.
- hit time은 더 낮은 전체 impact을 갖는다.
Results
- L-1 cache는 대개 single cache보다 더 작다
- L-1 block 크기는 L-2 block 크기보다 작다.

Intel Pentium III Die

Intel Pentium III Die

Memory Controller <-> DRAM

Software optimization

array가 cache에 딱 들어맞지 않는다고 가정하면 loop의 중첩을 교환하는 것이 spatial locality를 향상시킬 수 있다.
Data stored in row-major ordering (in C-language):

/* before */
for(j = 0; j < 100; j++)
    for(i = 0; i < 5000; i++)
        x[i][j] = 2 * x[i][j];

/* after */
for(i = 0; i < 5000; i++)
    for(j = 0; j < 100; j++)
        x[i][j] = 2 * x[i][j];

after와 같이 되어있어야 데이터가 저장되어 있는 순서대로 access하기 때문에 cache를 잘 사용하는 것이다.

before 방식처럼 사용하게 되면 access를 세로로 하기 때문에 데이터 access를 계속 jump를 해 가면서 하기 때문에 locality를 완전히 무시하게 된다.

Software optimization via Blocking

목표: 데이터가 교체되기 전에 데이터에 대한 접근을 최대화시키는 것
- Consider the loops of DGEMM (double precision general matrix multiplication): X = YZ

for ( i = 0; i < n, ++i)
    for ( j = 0; j < n; ++j)
    {
        r = 0;
        for( k = 0; k < n; k++ )
            r += Y[i][k] * Z[k][j];
        X[i][j] = r;
    }

n by n이 size가 작으면 상관 없는데 크면 문제가 된다.

두 개의 내부 루프는 모든 N을 Z의 N개 원소로 읽고, 같은 N개 원소를 Y의 행으로 반복해서 읽고, X의 N개 원소 중 한 행을 write한다.

Software optimization via Blocking

X, Y and Z arrays

column을 가져와야 하는 j는 부담이 너무 크다.

Software optimization via Blocking

/* after */
for (jj=0, jj < n, jj = jj+B)
for (kk=0, kk < n, kk = kk+B)

for ( i = 0; i < n, ++i)
    for ( j = jj; j < min(jj+B, n); ++j)
    {
        r = 0;
        for( k = kk; k < min(kk+B, n); k++ )
            r += Y[i][k] * Z[k][j];
        X[i][j] = X[i][j] + r;
    }

그래서 한 번에 쭉 다 계산하는 것이 아니라 적당한 block을 나누면 충분히 cache에 올라올 수 있기 때문에 그것에 대해서 계산을 진행하고 Block pointer를 옮겨가면서 Block 마다 matrix 계산을 쭉 이어 나간다.

이제 두 내부 루프는 X와 Z의 전체 길이가 아니라 크기 B의 단계로 계산됩니다. (X는 0으로 초기화된다고 가정합니다.)

Example (n=4, B=2)

두번째 퍼즐 그림 잘못됨

Software optimization via Blocking

GFLOPS - 초당 몇 기가의 floating point 계산을 할 수 있는지
blocked는 새로 block이 올라올 때만 바꾸면 되기 때문에 초당 연산량이 거의 감소하지 않는다.

Cache Coherence Problem

Shared memory
두 개의 CPU cores가 물리적인 주소 공간을 공유한다고 가정
- Write-through caches

처음에는 memory에 0이 들어있었다.
cache A가 이를 read 하면 A cache에는 0이 써질 것이다.
cache B가 또 read하면 B에도 0이 써질 것이다.
CPU A가 데이터 0을 1로 바꾸면 그 즉시 메모리 X에도 반영되어 write한다.
그러면 cache와 memory에 값들이 전부 다 다른 문제가 발생한다. -> cache coherence

두 CPU의 각 cache(즉, 클라이언트) 에서 접근한다고 했을 때 캐시의 갱신으로 인한 데이터 불일치가 생기는데 예를 들어, 쉽게 말해서 변수 x가 있는데 이 값은 0이다.

그런데 A에서 이 값을 1로 바꾸었고 B에서 x값을 읽는 상황을 가정해 보면, CPU B는 A가 수정한 값 1을 읽는 것이 아니라 현재 자신의 로컬 캐시인 0을 읽을 수 밖에 없다. 따라서 캐시 1, 2는 같은 X라는 변수에 대해 다른 값을 가지게 되므로 데이터 불일치 문제가 발생한다.

Cache Coherence Protocols

일관성( coherence )을 보장하기 위해 multiprocessors에서 캐시가 수행하는 연산
- local caches로 데이터의 migration
  - shared memory에 대한 bandwidth를 감소시킨다.
- read-shared 데이터의 복제(replication)
  - Reduces contention for access
  - 접근에 대한 경쟁을 감소시킨다.
Snooping protocols (snoop: 돌아다니면서 몰래 살펴보는)
- 각 cache는 bus reads/writes을 모니터한다.
- bus를 통해 누가 쓰고 있는지 아닌지를 모니터한다.
Directory-based protocols
- 어느 cache가 사용했는지 전부 기록하는 방식
- caches와 메모리가 directory에 block의 상태를 공유하는 것을 기록한다.

Invalidating Snooping Protocols

Cache는 block을 기록할 때 block에 대한 독점적인 접근 권한을 갖는다
- bus에서 유효하지 않은 메시지를 broadcast 한다
- Subsequent read in another cache misses
- 또 다른 cache에서 후속 읽기가 miss된다.
  - cache 소유를 통해 업데이트된 가치 제공