[컴퓨터 구조] - 메모리 #3 캐시 최적화 (Cache Optimization)

Cache Performance

이제부터는 캐시의 효율성에 관한 논의를 하고자 한다. 그러기 위해서 효율성의 지표를 설정해야 하는데 Memory stall cycles을 기준으로 한 것과 Average memory access time을 기준으로 한 것을 살펴볼 것이다.

모델링 (Memory stall cycles 기준)

캐시의 성능은 아래와 같은 수식으로 나타낼 수 있다.
$$\begin{align*}&\text{Memory stall cycle}\\ &= \frac{ \text{Memory access} }{\text{Program}} \times \text{Miss rate} \times \text{Miss penalty} \\ &= \frac{ \text{Instructions} }{\text{Program}} \times \frac{ \text{Misses} }{\text{Instruction}} \times  \text{Miss penalty} \end{align*}$$
 
예제

• I-cache miss rate = 2%
• D-cache miss rate = 4%
• Miss penalty = 100 cycles
• Base CPI (ideal cache) = 2
• Load & stores are 36% of instructions

Miss cycles per instruction

• I-cache: 0.02 x 100 = 2
• D-cache: 0.36 x 0.04 x 100 = 1.44

Actual CPI = 2 + 2 + 1.44 = 5.44
→ Ideal CPU is 5.44/2 = 2.72 times faster
 
Tip: 계산은 (원래 CPI) + (추가되는 CPI) 꼴로 계산해주면 된다. 시험을 볼 예정이라면 위쪽에 계산법만 잘 숙지하자!
 

모델링 (Average memory access time 기준)

Hit time 또한 고려해서 만든 성능지표로 Average memory access time (AMAT)이 있다.
$$\begin{align*}&\text{AMAT} =  \text{Hit time}  + \text{Miss rate} \times \text{Miss penalty}   \end{align*}$$
 
 
예제

• CPU with 1ns clock
• Hit time = 1 cycle
• Miss penalty = 20 cycles
• I-cache miss rate = 5%

AMAT = 1 + 0.05 x 20 = 2ns (2 cycles per instruction)

요약

• CPU가 좋아짐에 따라 메모리의 miss penalty를 무시할 수 없음
• CPU 발전 → CPI 감소 → 메모리 stall이 차지하는 비중 up
• CPU 발전 → Clock freq up → 메모리 stall 동안 기다리는 clock 수 up

따라서 성능 평가에서 캐시를 무시할 수 없다...!

캐시 성능 높이기

AMAT의 수식을 통해
$$\begin{align*}&\text{AMAT} =  \text{Hit time}  + \text{Miss rate} \times \text{Miss penalty}   \end{align*}$$
1) $ \text{Hit time} $을 줄이거나
2) $ \text{ Miss rate } $을 줄이거나
3) $ \text{ Miss penalty } $을 줄여야
캐시의 성능이 좋아진다.

Miss rate를 줄이자: Associative cache

이전글에서 설명한 Direct mapped cache는 메모리 주소마다 들어갈 수 있는 캐시를 지정해두어서 캐시가 비어 있다고 해도 지정된 자리가 아니면 들어갈 수 없었다. 그래서 모든 자리를 아낌없이 쓸 수 있도록하는 방식이 등장했는데 바로 Associative cache이다. Associative cache도 얼마나  Associative한지에 따라 종류가 여러개인데 이 글에서는 n-way set associative를 주로 다룰 것이다.

---

Fully associative cache

• 블록이 캐시의 어느 자리라도 들어갈 수 있게 함
• 캐시에 있는 모든 entries를 동시에 탐색할 수 있게 함
  • 동시에 탐색한다 = 모든 entries를 동시에 비교한다 = 구현이 어렵고 복잡, 다수의 비교기 필요
  • 이 문제 때문에 주로 set associative cache를 많이 사용한다.

n-way set associative
Set associative는 direct mapped와 fully associative를 섞은 것으로 블록은 몇그룹으로 나누어 그룹 안에서 탐색을 하는 방식이다. 이렇게 하면 같은 direct mapped보다 유연하게 데이터를 캐시에 넣을 수 있으며, fully associative보다 적은 비교가 필요하다.

• 각 set은 $n$개의 entries 보유
• Block number = $\text{Block number} \mod{\text{sets in cache}}$
• 같은 set 안에 있는 entries를 동시 비교
• $n$개의 비교기가 필요

이때 n-way set associative에서 n-way는 set 안 block의 개수를 의미한다. 착각하지 않도록 주의하자.
 
예제
- 4 block caches
- Access 0,8,0,6,8
1) Direct mapped

Block Addr	Cache idx	Hit/Miss	Cache contents
			0	1	2	3
0	0%4=0	Miss	mem[0]
8	8%4=0	Miss	mem[8]
0	0%4=0	Miss	mem[0]
6	6%4=2	Miss	mem[0]		mem[0]
8	8%4=0	Miss	mem[8]

 
2. 2-way associative

Block Addr	Cache idx	Hit/Miss	Cache contents
			set 0		set 1
0	0%2=0	Miss
8	8%2=0	Miss	mem[0]	mem[8]
0	0%2=0	Hit	mem[0]	mem[8]
6	6%2=2	Miss	mem[6]	mem[8]
8	8%2=0	Miss	mem[6]	mem[0]

 
3) Fully associative

Block Addr

Cache idx

Hit/Miss

Cache contents

0

-

Miss

mem[0]

mem[8]

8

-

Miss

mem[0]

mem[8]

0

-

Hit

mem[0]

mem[8]

6

-

Miss

mem[0]

mem[8]

mem[6]

8

-

Hit

mem[0]

mem[8]

mem[6]

 

---

 
Cache의 구조를 각각의 경우에 대해서 살펴 보았는데 어느 설계가 가장 효율적일까? Associativity에 따라 miss rate를 측정해보면 miss-rate가 계속 감소하다가 어느 순간부터는 줄어드는 폭이 급감하는 지점이 생긴다. 따라서 too much associativity보다는 적당한 지점을 찾는 것이 유리하다.
Set-associative 설계의 회로도는 아래와 같다.

---

캐시 성능을 높이기 위한 다음 방법을 소개하기 전에 세 개의 캐시 구조에 대해서 더 다루고자 한다. 구현에 대한 추가적인 설명이라고 생각하고 읽으면 된다.
 
Cache Organization
캐시의 크기는 Set의 개수 x Entry의 개수 x 데이터의 크기, 즉
$$\text{C} = \text{S} \times \text{E}  \times \text{B} $$
이다.
아래처럼 주어진 memory addressing에서

t bits (tag)

s bits (set idx)

b bits (block offset)

캐시를 읽을때는 

1. set idx 확인
2. tag 확인
3. valid 확인
4. offset 확인

의 과정을 거치게 된다.
 
Replacement Policy
캐시에 저장된 값을 교체할 때 어떠한 원칙으로 교체할지에 대한 질문.

1. Direct mapped cache: 무조건 정해진 위치에 넣어야 하므로 선택권이 없이 교체당한다.
2. Set-associative
   1. non-valid entry 우선
   2. Least-recently used (LRU) : 2, 4-way 정도에서만 활용, n이 커지면 구현이 너무 어려움
   3. 또는 Random도 사용할 수 있다.

Miss Penalty를 줄이자: Multilevel Cache

메모리 #1에서 다루었던 계층구조를 적용해서 miss penalty를 줄일 수 있다. L1, L2, L3 등의 캐시를 도입한다.
 
예제
조건

• CPU base CPI = 1, clock rate = 4GHz
• Miss rate / instruction = 2%
• Main memory access time = 100ns

만약 Primary Cache만 사용할 경우:
Miss penalty = 100ns / 0.25ns = 400 cycles
CPI = 1 + 0.02 x 400 = 9
 
만약 아래의 성능을 가진 L2 캐시를 도입한다면,

• Access time = 5ns
• Global miss rate to main memory = 0.5%

L1 miss + L2 hit Penalty = 5ns / 0.25ns = 20 cycles
L1 miss + L2 miss Penalty = 400 cycles
CPI = 1 + 0.02 x 20 + 0.05 x 400 = 3.4
$\Rightarrow$ 성능은 9/3.4 = 2.6 이 증가
 
Note: L2 캐시는 main memory access를 줄이는 것이 목표이기에 miss rate를 줄이는데 관심이 있다. 따라서 더 높은 associativity을 활용한다.
 

Q. 왜 Hit rate 대신 Miss rate을 주로 쓸까?
A. 성능에 영향을 미치는 지표는 miss 이기에 miss rate을 주로 사용한다. miss penalty로 stall 하는 cycles 수가 상당히 크기 때문에 97% hit rate와 99% hit rate은 거의 2배의 성능차이를 보이는데 이것을 수치화 할 때 hit rate보다는 miss rate(3%, 1%)가 더 직관적이다. 

 

Software

이제 메모리 구조에 따른 소프트웨어의 성능을 살펴보고자 한다. 캐시의 특성에 따르면 소프트웨어를 만들 때는

• Focus on the inner loops of the core functions
• Minimize the misses in the inner loops
  • repeated references to variables are good (temporal locality)
  • Stride-1 reference patterns are good (spatial locality)

이 정도의 원칙에 맞추어 제작하는 것이 좋다. 즉, 지역성을 최대한 살리는 코드일수록 유리하다.
 

예제: Matrix multiplication

이 예제에서 행렬곱에서 곱하는 순서에 따라서 프로그램의 효율성이 어떻게 바뀌는지 알아볼 것이다.
가정은 캐시 라인의 크기가 32 byte라 가정한다. 그리고 double은 8바이트이다.
순차접근을 하면 32 / 8 = 4번마다 cache miss가 발생하는 구조이다.
 
i j k 순서

/* ijk */
for (i=0; i<n; i++) {
    for (j=0; j<n; j++) {
        sum = 0.0;
        for (k=0; k<n; k++)
            sum += a[i][k] * b[k][j]; // 여기 캐시미스에 집중
        c[i][j] = sum;
    }
}

 
$\Rightarrow$ Miss per inner loop A = 0.25, B = 1.0, C = 0.0
 
j i k 순서

/* jik */
for (j=0; j<n; j++) {
    for (i=0; i<n; i++) {
        sum = 0.0;
        for (k=0; k<n; k++)
            sum += a[i][k] * b[k][j];
        c[i][j] = sum;
    }
}

 
$\Rightarrow$ Miss per inner loop A = 0.25, B = 1.0, C = 0.0
 
k i j 순서 ☆

/* kij */
for (k=0; k<n; k++) {
    for (i=0; i<n; i++) {
    	r = a[i][k];
        for (j=0; j<n; j++)
        	c[i][j] += r * b[k][j];
    }
}

 
$\Rightarrow$ Miss per inner loop A = 0.0, B = 0.25, C = 0.25
 
i k j 순서 ☆

/* ikj */
for (i=0; i<n; i++) {
    for (k=0; k<n; k++) {
    	r = a[i][k];
        for (j=0; j<n; j++)
        	c[i][j] += r * b[k][j];
    }
}

 
$\Rightarrow$ Miss per inner loop A = 0.0, B = 0.25, C = 0.25
 
j k i 순서

/* jki */
for (j=0; j<n; j++) {
    for (k=0; k<n; k++) {
        r = b[k][j];
        for (i=0; i<n; i++)
        	c[i][j] += a[i][k] * r;
    }
}

 
$\Rightarrow$ Miss per inner loop A = 1.0, B = 0.0, C = 1.0
 
k j i 순서

/* kji */
for (k=0; k<n; k++) {
    for (j=0; j<n; j++) {
        r = b[k][j];
        for (i=0; i<n; i++)
        	c[i][j] += a[i][k] * r;
    }
}

 
$\Rightarrow$ Miss per inner loop A = 1.0, B = 0.0, C = 1.0
 
위 예제를 통해 kij나 ijk의 접근이 캐시 효율성이 높다는 것을 알 수 있다.
따라서 코드를 작성할 때 시공간적 지역성을 잘 지키도록 코드를 짜는 연습을 하자.