Post

13. Cache (1)

Posted
By Mingyu An
10 min read
13. Cache (1)

Ideal Memory

  • Each program sees a contiguous 4GB memory → Virtual memory
  • We can access anywhere in memory in 1 cycle. → Cache

But…

  • Cannot afford 4GB for printf program…
  • machine are multi-tasked

Law of storage

  • SRAM (on-chip)
  • DRAM (off-chip)
  • Flash memory
  • Hard disk

Bigger is slower, faster is more expensive.

Locality

Temporal Locality

무언갈 했다면, 해당 명령어나 데이터는 조만간 쓰일 확률이 높다.

Spatial Locality

무언갈 했다면, 그 근처에 있는 (비슷한, 연계된) 것을 할 확률이 높다.

ex) insturction memory reference, array/data structure

Coro. Locality exists, but might change over time.

Memoization

locality 덕분에 re-computation없이 최근 값들을 조금만 저장함으로써 효과적으로 쓸 수 있다.

Cost Amortization

“그래도 오버헤드 증가하는거 아냐?”

계산이 오래걸려도, overhead가 커도 아끼는 사이클이 많아지면 이득이다!

Total cost = overhead + per-unit cost * N

Avg. cost = (Overhead/N) + per-unit cost

→ 메모리는 엄청 느리니까 N이 충분히 크다.

Memory Hierarchy

Regiester file → L1 cache (~32KB)→ L2 cache (512KB) → L3 cache (banking) → Main memory (DRAM) → Swap Disk (-10ms 단위.)

Performance Analysis

i-level에서의 탐색 시간을 $t_i$라 하자.

각 캐시의 miss rate와 hit rate를 각각 $m_i , h_i$라 하면

(perceived access time) $T_i = t_i + m_i T_{i-1}$이다.

m_i*T_i-1이 miss penalty이다.

그러면 어떻게 해야하는가.

(1) miss rate를 낮게 한다.

  • 단순히 C (capacity)를 늘리면 m은 줄겠지만 t가 늘어남.
  • Replacement, Prefetching을 좀 더 똑똑하게 한다.

(2) Time을 줄인다.

  • Lower hierarchy의 유닛을 빠르게 한다. 다만 이러면 비싸진다.
  • 중간의 계층 구조를 갖는 메모리를 추가로 넣는다.
  • cache는 이미 충분히 작고, 작은걸 넣으면 Miss rate가 증가함.

Calculate T1, T2…

  • 90nm P4, 3.6 GHz
  • L1 D-cache
    • C1 = 16KB
    • t1 = 4 cycle + 9 cycle fp
  • L2 D-cache
    • C2 = 1024KB
    • t2 = 18 cycle + 18 cycle
  • DRAM
    • t3 = ~50ns

→ 결론은 L1을 잘 맞추는게 중요하다!.

Why is DRAM slow?

SRAM

  • 강한 Vdd와 GND가 걸려있음.
  • 흔들리지 않고 안정적.
    • 그냥 row select로 하면 느림
    • bit-differential sensing

Read 과정: bitline, ~bitline을 1로 세게 precharging. 이후 시간이 지나면서 1이었던 곳은 유지되나, 0이었던 곳은 서서히 떨어진다. 이때 이 차이를 감지하는 하나의 큰 인버터(bit differential sensing)가 있어서 이를 감지하고 inverter로 증폭한다. ⇒ FF에 저장한다.

Why Precharge?

그냥 row select에 0을 넣어서 읽으면, 0이면 0 유지하나, 1이면 큰 금속 막대의 전압을 아주 조금 올릴 것이다. (어렵고 오래걸림).

DRAM

싸게 하려고 하나의 bitline.

  • write는 쉽게, wordline 켜고 bitline에 원하는 값을 인가하면 된다.

다만, 캐퍼시터라 1을 저장한경우 점점점 0으로 방전된다. DRAM 셀마다 정해져있는, 데이터를 유지할 수 있는 시간이 있고 그 시간이 지나기전에 값을 다시 한번 읽어서 write해줘야 한다. → DRAM은 refresh가 필요한다.

1 → 0.6 → 1 → 0.6… → (너무 느려) → 0.3 → 0 (wrong)

  • Read는, 0.5정도로 bitline을 precharge를 함. 이러면 1이었다면 조금 오를 것이고 0이었다면 조금 떨어질 것이다. bitline이 drop하는 것을 sensing한다.

Cache Design!

자주 쓰는걸 기억하는 SRAM 메모리.

(사실 1-cycle만에 못읽어옴. 즉, valid/ready 신호가 필요할 수 있음)

  1. address
  2. Cache lookup
  3. Hit?
    1. if hit, return data!
    2. if miss… 😟 go to 4
  4. Choose location. (해당 자리가 비어있나?)
  5. 비어있지 않다면 다시 그 친구를 메모리 아래로 빼야함
  6. 비어있거나, 빼는거 끝냈으면 메모리 fetch. 후 해당 자리에 쓰기
  7. 데이터 return

Basic Cache Parameter

M: size of the address space in bytes. (2^32 등)

G: 한번에 가져올 때 4바이트? 8바이트? → 랩은 4바이트.

C: 캐시 용량. 캐시에 저장될 수 있는 데이터의 크기

캐시용량을 키우면 hit rate는 증가한다. 다만 인컴상 스피드 마냥 증가한다.

당분간 많이 쓸 메모리의 조합 크기를 working set이라고 하는데, 이 working set size보다는 커야, cache miss가 최소화되고 성능이 좋아진다.

Direct-mapped Cache

마지막 일부 비트는 하나의 cache line에서 몇번째 block이 선택될지에 대해 남겨두고 앞에 비트에 따라 index를 결정하는 방식.

각 줄에는 하나의 word만 매핑된다.

Tag Bank가 (tag bit + 1)*line 수만큼 필요하다.

→ 32비트 CPU에 4 word씩만 각 라인에 저장하면 tag가 추가로 들기 떄문에 overhead가 발생한다.

⇒ Multiple G-byte words share a common tag!

각 캐시 라인을 block size로 바꾼다. block size로 각 라인의 크기가 결정된다.

여러개의 주소가 하나의 tag entry에 매핑된다.

그럼 block size를 무한정 늘리면 되는거 아냐?

(1) Cache collision 증가

같은 index에 매핑되는 주소가 많아짐. collision 발생하면 eviction해야함

(2) 불필요한 데이터 낭비

꼭 같이 있다고 모두 다 필요한건 아님. 불필요한 데이터 낭비

(3) miss penalty 증가

다시 DRAM에서 cache line을 모두 가져와야하는데 그만큼 시간이 더 듦

(3)을 어떻게 해결할 것인가

  1. critical word first reload

일단 요청한거 먼저 주고! 그 다음에 나머지를 말아서준다.

  1. sub-blocking reload

각 sub-block별로 valid bit

요청된 sub-block만 reload하기

bo를 MSB로 쓰면 안되는 이유

spatial locality를 챙길 수 없어진다.

a-way Set-Associative Cache

a개의 bank를 나누어 각각 cache를 관리한다.

block을 여러개로 나눈다. 하나의 set에는 C/a/B개의 라인이 있다.

즉, 하나의 주소가 갈 수 있는 곳은, direct-mapped에서는 1개 였지만, set-associative에서는 a개가 있는 것이다. 그 a개중 아무데나 들어갈 수 있다. (invalid한 곳이 있으면 싸악 들어감)

set에는 C/a/B line.→ C만큼이 있고 라인별 용량이 B임.

근데 그게 a개로 나눠져 있음.

index는 그만큼 줄어듦. 여러 주소가 더 같은 Index로 매핑되지만, 갈 수 있는 곳이 a개 이기 때문에 cache collision으로 인한 eviction overhead가 적다.

Fully Associative Cache

아예 모든 cache line에 들어갈 수 있음.

tag를 동시에 비교해서 같으면 바로 읽어와야함.

index bit = 0

bo (+g) = C / B

⇒ CAM이 이렇게 동작.

a가 이렇게 늘어나면 hit rate는 늘어나지만… 더 늘리면 늘릴수록 읽는 속도가 느려지고, 전력 소모가 많아지며 너무 비싸고 어렵다.

Lecture Notes, Computer Architecture
micro-architecture cache
This post is licensed under CC BY 4.0 by the author.