[컴퓨터 구조] - 메모리 #2 캐시 (cache)

메모리 #1 에서 메모리 구조와 캐시가 왜 필요한지, 어떠한 아이디어로 도입된 것인지 다루었다. 그 내용을 바탕으로 L1 캐시를 도입한 작은 컴퓨터를 구현했다고 하자. 그러면 CPU는 메모리를 요청할 때 먼저 그 데이터가 캐시에 있는지 확인하는 과정이 필요하다. 근데 어떻게 메모리에 있는지, 그리고 캐시의 어느 위치에 있는지 알 수 있을까?

방법은 lookup table을 이용하는 것이다. 캐시의 tag와 유효성 등을 저장해서 캐시에 저장되어 있는지 / 저장되어 있다면 어디 있는 것인지 확인할 수 있는 표를 가지고 있는 것이다.

Direct mapped cache

첫번째로 살펴볼 캐시로 Direct mapped cache를 골랐다.

Direct mapped cache는 메모리주소에 따라 캐시에 자장되는 위치가 결정되는 캐시이다. 가장 쉬운 방식으로 modulo 방식을 사용하면,

$$\text{index} = \text{(address of a block)} \mod{ \text{(blocks in cache)} }$$

위처럼 block의 메모리 주소에 따라 고유하게 cache를 대응시킬 수 있다.

보통 blocks in cache는 $2^n$개가 있고, 프로그램의 locality를 살려 캐시를 구현한다고 하면,

$$\text{index} = \text{(address of a block)} \& (\text{(blocks in cache)}-1)$$

위처럼 구현하는 것이 효율적일 것이다. Spatial locality를 고려하면 lower bits를 이용하여 캐싱하는 것이 유리하기 때문이다.

Example

<캐시>

0	1
1	4

(000, 011이 캐시에 들어간 상황)

<메모리>

000	001	010	011	100	101	110	111
1	2	3	4	5	6	7	8

 

하지만 캐시를 인덱스로만 가지고 있는 것은 충분하지 않다. 내가 찾는 데이터와 캐시에 있는 데이커가 같은지 알아야 하기 때문에 high-order bits 또한 비교해야 한다. 그러기 위해서 tag를 도입한다. Tag는 adress의 상위 t 비트를 저장해서, 원하는 데이터가 맞는지 검증하는 역할을 한다. 그리고 valid bit도 추가할 것인데, 캐시가 초기상태, 즉 비어있는 경우 해당 위치의 캐시가 유효하지 않다는 의미로 0, 캐시가 저장되어 유효해지면 1을 저장하는 용도이다. 그리고 lowerbits 마지막에 byte offset을 주어 블록의 어느 부분을 addressing 하는지 명시한다. (아래 그림에서 100 부분)

 

예제 - 8bit cache

<캐시>

idx	valid	tag	data
000	Y	10	Mem[10000]
001	N
010	Y	10	Mem[10010]
011	Y	00	Mem[00011]
100	N
101	N
110	Y	10	Mem[10110]
111	N

 

<메모리 요청 목록>

addr(int)	addr(bin)	cache idx	hit/miss
22	10 110	110	Miss
26	11 010	010	Miss
22	10 110	110	Hit
26	11 010	010	Hit
16	10 000	000	Miss
3	00 011	011	Miss
16	10 000	000	Hit
18	10 010	010	Miss

 

위처럼 작동한다고 보면 된다.

 

Cache Miss

1) Cache Hit → 정상적으로 진행

2) Cache Miss → ???

 

캐시 미스 발생시 cpu cycle을 stall 하고 다음 hierachy에서 block을 가져와야 한다. 그동안 cpu cycle을 stall해야 하고 만약 instruction을 fetch하는 중이었다면 다시 fetch하고 데이터의 경우에는 완전히 다시 가져와야한다. 그런데 한가지 의문이 든다. 만약 데이터를 업데이트하는 중이라면 캐시를 어떻게 관리해야할까? 즉, 데이터를 cache만 바꿔야 할지, 메모리도 업데이트할지에 대한 문제이다.

크게 두가지 해결책이 있는데, write-through와 write-back이 있다.

Note: cache의 데이터가 교체되는 것을 `eviction`이라 한다.

Handling write

Write-through

→ data-write가 hit이라면 캐시의 블록을 업데이트 하자

그러면 메모리의 outdated data는 어떻게 관리....? $\Rightarrow$ 메인 메모리도 함께 업데이트하자!

근데 write하는 동안 기다리면 시간이 너무 오래 걸리니까 write buffer을 도입하여 write할 데어터를 임시로 들고 있자. cpu는 write buffer이 가득 차지 않는 이상 멈출 필요가 없어진다.

Write-back

→ data-write가 hit이라면 캐시의 블록만 업데이트 하자

그러면 메모리의 outdated data는 어떻게 관리....? $\Rightarrow$ 캐시에서 내려갈 때 업데이트 진행시키기

그러기 위해서 메모리와 캐시와 값이 달라졌는지 확인할 "dirty bit"을 도입하여 관리한다. 근데 write-through에서처럼 write하는 동안 기다리면 시간이 너무 오래 걸리니까 write buffer을 두어 eviction이 일어날 때 write을 기다리지 않게 한다.

Write Miss

→ data-write가 캐시에 없다면...?

1) Allocate on miss:  write할 데이터를 캐시로 옮겨오고 write하자 (주로 write-back)

2) Write around: 캐시에 옮기지 말고 write하자 (initialization처럼 access하고 사용하지 않는 경우 존재)

Block size

이제 블록 크기와 miss rate에 대한 고찰을 해보려 한다. Spatial locality에 따르면 block size가 클수록 캐시에 원하는 데이터가 있을 가능성이 크므로 miss rate가 줄어들 것이다. 그러나 총 캐시의 크기가 유한하다면 block size가 커지는 만큼 block count가 줄어드니, 블록의 크기가 너무 크면 오히려 miss rate가 증가한다. 또, miss 발생시 가져와야하는 데이터의 양이 커지기 때문에 miss penalty가 증가하게 된다. 

마지막 "miss penalty가 증가한다"라는 문제는 두 가지 방법으로 해결할 수 있다.
Early Restart: 요청한 word를 가져오면 바로 execution을 재개한다
Requested(Critical) word first: 요청된 word를 가장 먼저 가져오고 나머지를 가져온다.

Miss penalty Reduction

DRAM에서 fetch를 할때의 penalty를 줄일 방법.

예시와 함께 살펴보자

---

DRAM Spec

• 15 Bus cycle per access
• 1 bus cycle for address, data transfer

Block-size = 4 words  &  1 word-wide DRAM

Miss penalty = 1 + 4 x 15 + 4 x 1 = 65 Bus cycles

Bandwidth = 16 bytes / 65 Bus cycles = 0.25 bytes / cycle

 

Block-size = 4 words  &  4 word-wide DRAM

Miss penalty = 1 + 15 + 1 = 17 Bus cycles

Bandwidth = 16 bytes / 17 Bus cycles = 0.94 bytes / cycle

 

Block-size = 4 words  &  4-bank interleaved memory

Miss penalty = 1 + 15 + 4 x 1 = 20 Bus cycles

Bandwidth = 16 bytes / 20 Bus cycles = 0.8 bytes / cycle

 

Note. `4 x 1` 부분은 4 word를 다시 전송하는 부분이다. 첫번째의 경우 4word를 전송하는데 4x1의 시간이 걸린 것이고 세번째의 경우는 병목현상에 의해 첫번째와 마찬가지로 4x1의 시간이 걸린 것이다.

 

위처럼 메모리 구성에 따라 대역폭이 바뀌는 것을 계산할 수 있다.

---

Summary

Block size에 따라서 tradeoff가 존재!

 

Block 크기가 클수록 miss rate가 감소하지만 miss penalty는 증가

Early restart/Critical word first를 활용하거나 memory bandwith를 증가시켜야 한다.