[Cache] Cache의 종류와 Memory System

1. Cache의 종류

1) Fully Associated Cache

entry가 cache의 어느 곳에 들어가든 상관 없다. 속도 slow, 충돌 ↓

2) Direct Mapped Cache

entry가 cache에서 갈 수 있는 위치가 하나로 정해져 있다. 속도 fast, 충돌 ↑

(idx가 가리키는 위치가 1개)

3) Set Associative Cache

1)과 2)의 중간. n-way set associative cache는 entry가 n개의 가능한 위치를 갖는다.

 

2. Cache의 principle of locality

1) Temporal Locality

2) Spatial Locality

 

3. Cache Miss 발생원인 (3C's models)

1) Compulsory miss (Cold miss)

처음에 캐시에 데이터를 올리기 위해 발생하는 강제 미스

--> 대책 : prefetch, block size 늘리기

2) Capacity miss

캐시의 용량이 부족해서 발생하는 미스

--> 대책 : cache의 크기를 키우기, working set의 크기를 줄이기

cf : capacity miss를 측정하기 위해서는 fully associative cache를 사용해야한다.
conflict miss때문에 자리를 배정받지 못하는 block이 생기면 안되기 때문이다.

 

3) Conflict miss (Collision miss, Interference miss)

서로 다른 block이 cache의 동일한 자리에 들어가고자 해서 발생하는 미스.

set의 way가 부족해서 발생하는 미스라고도 할 수 있고,

associativity의 부족으로 인한 미스라고도 한다.

따라서 각 block이 모든 공간에 들어갈 자격을 갖는 fully associative cache에서는 발생하지 않는다.

--> 대책 : associativity를 늘린다.

 

4. CPU 칩에 들어가는 Cache의 모습

L1, L2 캐시가 cpu chip 내에 들어간다.

1) L1 : processor와 가장 가까운 캐시. 속도를 위해 I$, D$로 나뉜다.

- Instruction Cache(I$) :  메모리의 text 영역 데이터를 저장하는 캐시 - 보통 spatial locality가 좋다.

- Data Cache(D$) : text 영역을 제외한 모든 데이터를 다루는 캐시 - 보통 temporal locality가 좋다.

cf) memory = stack + heap + data + code(text)

2) L2 : 용량이 큰 캐시. 크기를 위해 나누지 않는다.

cf) L3 : 멀티 코어 시스템에서 여러 코어가 공유하는 캐시

 

5. Cache Metrics

- Hit Time : 캐시 히트여서, cpu에서 요청한 데이터를 캐시에서 가져올 때 소요되는 시간(cycles)

- Miss Penalty : 캐시 미스여서, 메모리에서 데이터를 가져올 때 소요되는 시간(cycles)

- AMAT(Average Memory Access Time) : Hit Time + Miss rate x Miss Penalty

-> Miss rate = Cache misses / Cache accesses

Q. cpu with 1ns clock, hit time = 1 cycle, miss penalty = 20 cycles, I$ miss rate = 5%일때
AMAT은?

A. 1ns clock => 1ns에 1 cycle
AMAT : 1 cycle + 0.05 * 20cycles = 2cycles이므로 2ns!!

 

.. 캐시의 크기를 줄이면 hit time 감소, 늘리면 miss rate이 감소 

 

 

6. Cache의 구조

캐시는 SRAM, 하드웨어로 구현한 해시 테이블.

캐시의 단위는 Block으로, 보통 64Bytes (memory에서 cache로 가져오는 단위도 Block)

 

*32bits address space / cache 4KB / block 4bytes / direct mapped cache 기준

1) 캐시에 접근하려는 주소

tag (20bits)

idx (10bits)

byte offset (2bits)

- idx는 block 개수가 결정한다.

cache 전체 크기가 4KB, block 1개 크기가 4bytes 이므로 block 개수는 2^10개이다.

각 block들을 구분하기 위해 idx가 10bits가 된다.

(주소의 idx 10bits를 보고 cache의 몇번째 block에 원하는 data가 있을지 찾아간다.)

- offset은 block 크기가 결정한다.

cache가 큰 덩어리인 4bytes block으로 이루어져있더라도, byte단위로 접근해야한다.

지금은 block 1개에 4개의 byte가 있으므로 각 byte를 구분해주기 위해 2bits를 사용하게 된다. 

(주소의 byte offset 2bits를 보고 cache block의 몇번째 byte에 접근할지 결정하게 된다.)

 

 

 

2) 캐시의 내부 구조

valid bit

tag (20bits)

data (32bits)

 

7. Cache 관련 정책들

7-1) cache -> memory 로 write할때 (Cache write policy)

.. cache는 임시 메모리 저장소이므로 프로세서가 캐시에 데이터를 write하면 진짜 메모리 저장소에도 반영해주는 작업이 필요하다.

여기서 캐시의 write 정책이 필요하다. 2가지가 있는데, write-through와 write-back이다.

1) write-through

캐시에 데이터를 write할때, 메모리에도 곧바로 write하여 반영해준다.

 

장점)

  - 캐시 일관성를 유지할 수 있다

  - cache entry 방출이 simple

  - miss났을 때 메모리에 write할 필요가 없으니 simple & cheaper

  - 구현이 쉽다

  - next level 메모리에 대한 bandwidth 사용이 크다

단점)

  - 처리속도가 느려진다.

그래서 write buffer(물리적인 메모리 구조, FIFO)를 함께 사용한다.

데이터를 write buffer에 써놓으면 캐시는 재사용이 가능해진다.

2) write-back(lazy-write)

캐시에 데이터를 write해도 곧바로 반영하지 않고, 블록이 쫒겨날 때 메모리에 write한다.

블록이 재사용될 때마다 dirty bit를 설정해서 표시한다.

 

장점)

  - hit일때 처리속도가 write-through보다 빠르다

  - 한 block내의 multiple write은 write back을 한번만 해도 된다

단점)

  - 구현이 어렵다

  - 캐시 일관성 유지가 어렵다. (inconsistent)

 

 

7-2) cache miss 발생시 (Write miss policy)

.. cache에 write 하려고 했는데 원하는 주소가 없을 때

1) Allocate

원하는 주소를 memory에서 cache로 가져와 allocate, 즉 할당 후 cache에 write한다.

2) No-allocate

cache를 업데이트 하지 않고 그냥 memory에 직접 가서 쓴다.

 

8. Main Memory Supporting Caches

ex 상황)
1 bus cycle for address transfer
15 bus cycles per DRAM access
1 bus cycle per data transfer
Block size = 4 bytes = 1 word

1) 1 word wide memory organization

memory에서 한번에 1 word씩 읽고, 1 word씩(block size만큼씩) 캐시로 보낸다.

▶ miss penalty =
1 bus cycle(address transfer) + 
15 bus cycles(per DRAM access) x 4(1 word씩 4번해서 4word) +
1 bus cycle(data transfer) x 4(1 word씩 4번해서 4word) = 
65 bus cycles
▶ bandwidth = 16bytes / 65cycles = 0.25 B/cycle

2) wider memory organization

memory에서 한번에 4 word씩 읽고, 4word씩 캐시로 보낸다.

▶ miss penalty =
1 bus cycle(address transfer) + 
15 bus cycles(per DRAM access) +
1 bus cycle(data transfer) = 
17 bus cycles
▶ bandwidth = 16bytes / 17cycles = 0.94 B/cycle

3) interleaved memory organization

2)의 memory를 4등분하여 병렬적으로 1 word씩 총 4 word를 읽고, 순차적으로 1 word씩 캐시로 보낸다.

▶ miss penalty =
1 bus cycle(address transfer) + 
15 bus cycles(per DRAM access) +
1 bus cycle(data transfer) x 4(1 word씩 4번해서 4word) = 
20 cycles
▶ bandwidth = 16bytes / 20cycles = 0.8 B/cycle