13. Memory Hierarchy

Memory Hierarchy

The Law of Storage

1. Bigger capacity → Higher latency (걸리는 시간: SRAM < DRAM < SSD)
2. Faster 비싸진다 (SRAM > DRAM > SSD)

Basic Principles

Locality

• 프로그램에서 어떤 address에 있는 data와 instruction을 사용했으면 조만간 비슷한 곳에서 사용할 가능성이 높다
• Temporal Locality: 최근에 reference했으면 또 사용할 가능성이높다. (ex. loop)
• Spatial Locality: 근처 주소에 있는 것을 또 reference할 가능성이 높다

Cost amortization

DRAM에 한 번 access해서 데이터를 가져온 다음에 cache에 저장을 하면 된다.

One-time-overhead = DRAM access 시간

Per-unit-cost = cache access 시간

Cache

Access time이 상대적으로 짧은 컴퓨터 메모리로, 최근에 사용했거나 자주 사용한 instruction/data 등을 저장해놓는 것이다.

Memory Hierarchy

자동으로 관리할 수도 있고, 수동으로 관리할 수도 있다. GPU, special-purpose processor 등에서는 수동으로 관리하기도 하지만 너무 번거로워서 잘 하지 않음.

Register file → L1 cache → L2 cache → L3 cache → Main memory(DRAM) → Hard disk/SSD

• Register spilling: Register file은 CPU 안에 있어서 매우 빠르다. 만약 필요한 variable이 register보다 많은 경우, 컴파일러가 일부분을 L1 cache로 “spill”한다. 이는 하드웨어가 아닌 compiled code에 의해서 관리된다.
• Automatic cache management: L1, L2, L3 cache 사이에 움직이는 것은 하드웨어가 처리한다.
• Automatic demand paging: 만약 프로그램이 DRAM에 없는 메모리를 access하려고 할 경우 paging이 일어난다. OS가 자동으로 필요한 page를 memory로 로딩한다.

Memory Hierarchy with a 5-stage pipeline

• L1 cache에 대해서는 I-cache랑 D-cache를 분리

• L2, L3, DRAM에 대해서는 unified 형태

cf. Cache Hierachy: CPU에 가까울수록 high (ex. L1 cache)

SRAM/DRAM:

SRAM (static random access memory)- 접근 속도가

Hierarchical Performance Analysis

각 memory hierarchy level에서의 access time이 t_i이라고 하자.

Ti=hi⋅ti+mi⋅(ti+Ti+1)

• hi: hit rate, 이 때 access time: ti
• mi: miss rate, 이 때 access time: ti+Ti+1

Cache as Request Filter

BR: Bandwidth requested

BP: Bandwidth provided

각각의 cache level을 일종의 필터처럼 생각할 수가 있다.

Hierarchy Design Considerations

1. DRAM (Dynamic RAM)

• used for large memory
• optimized for Capacity/$

1. SRAM (Static RAM)

• Static RAM, cache나 register file에 사용된다.
• Capacity, latency, Capacity/$ 등 다양한 compromise를 고려
• Working set: 어떤 process에서 현재 사용하고 있는 데이터

Cache design basics

Cache interface

Basic operation: cache는 어떻게 작동하는가?

1. Address가 주어지면, cache에서 그 address를 찾는다
2. Hit → data를 리턴한다
3. Miss → Cache에 저장할 새로운 주소를 정한다
4. Update cache

Basic Cache Parameters

• M-bit address: Address space의 전체 크기 (ex. 4GB address space라면 32-bit)
• C (capacity): cache의 총 데이터 사이즈 (ex. 16KB = 2^16 bits)
• G = 2g (granularity): 한 번에 몇 byte를 가져올 것인가? (4 bytes per word)

Direct-mapped cache

• Tag bank: 주소 중에서 tag 비트를 저장한다.
• Data bank: 실제 데이터를 저장하는 역할 (각 줄당 G bytes)
• Valid bit: cache에 있는 데이터가 초기화된 상태인지 확인

m-bit의 주소를 다음과 같이 나눈다.

• idx: 특정 cache block 선택
• tag: cache hit인지 아닌지 확인
• bo (block offset): 만약 hit이라면, 해당 block 안에서 가져올 byte를 선택
• g: 요청한 byte 수 (ex. lw: 4byte)

Cache hit logic

1. Address에서 index를 확인해서 맞는 line을 찾는다.
2. address에 있는 tag와 tag bank에 있는 tag를 비교한다.
3. valid bit를 확인한다 (dirty, 즉 데이터가 초기화되지 않은 상태이면 안 되기 때문에)

→ 이 모든 게 다 맞으면 cache hit이다!

용어 정리를 하고 가자

• page: virtual memory system에 있는, 고정된 사이즈의 memory block.
• cache block/line: CPU가 cache하는 데이터의 단위.
• set: 같은 index를 가지는 cache block/line들의 모임.

Block size & Tag storage overhead

Block size가 작을 경우 tag space를 쓸데없이 낭비하게 된다.

Block size를 늘리면 어떻게 될까?

아래 그림의 cache 에서, 1 row = 1 cache block = 1 cache line

가로 길이가 block size, 세로 길이가 block의 개수라고 생각하면 된다.

오른쪽과 같이 block size를 늘리게 되면 한 번에 가져오는 data가 더 많아진다고 생각하면 됨.

따라서 tag가 전체 cache에서 차지하는 공간이 적어지게 된다.

• tag: 현재 cache에 있는 address
• idx: cache 안에서의 line number를 선택
• bo (block offset): block 안에서 단어를 선택
• g: granularity (byte offset inside word)

Block size and miss rate

block size를 늘릴 때의 장점 (Total capacity C가 고정되어 있을 때)

• Spatial locality가 올라감 (한 번에 multi-word block을 fetch한다는 거 자체가 주변 block까지 가져온다는 뜻이기 때문에)
• Miss penalty는 block당 발생하기 때문에 페널티가 줄어들게 됨
• tag overhead 감소

block size를 늘릴 때의 단점:

• capacity 낭비
• latency 증가 (아래 써있음)
• block수가 줄어들기 때문에 cache 내부에서 conflict가 발생할 가능성이 올라감

Block size and Ti+1 (total access time)

• block이 커지면 loading time도 늘어남 (예를 들어 block의 맨 끝에 있는 단어를 load해야 될 경우 그 block 전체가 loading 될 때까지 기다려야 함!)
• 이를 해결하기 위한 2가지 방법이 있음

Conflicts in direct-mapped cache

= direct-mapped cache에서는 필연적으로 conflict miss가 발생하게 된다!

다음과 같은 Direct mapped cache 그림을 다시 생각해 보자. address가 다르더라도 index가 같으면 같은 cache block으로 매핑되게 된다.

예를 들어, cache size C = 16KB = 2^14 B 이고 block size B = 64B 라고 생각해보면 index는 log_2^C/B = 256개가 된다. 따라서 256번째 memory block마다 collision이 일어난다.

Set-associative cache

📌 Key Point

• Direct-mapped cache는 하나의 index당 저장할 수 있는 위치가 하나만 존재해서 conflict가 일어나게 된다.
• 그렇다면 여러 개의 direct-mapped cache를 묶어서 쓰면 하나의 index가 여러 위치에 저장되어, collision을 최소화할 수 있지 않을까?

📌 기본적인 구조

• Cache를 ”set”으로 나눠서, 각각의 set는 a개의 cache line으로 구성되어 있다.
• 하나의 index가 하나의 set으로 매핑되는데, 각각의 set 안에서는 a개 중 어디에나 들어갈 수 있게 된다.
• set당 여러 개의 line으로 매핑된다

Field	Bits	Role
Tag	remaining bits	compared to identify the cache line(block)
Index	log₂(# sets)	selects the set
Offset	log₂(B)	selects byte within cache line(block)

Replacement policy for set-associative cache

LRU (Least Recently Used): 제일 나중에 쓰던 memory block부터 제거한다

Fully associative cache

Block 개수가 C/B개인 cache이다.

각 row마다 tag, valid bit, data가 존재한다.

주소가 주어지면 모든 block에서 tag를 비교해서, 맞으면 hit,

저 삼각형 모양들이 사실 하나의 큰 mux이며, C/B개의 cache line이 input이고 tag 일치 여부 && valid bit 이 control signal이다.

Fully associative cache의 특징

• C/B - way associative cache와 같다.
• CAM = Content-Addressable Memory이다.

시험 문제 풀이

ex. 2021 final 2-A, 2-B

Memory address: 16-bit = 2^16 Cache line size: 16 bytes = 2^4 Cache capacity: 64 bytes = 2^6 Set-associativity: 2

A. How many bits are required for a tag for a cache line in this cache?

sol) tag / idx / offset로 비트를 나눌 수 있다.

cache line이 16 bytes → offset = 4 bits

Cache size = # of sets * line size * associativity 에서

64 = ? * 16 * 2 , # of sets = 2

so, index: 1 bit

tag = 16-4-1 = 11 bits

offset: 32-11-1=20

B. What is the total storage overhead per cache line other than the tag bits?

Storage overhead: 전체 cache 안에서 tag bits가 차지하는 byte 수

valid bit 1 bit + dirty bit 1 bit + LRU bit 0.5 bit = 2.5bits

total 128 bits → 2.5/128

• Total cache size = C, block size = B, associativity = a
• Number of sets = C / (B × a)
• Tag, index, offset 계산:

ex. 2021 final 3-A

Page size: 4 KB = 2^12 B Cache capacity: 128 KB = 2^17 B Cache set-associativity: 4 Cache line size (= block size): 64 bytes = 2^6 B

1. How many copies of the same data can exist in the cache due to the synonym problem?

• Page offset = 12 bits
• cache size = block size * cache sets * set associativity
• block offset = 6 bits
• 따라서 cache lookup에 필요한 총 bit 수는 9(index)+6(offset) = 15 bits이다.
• 그러나 page offset은 12 bits이므로, 2^3 =8개의 synonym이 발생하게 된다.

14. Memory Hierarchy 2

Classification of cache misses

→ Cold, Capacity, Conflict miss!

1. Cold miss

• 어떤 address를 처음으로 access할 때 발생하는 miss
• 어쩔 수 없이 일어난다는 의미에서 compulsory miss라고도 부른다.
• Domination: Locality가 적을 때 (여기저기서 불규칙적으로 access할 때)

1. Capacity miss

• cache size가 data size보다 작을 때
• Domination: C (Cache capacity) < W (Working set size) 일 때 (Cache size가 작은 거)

1. Conflict miss

• Direct-mapped, set-associative cache에서 collision에 의해 miss가 날 때
• Domination: C (Cache size) ≈ W (Working set size)일 때, C/B (같은 건 아니지만 associativity)가 작을 때

Cache read/write (issues)

• Read access: tag, data bank에 동시에 접근
• Write access: tag bank에 먼저 접근하고, write-hit인 경우에만
• 문제: Partial-word write

Store buffer

• Tag bank → data bank 이렇게 순차적으로 접근하면 Store가 여러 cycle 걸리는데, 다음 instruction도 memory instruction이면 structural hazard 발생
• Store buffer:
• Memory forwarding: 같은 address에서 load했을 때 업데이트되기 전의 데이터를 보면 안 되기 때문에, store buffer를 먼저 확인하고 load해서 RAW correctness를 보장한다.

Blocking vs non-blocking cache

• Blocking cache: Cache miss가 발생했을 때 CPU가 완전히 stall
• Non-blocking cache: Cache miss가 발생해도 다른 instruction을 계속 실행.

MSHR (Miss Status Handling Register)

non-blocking cache에서 사용하는 방법

말 그대로 miss인 cache register를 트래킹하는 것을 의미한다.

각 MSHR의 구성은 다음과 같다.

• block address: 어느 cache line이 fetch되고 있는가?
• list of pending loads: dest register, format (byte/word, signed/unsigned), block offset

1. Cache miss 발생 → 새로운 MSHR를 할당 (primary miss), 다른 instruction들은 정상적으로 실행
2. 새로운 cache miss 발생
3. 더 이상 할당할 MSHR entry가 없을 경우 pipeline을 stall한다.

Write-hit / Write-miss policy

데이터를 memory에 store하려고 할 때, write할 주소가 이미 cache에 있으면 Write-hit, 없으면 Write-miss이다.

Write hit: write-back or write-through?

Write-back: Cache에만 쓰고 “Dirty” bit로 지정한 후, 나중에 write back을 한다.

• Dirty: cache에서는 update되었는데 main memory에서는 아직 update되지 않은 것을 의미.
• Dirty가 아니면 write-back을 할 필요가 없음
• L1 cache와 같이 낮은 hierarchy에서 필요한 bandwidth를 줄일 수 있다. (MB/s)

Write-through: Cache에도 쓰고, 아래 레벨에 있는 cache와 memory 등에 모두 쓴다. (ex. L1 cache에서 write hit이 발생했으면 L2, L3를 거쳐서 순차적으로 main memory까지 모두 update한다)

Write miss: write-alloc or write no-alloc?

Write-allocate: Block을 cache에 load한 후에 update한다.

• temporal locality를 활용할 수 있다. (근처에 있는 address를 load할 경우 미리 cache에 로딩을 해놨기 때문에)

Write no-allocate: Block을 cache가 아닌, lower-level memory에 직접 쓴다.

• store와 load 사이에 locality가 높지 않을 경우 굳이 그 데이터를 cache에다가 저장해놓을 필요가 없어서 효율적일 수 있다.

cf. C/B effect: Cache size/block size 의미로

Design tradeoffs

Hierarchy가 높을수록 (ex. L1 cache)

• C는 작아진다 (capacity): 안에 들어 있는 SRAM에 따라 access time이 결정되기 때문에 규모가 작아야 한다
• B는 작아진다 (block size): spatial locality, C/B (cache block)의 개수에 영향을 받음
• a: 적당히

Hierarchy가 낮을수록 (ex. LLC cache)

• C, B가 커진다

Inclusive vs Exclusive cache

LLC (last level cache)

Inclusive cache

• L1에 있는 block이라면 L2, L3에도 있다.
• 문제점: Back invalidation: LLC에서 evict되면 모든 다른 upper level cache에서도 evict 된다.

Exclusive cache

• 문제점: 예를 들어, L1에서 cache miss → LLC까지 cache miss가 났을 때, inclusive cache는 바로 DRAM access하면 되지만 Exclusive cache는 다른 L1도 확인해봐야 함.