Chapter 5. Large and Fast: Exploiting Memory Hierarchy

박병준·2022년 6월 4일

CS 컴퓨터 구조론

컴퓨터 구조론

목록 보기

5/5

5.1 Principle of Locality

Temporal Locality

한번 접근된 데이터은 다시 접근될 수 있다.

Spatial Locality

접근된 데이터 근처의 데이터도 접근 될 수 있다.

5.2 Memory Technology

메모리에는 ROM과 RAM이 있다.

ROM은 Read-Only Memory. 비휘발성 메모리. 기본적으로 읽기전용이지만, 다시 쓸 수도 있음.
RAM은 Random Access Memory. 휘발성 메모리.

DRAM Technology

capacitor(축전기. 콘덴서)의 충전으로써(flip-flop처럼) 데이터가 저장된다.

전하(the charge)에 access하기 위해 단일 트랜지스터(single transistor)가 사용된다.

주기적으로(periodically) 데이터를 다시 써줘야한다(refresh).

내용을 읽고 다시 씀(read and write back).
DRAM의 "row"에 수행(데이터를 쓰는 곳).

SRAM은 한 번 써두면 recharge할 필요가 없으나, DRAM은 주기적으로 recharge 필요함.

Advanced DRAM Organization

DRAM의 bit들은 직사각형의 배열(rectangular array. 2차원 배열)로서 편성된다.

Double Data Rate (DDR) DRAM

rising과 falling clock edge마다(두 곳) 데이터 교환(transfer)

Quad Data Rate (QDR) 혹은 DDR2 DRAM

기존의 DDR칩에 input과 output을 하나씩 더 추가해서, bandwith를 2배로 증가.

The Memory Wall

프로세서 vs DRAM(메모리)의 속도 차이는 계속해서 커지고 있다.

Increasing Memory Bandwidth

4-word wide memory (b. 중간의 형태. wider memory organization)

긴 word를 다루니까, 메모리에도 긴 word단위로 접근, 데이터 교환도 긴 word로.

4-bank interleaved memory (c. 맨 우측. interleaved memory)

실제로 주로 사용하는 방식
bank는 I/O이 독립적으로 이루어질 수 있는 단위.
메모리 접근은 여러 곳(bank)으로 동시에 접근(I/O가 모두 독립적으로 가능),
하지만 데이터 교환은 차례로 일어남.

성능은 b가 가장 좋지만, 많은 하드웨어 자원(큰 bus, ...)이 사용되므로, c 형태(bank interleaved memory)를 주로 사용.

c는 하드웨어 자원은 a와 거의 유사하면서도, 성능은 b에 근접하게 향상된다.

DRAM Performance Factors

row buffer

병렬적으로(in parallel) 여러 word들을 읽고(read) 다시쓸(refresh) 수 있게 해 줌.
DRAM에서는 row 전체를 가져와서 데이터를 access함.

synchronous DRAM

DRAM이 clock에 동기화되어서 동작.
각각의 주소를 보내지 않고도, 연속된(consecutive) 주소에는 burst하게 access할 수 있게 해 줌.
bandwidth를 향상

DRAM banking

여러 DRAM(multiple DRAMs)에 동시에(simultaneous) access할 수 있게 해 줌.
bandwidth를 향상

5.3 Cache Memory

메모리 계층에서 가장 CPU와 근접한 단계

X1, ..., X(n-1), X_n으로 캐시에 access한다고 했을때, 아래를 보자.

access 후에 X_n에 해당하는 block이 캐시에 들어오게 된다.

Direct Mapped Cache

위치가 주소로 결정된다.

block의 수는 2^n개이다.
최하위 n비트를 address bits로 사용한다.

Tag and Valid Bits

블록 주소를 데이터처럼 저장한다.
실제로는, 오직 상위 비트들만 필요하다.
이걸 tag라고 부른다.

만약 캐시에 데이터가 없다면?

valid bit가 1이면 존재하는 것, 0이면 없는 것.
처음엔 0으로 시작.

Cache 예제

초기 상태

데이터 들어옴

index에 있던 다른 자료(11010) 대신 새로(10010) 쓰여짐.

Direct Mapped Cache 예제

Multiword Cache

64 blocks. 16 bytes/block. (4 words/block)

메인메모리의 주소가 1200인 block은 어떤 block number에 mapping되는가?

16-byte를 위해, 최하위 4비트(0~3자리)를 offset으로.
즉, 주소 중 최하위 4자리는 캐시저장에 무시한다는 것임.
주소의 최하위 4자리를 깎기 위해, right shift*4로써, 2^4인 16으로 나누면,
→ block address = 1200 / 16 = 75
64개의 block이니, 그 위 6비트(4~9자리)를 index로.
유의미한 75를 block의 수로 나머지 연산을 하면,
→ block number = 75 % 64 = 11 ∴
나머지 22비트(10~31자리)가 tag로.

Multiword Block Direct Mapped Cache

16 words/block.
cache size = 4K words

16 words는, 16*4 bytes. 2^6 bytes. 즉, 최하위 6비트를 offset으로.

word단위로 access하므로, 이 중 word offset은 최하위 2비트(0~1자리. 4byte.).
그 위 4비트(2~5자리)가 block offset.

캐시 사이즈는 4K words = 2^12 words = 2^(4+8) words.
즉, 2^8의 block이니, 블록 수는 256개.
offset의 상위 8비트(6~13자리)가 index.

나머지 최상위 18비트(14~31자리)가 tag.

한 block에 16개의 word가 담기지만, CPU가 access하는 것은 1 word.
즉, MUX를 사용하며, 여기에 block offset을 통해 블록의 몇 번째 word에 access할지 결정.

Block Size Considerations

블록이 클 수록 miss rate는 감소한다.

하지만 캐시의 크기는 고정되어 있다.
캐시의 크기는 고정되어 있는데, 블록의 크기가 커지면 캐시의 line(캐시의 블록)의 수는 줄어든다.

line이 줄어든다는 것은,
하나의 line이 map해야 할 담당 메모리 위치가 늘어나게 된다는 것.
(refresh가 자주 일어나고, 경쟁(competition)이 잦아진다.)
→ miss rate를 증가시킨다.
블록이 클 수록, 캐시의 line에 read/write가 자주 발생하면서 오염(pollution)된다.
→ refresh때 overhead가 더 커질 수 있음.

블록이 클 수록, miss penalty도 커진다.

Cache Misses

캐시가 적중했을 때(on cache hit)는, CPU는 보통처럼 동작한다.

캐시가 적중 실패했을 때(on cache miss)는,

CPU pipeline에 stall을 발생시킨다.
메모리의 다음계층(lower level)에서 해당 block을 fetch해온다.
Instruction cache miss였다면,
다시 instruction fetch가 될 수 있도록 한다.
Data cache miss였다면,
data access를 완료한다.

Write-Through

캐시와 함께 메모리 또한 업데이트한다.

문제
write가 더 오래 걸린다.
해결책: write buffer
메모리에 쓸 data를 여기서 가지고 있는다. 메모리에 write가 될 때까지.CPU는 즉시 계속 진행한다.
write buffer가 이미 가득 차있을 때(빼서 메모리에 써야함)에만 stall이 발생한다.

Write-Back

data-write가 발생하면, 메모리가 아닌 캐시의 블록만 바로 업데이트한다.

각 블록이 다른지(dirty한지) dirty bit로 추적한다.

dirty block이 제거될 때에

즉, 캐시의 데이터가 유효값인데, 해당 line에 교체 등의 이유로 캐시에서 빠져나가야 될 때,그 때에 메모리에 write it back.
여기에도 write buffer를 활용하여 메모리에 쓰는 걸 CPU가 기다리지 않도록 할 수 있다.

Write Allocation

write miss가 발생한다면 어떻게 되는가?

write-through의 대안(alternative)

allocate on miss(miss해버린 data를 가져와둠): fetch the block
write around: 블록을 fetch하지 않음(No write allocate).
- 그러면 그냥 캐시에는 write하지 않고, 메모리만 직접 업데이트함.

write-back의 대안(alternative)
＊주로 fetch the block.

5.4 Measuring and Improving Cache Performance

Measuring Cache Performance

Cache Performance 예제

조건

I-cache miss rate: 2%
D-cache miss rate: 4%
miss penalty: 100 cycles
base CPI (ideal cache): 2.0
instruction들의 36%가 load & store로 이루어져 있음.

miss cycles per instruction

I-cache = 0.02 * 100 = 2
D-cache = 0.36 0.04 100 = 1.44

actual CPI = 2.0 + 2 + 1.44 = 5.44

ideal CPU는 5.44/2.0 = 2.72배의 속도.

Average Access Time

hit time 역시 성능에 중요하다.

Average Memory Access Time (AMAT) 평균 메모리 접근 시간

AMAT = hit time + miss rate * miss penalty

ex)
조건

CPU with 1ns clock (CPU의 clock period가 1ns)
hit time: 1 cycle
miss penalty: 20 cycles
I-cache miss rate: 5%

AMAT = 1 + 0.05*20 = 2ns

2ns라면 조건에서는 2 clock cycles.
즉, 2 cycles per instruction

Performance Summary

CPU 성능이 향상되면 miss penalty가 점점 더 중요하게 여겨진다.

base CPI를 줄이면 총 시간 중에, 메모리 stall에 소요되는 시간의 비중이 더 커짐.

clock rate를 높이면(cycle time이 줄어서 더 자주 clock) 메모리 stall에 걸리는 CPU cycle이 더 많아진다.

시스템 성능을 평가할 때, cache 동작(behavior)을 무시할 수 없다.

Associative Caches

fully associative

block이 캐시의 어느 entry에나 들어갈 수 있음.
모든 entry를 한번에(즉시 동시에) 검색해야 함.
entry마다 comparator가 필요함. (비용이 비싸짐)

n-way set associative

각 set은 n개의 entry로 구성되어 있음(각 set은 n개의 entry를 갖고있음).
ㆍset은 캐시 line과 같은 의미라고 할 수 있음.
block number가 어떤 set에 매핑되는지 결정함.
ㆍ어느 set = (block number) % (캐시의 set 갯수)
해당 set의 entry들을 한번에 검색해야 함.
n개의 comparator가 필요함. (fully보다는 비용이 적어짐)

Associative Cache 예시

Spectrum of Associativity

How Much Associativity

associativity를 증가시킬 수록 miss rate는 낮아진다.

6-word blocks의 64KB D-cache를 가진 시스템을 SPEC2000으로 시뮬레이션해본 결과,
miss rate는,

1-way(direct mapped): 10.3%
2-way: 8.6%
4-way: 8.3%
8-way: 8.1%

Replacement Policy

cache miss가 발생했을 때, set 안에서 어떤 block을 교체할 것인가?

direct mapped: 선택권이 없음. 그냥 무조건 교체.

set associative

non-valid(valid bit가 0인) entry가 있다면, 이걸 선호

Least-Recently Used (LRU) 최근에 적게 사용된 것을 고른다.

2-way에서는 둘 중 고르기 쉽고, 4-way에서는 다룰 만한데, 그 이상에서는 이걸 고르는 것도 어려워진다.

Random

근데 high associativity에서는 LRU와 거의 유사한 성능 수준을 보여준다.

Set Associative Cache Organization

Multilevel Caches

Primary(L-1) cache는 CPU와 붙어있음(attached).

작지만, 빠르다.

Level-2 cache에는 primary 캐시 miss가 발생되었을 때에 접근한다.

L1보단 조금 더 크고, 조금 더 느리지만, 여전히 메인메모리에 비해서는 빠르다.

메인메모리에는 L-2 캐시(캐시메모리의 최하단) miss가 발생되었을 때에 접근한다.

최근의 고성능 시스템은 L-3 캐시도 갖기도 한다.

Multilevel Cache 예제

조건

CPU base CPI: 1, clock rate: 4GHz (즉, clock period는 1/(4*10^9) s/cycle = 0.25ns/cycle)
miss rate/instruction: 2%
메인메모리 access time: 100ns

primary cache만 사용했을 때,

miss penalty = 100ns / (0.25ns/cycle) = 400 cycles
effective CPI = 1 + 0.02 * 400 = 9

L-2 cache를 추가했을 때,

L-2 access time: 5ns
global miss rate to main memory: 0.5%
primary miss with L-2 hit
penalty = 5ns / (0.25ns/cycle) = 20 cycles
primary miss with L-2 miss
추가 penalty = 400 cycles (메인메모리로 miss penalty는 아까 구했었음)
effective CPI = 1 + 0.02 20 + 0.005 400 = 3.4
성능비(performance ratio) = 9/3.4 = 2.6
L-2캐시를 함께 사용하는 것이, 2.6배의 속도.

Multilevel Cache Considerations

고려사항

Primary cache

hit time을 줄이는 것에 초점을 둔다.

L-2 cache

miss rate를 줄여서 메인메모리에 access하는 것을 줄이는 것에 초점을 둔다.
hit time은 전체 성능에 별로 큰 영향을 주지 않음.

그 결과, 멀티레벨 캐시의 L-1 cache는 일반적으로 single 캐시보다 작다.
L-1의 블록 크기는 L-2의 블록 크기보다 작다.

5.7 Virtual Memory

메인메모리를 secondary memory(storage)의 캐시로써 사용

프로그램들은 메인메모리를 공유한다.

각 프로그램들은 private한 virtual address space를 갖게되며, 자주 사용하는 code와 data를 여기에 두고 사용.
이 private한 영역들은 다른 프로그램으로부터 보호된다.

CPU와 OS는 virtual adress들을 physical adress로 번역한다.

Address Translation

프로그램이 사용하는 주소는 virtual address,
실제 메인메모리(DRAM)의 주소는 physical address.

각각의 virtual address는 translation을 통해 physical address와 mapping이 된다.

fixed-size pages

그림의 예시는 2^12 = 4096 = 4KB의 page size.
page offset이 12비트(0~11자리)로, 2^12 = 4096 = 4KB.
access 단위가 page.
virtual memory(0~31 비트)는 2^32 = 4 * 2^30 = 4GB.
page offset인 12비트를 빼면, 20비트.
physical memory(0~29 비트)는 2^30 = 1GB.
page offset인 12비트를 빼면, 18비트.
4GB인 virtual address 공간이 1GB인 physical address 공간으로 translate되어야 함.
2^20인 virtual page number를, 2^18인 physical page number로.

Page Table

placement(translation) 정보를 갖고있음

age table entry들이 배열로 되어있음. virtual page number로 색인화(index) 되어있음.
CPU의 page table 레지스터가 page table이 존재하는 physical memory영역을 가리킨다.

page가 메모리(메인메모리)에 있다면,

page table entry(PTE)가 physical page number를 갖고있다.
그 외 다른 상태 정보들도 비트로 갖는다. (referenced, dirty, ...)

page가 메모리에 없다면,

PTE는 disk에 있는 swap space의 장소를 가리키게 된다.

valid가 1(Y)이라는 것은,

메인메모리에 해당 영역이 있어서, 제대로 메인메모리의 해당 영역을 가리킴.
valid가 0(N)이라는 것은,
메인메모리에 해당 영역이 없어서, storage의 swap space의 장소를 가리킴.

Translation Using a Page Table

Page Fault

page fault가 일어나면 page는 반드시 "disk"로부터 읽어와야(fetch) 된다.

수백만(millions) clock cycle이 소요된다.
OS code에 의해 처리된다.

page fault rate(발생률)을 최소화해보자.

fully associative placement기법
즉, 전체 page table의 translation 정보를 가져와서 갖고있는 것.
smart replace algorithms
OS에서 아주 정교한 알고리듬을 사용.

Page Fault Handler

page table의 PTE를 찾기 위한 virtual address가 잘못되었을 때.

해당 PTE를 통해 메인메모리의 page를 찾으려고 해도, 그 page가 없을 때.

disk의 swap space에 page를 할당시킨다.

교체할 page를 고른다.

만약 dirty가 있다면 이걸 우선한다.

page를 메모리로 가져와서(disk의 page 위치를 가져와서) page table을 업데이트한다.

프로세스를 다시 실행가능한 상태로 한다.

실패한 instruction을 재시작한다.

Replacement and Writes

page fault rate를 줄이기 위해서, Least-Recently Used (LRU) replacement(교체) 기법이 선호된다.

page에 access할 때, PTE(page table entry)의 reference bit(aka. use bit)을 1로 한다.
OS는 주기적으로 이 비트를 0으로 초기화시킨다.
즉, page의 reference bit이 0이라는 것은, 최근에 사용되지 않았다는 것.

disk(storage)에 쓰는 것은 millions(수백만) cycle이 소요된다.

한 번에 block 단위로 이루어짐. 개별적으로(byte) 이뤄지지 않음.
캐시와 메모리를 함께 업데이트하는 write-through방식은 사용할 수 없다(현실적이지 않다. impractical).
그러므로, write-back 방식을 사용한다.
그러므로, page가 업데이트된걸 알기 위해 PTE에 dirty bit을 두고 표시한다.

Fast Translation Using a TLB(Translation Look-aside Buffer)

page table로의 access는 good locality를 활용할 수 있다.

그러므로 PTE를 위한 빠른 캐시를 CPU에 두고 사용할 수 있다.

TLB Misses

page가 메인메모리에 있을 때(단순 TLB miss)

page table에 가서 PTE를 받아와서, 다시 시도한다.
하드웨어에서 처리할 수도 있다.
그러려면 page table 구조가 더 복잡해지고, 이를 위해 하드웨어 또한 복잡해진다.
소프트웨어(OS)가 처리하면,
특별한 exception을 발생시키고, optimized handler로 처리한다.

page가 메인메모리에 없을 때(true page fault)

OS가 처리하며, storage(disk)로부터 page를 fetch하고, page table을 업데이트한다.
그리고는 fault가 발생했던 instruction을 재시작한다.

TLB Miss Handler

TLB miss는 다음 중 하나이다.

page는 (메인메모리에) 존재하지만, TLB에 PTE(translation 정보)가 없는 것.
page가 (메인메모리에) 존재하지 않는 것.

handler는 메인메모리의 page table로부터 PTE를 TLB로 복사해온다.
그리고는 instruction을 재시작한다.
만약 page가 실제로 없다면, page fault가 발생할 것이다.

TLB and Cache Interaction

Memory Protection

다른 작업(task)은 각각 고유의 virtual address space를 사용한다.

다른 작업이 virtual address space의 같은 영역 일부분을 공유할 수도 있다.

e.g., 데이터 교환이나..
하지만 잘못된 access는 일어나지 않도록 보호해야 한다.
OS의 보조(assistance)가 필요하다.

하드웨어는 OS protection을 위해, 하드웨어적인 지원(support)을 한다.

privileged supervisor mode (aka. kernel mode)
privileged instructions
page table과 기타 state 정보들은 오직 supervisor mode에서만 접근이 가능하다(accessible).

5.8 A Common Framework for Memory Hierarchy

The Memory Hierarchy

공통적인(common) 원칙들(principles)이 메모리 계층(memory hierarchy)의 전 단계(all levels)에 적용된다.

계층(hierarchy)의 각 단계(each level)에서,

block placement(위치시키기. 할당.)
block 찾기
miss 발생시 replacement(교체)
write policy

Block Placement

associativity에 따라,

Direct mapped (1-way associative)
placement에 오직 한가지. 즉, set은 1way라 한 칸 뿐이라 무조건 한가지 선택지 뿐.
n-way set associative
set에 n개의 way가 있어서, n개의 선택지.
Fully associative
하나의 set 뿐이며, 한 set에 모든 block이 들어가 있으므로, 캐시의 block수 = 선택지의 수.

associativity가 높을 수록 miss rate가 감소한다.

해당 index인 set에 들여놓을 수 있는 선택지가 많아지니, replacement할 일이 줄고, 많은 정보를 갖고 있게 된다.

하지만, 복잡성, 비용, access time을 증가시켜버린다.

Finding a Block

associativity	location 방법	tag 비교
Direct mapped	index	1번
n-way set associative	index로 set을 찾고, 그 안의 entry들을 비교	n번
Fully associative	1. 한 개뿐인 set에서 모든 entry들을 비교 (cache)	"entry 수"번
	2. full lookup table (VM)	0번

하드웨어 캐시(SRAM)

비용을 줄이기 위해, 비교 횟수(comparator 수)를 줄임.

virtual memory(메인메모리를 storage를 위한 캐시로)

full lookup table이 full associativity를 가능토록 해줌.
miss rate를 줄여서 이득을 보기위해

Replacement

miss 발생시, 교체할 entry를 선택하는 방법

Least Recently Used (LRU)
high associativity에서는 복잡하고, 하드웨어 비용도 많이 든다.
Random
LRU와 비슷한 miss rate에 근접할 수 있으면서도(high associativity에서), 구현(implement)하기는 더 쉽다.

virtual memory

하드웨어의 도움(support)으로, LRU 근사(approximation) 기법을 사용.
clock replacement algorithm이라고 함.

Write Policy

write-through

현재(상층부, upper)와 하층부(lower) 단계를 함께 업데이트함.
replacement를 간단하게 만들어주지만, write buffer를 필요로한다.

write-back

먼저 현재(상층부, upper) 단계만 업데이트함.
업데이트된 block이 교체(replace)될 때, 하층부(lower) 단계를 마저 업데이트함.
더 많은 상태(state) 정보를 가지고 있어야 함.