[Computer Architecture] Memory

"Memory"

[Memory]

▣ Ideal Computer Architecture

· 이상적인 구조는 Processor가 Stall 없이 계속해서 명령어와 데이터를 공급 받아 쉬지 않고 동작

> Ideal Processor
  · No Pipeline Stalls

    → Perfect Data Flow(No Data Hazards)

    → Perfect Control Flow(No Control Hazards)

  · No Execution Latency

> Ideal Memory

  · No Access Latency (Fast)

  · Infinite Capacity (Large)

  · Infinite Bandwidth (Unlimited Accesses per Cycle)

  · No Silicon Costs (Cheap)

> Real-World Memory Problem

· 용량이 큰 Memory는 속도↓
· 속도가 빠른 Memory는 용량↓

· 높은 대역폭을 구현하려면 비용↑

▣ Locality

> Temporal Locality (a[i + 1] → i++ → a[i])

· 한 번 사용한 데이터가 가까운 미래에 다시 사용될 가능성↑

> Spatial Locality (a[i], a[i + 1])

· 어떤 데이터를 사용하면 그 주변 데이터도 곧 사용할 가능성↑

▣ Memory Hierarchy

· 위로 갈수록 빠르고 작고 비싸며, 아래로 갈수록 느리지만 크고 저렴한 Memory 계층 구조 사용

→ 자주 쓰는 데이터는 빠르고 작은 Memory에 두고, 덜 자주 쓰는 데이터는 크고 느린 Memory에 두고 사용

> Multi-Level Memory Hierarchy

· Upper-Level Memory : Processor와 가까이 붙어 있으며, 용량은 작지만 빠른 데이터 접근 제공

· Lower-Level Memory : 대용량 저장이 가능하지만 속도↓

· Block 또는 Line : 메모리 계층 간에 한 번에 전송되는 데이터의 최소 단위

· 동작 방식 : Processor가 자주 찾는 데이터 Block을 하위 계층에서 상위 계층으로 복사 → Processor의 접근 시간↓

[Cache]

· Cache : 보통 SRAM으로 만든 작고 빠른 Memory로 CPU 가까이에 위치하며 자주 사용하는 데이터 Block을 저장

▣ Cache Access (Hit or Miss)

· Cache Hit : Processor가 요청한 Memory 주소의 데이터 Block이 이미 Cache 내에 존재 → 빠르게 데이터 Load

· Cache Miss : Processor가 요청한 데이터가 Cache에 없는 상태 → 하위 계층의 느린 Memory로부터 해당 Block Load

▣ Cache Performance

· Hit Rate : 전체 Cache 접근 중 Hit가 발생한 비율

· Miss Rate : 전체 Cache 접근 중 Miss가 발생한 비율

· Hit Time : Cache에 데이터가 있을 때 접근하는 데 걸리는 시간

· Miss Penalty : Miss가 발생했을 때 Lower-Level Memory에서 Block을 가져오는 데 추가로 걸리는 시간

[Direct-Mapped Cache]

▣ Tag & Valid Bit

· 같은 Cache Index에 여러 Memory Block이 Mapping될 수 있기 때문에, Index만 보고는 요청한 데이터인지 확인 불가

· Tag : Cache Entry에 들어 있는 데이터가 정확히 어느 Memory Block에서 온 것인지 구분하는 정보

    → Cache Hit 조건 : 해당 Entry가 유효 & 저장된 Tag = 요청한 주소의 Tag

· Valid Bit : 해당 Cache Entry가 실제로 의미 있는 데이터를 담고 있는지 표시(유효한 데이터 = 1)

▣ Direct-Mapped Cache

Cache_Index = Block_Address % Num_Cache_Entries

· 각 Memory Block은 Cache 안의 정확히 한 위치에만 할당 가능

    (Ex. Block Address = {1, 9, 17, 25} & Cache Entry = 8 → 동일한 Cache Index)

    → 5-bit Address 중 아래 3-bit가 Index로 사용되고, 위 2-bit가 Tag로 사용됨

∴ Direct-Mapped Cache : 단순하고 빠르지만 충돌 발생 가능성↑

> Direct-Mapped Cache Access Example

· 22(10110) : Tag = 10, Index = 110 → Miss → Memory[22] 저장

· 26(11010) : Tag = 11, Index = 010 → Miss → Memory[26] 저장

· 22(10110) : Index 110에 Tag 10 존재 → Hit

· 18(10010) : Tag = 10, Index = 010 → 기존 Memory[26]과 Index 충돌 → Miss → Memory[18]로 교체

· 30(11110) : Tag = 11, Index = 110 → 기존 Memory[22]와 Index 충돌 → Miss → Memory[30]로 교체

→ Hit Rate = 1/5

> Direct-Mapped Cache Architecture

· Cache Entry가 1024개 → Index = 10-bit

· Block Size = 8-Byte → Block Offset = 3-bit

▣ Cache 전체 Bit 수 계산

** Cache 크기를 말할 때는 보통 Data 저장 공간만 계산, But, 실제 HW는 Data뿐 아니라 Tag & Valid Bit 필요

· Memory 주소 : 64-bit

· Cache Block 개수 : 2ⁿ (n-bit Index)

· Cache Block 하나의 크기 : 2^m x 8-Byte(Double Words) = 2^{(m + 3)}-Byte

· Tag Bit Length : 64 - (n + m + 3)

→ Total Bit = 2ⁿ x (Data Bit per Block + Tag Bit + Valid Bit)

                     = 2ⁿ x [2^m x 64 + {64 - (n + m + 3)} + 1]

→ 순수 데이터 저장 용량 = 2ⁿ x 2^{(m + 3)}-Byte

Ex) Direct-Mapped Cache = 16KB(= 2¹⁴-bit), Cache Block = 8 Double Words(= 64-Byte =  2⁶-bit)

· Cache Block 개수 = 2¹⁴ / 2⁶ = 2⁸ = 256개

· Tag Bit = Memory Address - Index Bit - Block Offset = 64 - 8 - 6 = 50-bit

· Total Bit = 2⁸ x [2³ x 64 + {64 - (8 + 3 + 3)} + 1] = 256 x 563 = 144,128-bit ≒ 17.6KB

▣ Mapping A Memory Address to A Cache Block

· 64개 Block을 가진 Direct-Mapped Cache 존재(Block Size = 16-Byte) → Memory 주소 1,210은 어느 Cache Line?

· Block Address = [Byte Address / Bytes per Block] = [1,210 / 16] = 75

    → Memory 주소 1,210은 Memory Block 75에 속함

    → Memory Block 75는 Memory 주소 1,200 ~ 1,215 포함

· Cache Index = Block Address % # of Cache Blocks = 75 % 64 = 11

[Cache Write]

▣ Data Consistency

· 위 내용까지는 Load 과정으로 Load 명령어의 결과를 바로 다음 명령어가 사용하면 Pipeline이 Stall되므로 성능 매우 중요

· 지금부터는 Store 과정으로 Store 명령어는 Load 명령어보다 성능 상 덜 급할 수 있지만, 일관성 문제 발생

▣ Write-Through Cache

· Store가 발생할 때마다 데이터를 Cache에도 Write, Lower-Level Memory에도 Write

△ 항상 Cache와 Main Memory가 최신 상태로 일치하므로 일관성이 완벽히 유지

▼ Main Memory는 속도가 아주 느리기 때문에, Write할 때마다 Processor가 느린 Memory 속도에 맞춰서 성능↓

Ex) CPI = 1, Cache Hit Rate = 100%, 10% Store, Store 하나가 Memory에 Write하는 데 100 Cycle 소요

· CPI = 1 + 0.1 x 100 = 11 (성능 저하)

▣ Write Buffer

· Store 데이터를 바로 Main Memory에 Write하지 않고, Write Buffer에 먼저 저장

△ CPU는 Buffer에 넣고 다음 일을 계속 수행 가능 & Main Memory는 나중에 Buffer에 쌓인 Write 처리

▼ Store가 너무 자주 발생해서 Buffer가 꽉 차면 CPU는 다시 Stall

▼ Memory Traffic↑

▣ Write-Back Cache

· Write-Through Cache의 대안으로, Store가 발생해도 일단 Cache에만 Write하고 Main Memory에는 바로 Write X

· Cache Block이 나중에 교체될 때, 해당 Block이 수정된 상태라면 Main Memory에 Write (수정된 Block = Dirty Block)

△ Store마다 Main Memory에 Write하지 않아도 되므로 성능↑

▼ Dirty Block이 Cache에서 쫓겨날 때 Memory에 반영하지 않으면 수정된 데이터가 사라짐

** Write-Back Cache에는 Dirty Bit 필요

** Dirty Block을 Main Memory에 Write하는 동안 Delay를 줄이기 위해 Write Buffer도 여전히 필요

[Cache Miss]

▣ Cache Miss 발생 조건

· Valid Bit = 0 : 해당 Entry가 비어 있거나 아직 유효한 데이터를 담고 있지 않은 경우

· Tag 불일치 : Index는 같지만 원하는 Memory Block이 아닌 경우

→ Cache Miss 발생 시 Lower-Level Memory에 요청해서 필요한 Block을 Load(Pipeline Stall 유발, Program 실행 시간↑)

▣ Cache Miss 종류에 따른 정지 상태

· Instruction Cache Miss : PC가 가리키는 Instruction을 가져올 때까지 Instruction Fetch가 멈춤

· Data Cache Miss : 필요한 Data Block이 Data Cache에 들어올 때까지 이후 Pipeline 명령어들이 Stall

▣ Processor Execution Time

· Total Execution Time = (Pipeline Execution Cycles + Memory Stall Cycles) x (Clock Period)

· Memory Stall Cycles = (Read Stall Cycles) + (Write Stall Cycles)

· Read Stall Cycles = (# of Reads) x (Read Miss Rate) x (Read Miss Penalty)

· Write Stall Cycles = (# of Writes) x (Write Miss Rate) x (Write Miss Penalty) + Write Buffer Stalls

> Memory Stall Cycles

· Write Buffer Stall : Write Buffer가 가득 차면 CPU는 더 이상 Store를 넘기지 못하고 대기 → 드문 Case이므로 무시

∴ Memory Stall Cycles = (# of Memory Accesses) x (Miss Rate) x (Miss Penalty)

▣ Cache Performance Evaluation

· Instruction Cache Miss Rate = 2%

· Data Cache Miss Rate = 4%

· Memory Stall이 없을 때 CPI = 2

· Miss Penalty = 100 Cycles

· Load/Store 명령어 비율 = 전체 명령어의 36%

** Instruction Fetch : 모든 명령어마다 1번 발생 / Data Cache Access : Load/Store 명령어에서만 발생

※ i : 전체 명령어 수

· Memory Stall이 없을 때 기본 실행 Cycle = 2i

· Instruction Cache Miss Stall = i x 0.02 x 100 = 2i

· Data Cache Miss Stall = i x 0.36 x 0.04 x 100 = 1.44i

→ 전체 Cycle = 2i + 2i + 1.44i = 5.44i

∴ CPI = 5.44i / i = 5.44 → 기본 CPI = 2이므로 실행 시간은 2.72배 느려짐

▣ Processor Speedup 한계

· Execution Time = 5.44i / f(= Clock Rate)이므로 Processor가 2배 빨라지면 기본 연산과 Cache Hit는 더 빨라짐

· But, Off-Chip Memory(Main Memory)는 여전히 느린 속도

    → 기존 Miss Penalty = 100 Cycles ▶ 새로운 Miss Penalty = 200 Cycles

∴ 새로운 전체 Cycle = (기본 CPI) + (Instruction Miss Stall) + (Data Miss Stall)

                                    = 2i + (0.02 x 200 x i) + (0.36 x 0.04 x 200 x i) = 8.88i

· Execution Time = 8.88i / 2f = 4.44i / f → 실제 Runtime 감소 = (5.44 - 4.44) / 5.44 ≒ 18%

→ Memory 병목 때문에 성능 2배 향상 X

▣ AMAT(Average Memory Access Time)

· AMAT = (Hit Time) + (Miss Rate) x (Miss Penalty)

  (Ex. Cache Access = 1 Cycle, Miss Penalty = 20 Cycles, Miss Rate = 5% → AMAT = 1 + 0.05 x 20 = 2 Cycles)

> Multi-Level Cache 사용으로 AMAT↓

 - Single-Level Cache

· L1 Cache Hit Time = 1 Cycle

· L1 Miss Rate = 2%

· L1 Miss 발생 시 Off-Chip Memory(Main Memory) 접근

· Main Memory Miss Penalty = 400 Cycles

→ AMAT = 1 + 0.02 x 400 = 9 Cycles

 - Multi-Level Cache

· L2 Cache Access Time = 20 Cycles

· L2 Miss Rate = 25%

· L2 Miss 발생 시 Off-Chip Memory(Main Memory) 접근

· Main Memory Miss Penalty = 400 Cycles

→ AMAT = 1 + 0.02 x (20 + 0.25 x 400) = 1 + 0.02 x 120 = 3.4 Cycles

** L1 Cache에서 Miss가 발생해도 바로 Main Memory로 접근하지 않고, 중간에 L2 Cache에 접근하여 접근 시간 감소

[Cache Miss]

▣ Cache Miss Type

> Compulsory Miss

· 처음 접근하는 Block에서 발생

· 한번도 Cache에 들어온 적이 없으므로 피하기 어렵지만, Pre-Fetching으로 감소 가능

> Capacity Miss

· Cache 용량이 부족해서 발생

· 필요한 Working Set이 Cache보다 크면 이전 Block들이 쫓겨나고, 나중에 다시 접근할 때 Miss 발생

· Cache 크기를 키우면 감소 가능

> Conflict Miss

· Cache에 빈 공간이 있어도 특정 Block들이 같은 위치에만 Mapping되어 서로 밀어내어 발생

· Direct-Mapped Cache에서 자주 발생

▣ Reducing Conflict Miss

<112(= 01110000) & 176(= 10110000)>

· 8-bit 주소 {2-bit(Tag) + 3-bit(Cache Entry Index) + 3-bit(Block Offset)}

· 112의 Block Offset = 000 / 176의 Block Offset = 000

· 112의 Cache Index = 110 / 176의 Cache Index = 110

· 112의 Tag = 01 / 176의 Tag = 10

→ 두 주소 모두 Index가 110으로 똑같지만 Tag는 서로 달라서 계속 밀어내는 Conflict Miss 발생

[Set-Associative Cache]

▣ n-Way Set-Associative Cache

<2-Way Set-Associative Cache>

· 하나의 Set 안에 n개의 Block을 저장 가능

· Set Index = (Block Address) % (Number of Sets)

· 주소 112와 176이 같은 Set Index에 Mapping되더라도, Direct-Mapped와 달리 하나는 Way 0, 다른 하나는 Way 1에 저장 가능

→ Conflict Miss↓

> Option

· Direct-Mapped : Index가 가리키는 위치가 단 하나뿐이므로 별도의 탐색 회로 필요 없이 하나의 Tag만 비교해서 일치하는지 확인

· n-Way Set-Associative : Index를 통해 특정 Set를 찾은 후, 해당 Set 안에 있는 n개를 동시에 조사

· Fully-Associative : Set 구분이 없어 전체가 하나의 거대한 Set → Index 연산 없이 모든 Entry 동시 확인

> 4-Way Set-Associative Cache Architecture

· 256개의 Set → Index = 8-bit

· Block Size = 8-Byte → Offset = 3-bit

· Tag = 64 - (8 + 3) = 53-bit

▣ Tag Overhead

> Direct-Mapped Cache

· Cache Block 수 = 4,096 Blocks = 2¹² Blocks → Index = 12-bit
· Block Size = 2 Doublewords = 16-Byte → Block Offset = 4-bit

· 주소 길이 = 32-bit

→ Tag = 32 - (12 + 4) = 16-bit

∴ Total Tag Bit = 16 x 4,096 = 65,536-bit

> 2-Way Set-Associative Cache

· Set 수 = 4,096 Blocks / 2 Ways = 2,048 Sets =  2¹¹ Sets → Index = 11-bit

· Block Size = 2 Doublewords = 16-Byte → Block Offset = 4-bit

· 주소 길이 = 32-bit

→ Tag = 32 - (11 + 4) = 17-bit

∴ Total Tag Bit = 17 x 2 x 2,048 = 69,632-bit

> 4-Way Set-Associative Cache

· Set 수 = 4,096 Blocks / 4 Ways = 1,024 Sets =  2¹⁰ Sets → Index = 10-bit

· Block Size = 2 Doublewords = 16-Byte → Block Offset = 4-bit

· 주소 길이 = 32-bit

→ Tag = 32 - (10 + 4) = 18-bit

∴ Total Tag Bit = 18 x 4 x 1,024 = 73,728-bit

> Fully-Associative Cache

· Set = 1개 → Index X

· Block Size = 2 Doublewords = 16-Byte → Block Offset = 4-bit

· 주소 길이 = 32-bit

→ Tag = 32 - (0 + 4) = 28-bit

∴ Total Tag Bit = 28 x 4,096 = 114,688-bit

** Associativity↑ ▶ Index Bit↓ & Tag Bit↑ ▶ Conflict Miss↓ & Tag Overhead↑

▣ Cache Block Replacement

· Set-Associative Cache에서 어떤 Set의 모든 Way가 이미 차 있는데 새 Block을 넣어야 하면, 기존 Block 하나를 내보내야 함

> LRU(Least Recently Used)

· 가장 오랫동안 사용되지 않은 Block을 교체

△ 대부분의 Program은 Temporal Locality가 존재하여 LRU가 잘 작동

▼ Working Set이 Cache보다 조금 큰 순환 접근 Pattern에서는 LRU 최악

▣ Cache-Aware Matrix Multiplication

<C[i][j] = A[i][k] x B[k][j]>

· A의 한 행 Read : 메모리 상 연속된 원소들을 Read → Spatial Locality 좋음

· B의 한 열 Read : 불연속적인 서로 다른 Cache Block에 접근 → Spatial Locality 나쁨

> Tiled Matrix Multiplication(= Blocking)

<Blocking Factor f = 4>

· 전체 행과 전체 열을 한 번에 처리하지 않고, 작은 Block 단위로 나누어 계산

· A, B, C의 작은 부분 행렬을 Cache에 올려놓고 여러 번 재사용 가능

△ Spatial Locality : Cache Block 안의 여러 원소를 사용

△ Temporal Locality : 한 번 Cache에 올라온 Block을 여러 계산에 반복 사용

[Reference]

· 5_memory (Computer Architecture) - William J. Song