컴퓨터 구조 및 설계 - Chapter 5. Large and Fast: Exploiting Memory Hierarchy

Chapter 5. Large and Fast: Exploiting Memory Hierarchy

ㆍCache 메모리를 이해할 수 있다.

5.2 - Memory Technologies

5.1 - Introduction

5.3 - The Basics of Caches

5.4 - Measuring and Improving Cache Performance

5.5 - Dependable Memory Hierarchy

5.6 - Virtual Machines

5.7 - Virtual Memory

5.8 - A Common Framework for Memory Hierarchy

5.9 - Using a Finite-State Machine to Control a Simple Cache

5.10 - Parallelism and Memory Hierarchy: Cache Coherence

5.11 - Parallelism and Memory Hierarchy: Redundant Arrays of Inexpensive Disks

5.12 - Advanced Material: Implementing Cache Controllers

5.13 - Real Stuff: The ARM Cortex-A8 and Intel Core i7 Memory Hierarchies

5.14 - Going Faster: Cache Blocking and Matrix Multiply

5.15 - Fallacies and Pitfalls

5.16 - Concluding Remarks

(목차를 블록 선택 후, Ctrl+F로 탐색 가능 - 브라우저에 따라 다를 수 있음)

---

<5.2 Memory Technologies>

 

 

 

Review: Major Componenets of a Computer

4장에서는 Processor에 대해 배웠었음.

5장에서는 Memory에 대해 배울 것임.

(6장에서는 Input/Output에 대해)

 

＊메모리는 크게 3가지로 나뉘어짐.

　ㆍSecondary Memory(Disk, Storage) → chapter6

　ㆍMain Memory → chapter5

　ㆍCache → chapter5

 

 

 

Memory Technology

 

＊메모리에는 ROM과 RAM이 있음.

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

　ㆍRAM은 Random Access Memory. 휘발성 메모리.

 

＊Static RAM (SRAM)

　ㆍ0.5ns ~ 2.5ns. $2000 ~ $5000 per GB.

 

＊Dynamic RAM (DRAM)

　ㆍ50ns ~ 70sn. $20 ~ $75 per GB.

 

＊Magnetic disk (HDD)

　ㆍ얜 storage(secondary memory).

　ㆍ5ms ~ 20ms. $0.20 ~ $2 per GB.

 

＊이상적인 형태라면..

　ㆍSRAM의 access 속도에

　ㆍ용량과 cost/GB는 disk 수준의 것

　(※ 없지만..!!)

 

 

 

Processor-Memory Performance Gap

＊프로세서는 Moore's Law를 따르면서 약 2년마다 기존 2배의 성능으로.

　ㆍ55%/year (2X/1.5year)

＊DRAM은

　ㆍ7%/year (2X/10year)

＊프로세서와 메모리의 성능차이는 50%/year만큼 증가하고 있음.

＊프로세서의 성능은 아주 빠르게 발전했지만,

　메모리의 성능향상은 더디기 때문에,

　실제로 체감하는 전체적인 성능향상은 크게 와닿지 않음.

　(※ Amdahl's Law.

　　전체에 차지하는 비중이 높은걸 향상시켜야 전체적으로 성능이 향상.

　　프로세서도 당연히 비중이 크지만, 메모리의 비중도 큼.)

 

 

 

The Memory Wall

 

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

　※ clock cycles. 클럭 싸이클 횟수.

　ㆍinstruction 수행(프로세서)에는 clock cycle 수가 줄어들었지만,

　　메모리 접근에는 필요한 clock cycle 수가 반대로 늘어났음.

　ㆍ메모리 접근에 필요한 clock cycle 수가 늘어나서(메모리의 성능 향상 제한으로)

　　성능 향상에 방해되는 것을 Memory Wall이라고 부름.

　ㆍ메모리 체계 (캐시) 설계를 잘하는 것이, 컴퓨터의 전체 성능 향상에 점점 더 중요해지고 있다.

 

---

<5.1 - Introduction>

 

 

 

Principle of Locality

지역성의 원칙

 

＊프로그램은 언제나 주소공간(메모리)의 아주 작은 일부분에 접근한다(access).

　ㆍ즉, access하는 부분을 계속 access할 확률이 높다.

 

＊Temporal(시간적인) locality(지역성)

　ㆍ최근에 access한 항목은 아마 곧 다시 access할 확률이 높다.

　ㆍe.g., loop에서의 instruction, induction 변수(반복문의 i)

 

＊Spatial(공간적인) locality

　ㆍ최근에 access한 항목 근처의 것들을 아마 곧 access할 확률이 높다.

　ㆍe.g., 연속되는(순차적인, sequential) instruction access, array 데이터

 

 

 

Taking Advantage of Locality

지역성을 활용

 

＊Memory hierarchy(계층)

　ㆍ자주 사용하는 데이터를 점점 고속의 임시 저장소로, CPU에 가깝게.

＊disk에 모든 것을 저장(store).

＊최근에 access한(그리고 주변들의) 항목들을 disk에서 작은 DRAM 메모리로 복사한다.

　ㆍ메인 메모리(고속)

＊좀 더 최근의 항목들은 DRAM에서 더 작은 SRAM 메모리로 복사한다.

　ㆍCPU에 붙은(CPU와 통합된) 캐시 메모리(초고속)

 

 

 

Memory Hierarchy Levels

메모리 계층의 단계

ㆁblock(aka. line): 복사의 단위(unit of copying)

　＊아마 여러개의 word(multiple words. 32-bit*n)

ㆁ만약 원하는 데이터가 상층부(upper level. 캐시, 더 빠른)에 존재하면,

　＊Hit(적중): 상층부에서 access를 성공.

　　ㆍhit ratio: hits/accesses

ㆁ만약 원하는 데이터가 없다면,

　＊Miss: 하층부(lower level. 더 느리고 더 큰)에서 block을 복사.

　　ㆍ시간소요: miss penalty

　　ㆍmiss ratio: misses/accesses = 1 - hit ratio

　＊상층부로 복사해와서는, 이제 상층부에서 데이터를 access함.

 

 

 

Characteristics of the Memory Hierarchy

메모리 계층의 특징

(※ 영어 cach와 cache의 발음유사성으로, cache를 $로 축약해서 표현하기도 함.)

＊access time

　ㆍ프로세서와 가까울 수록 upper level. access time이 적게 걸리고(더 빠르고), 용량은 작음.

　ㆍ프로세서와 멀 수록 lower level. access time이 오래 걸리고(더 느리고), 용량은 더 큼.

＊Inclusive(포함)의 특성

　ㆍL1$는 L2$의 subset(일부분)

　ㆍL2$는 메인메모리의 subset

　ㆍ메인메모리는 2차메모리의 subset

 

 

 

DRAM Technology

 

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

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

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

　　ㆍ내용을 읽고 다시 씀(read and write back).

　　ㆍDRAM의 "row"에 수행(데이터를 쓰는 곳).

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

DRAM의 내부 조직

 

 

 

Advanced DRAM Organization

발전된 DRAM 조직

 

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

　ㆍDRAM은 하나의 row에 전체적으로 access하고, 그 안에서 column..

　ㆍBurst mode: 감소된 지연시간(reduced latency)으로 row로부터 연속적인(successive) word들을 공급.

　　(row가 같은 곳에서 column만 다르다면, row를 바꿀 필요가 없으므로 훨씬 빨리 access 가능하다는 것)

 

＊Double Data Rate (DDR) DRAM

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

　(※ single은 rising이나 falling 중 한 edge에서만)

 

＊Quad Data Rate (QDR) 혹은 DDR2 DRAM

　ㆍDDR의 input과 output을 분리함?? ????

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

 

 

 

DRAM Generations

DRAM 세대

용량이 급격하게 커지고, cost/GB도 급격하게 좋아짐(싸짐).

 

 

 

DRAM Performance Factors

DRAM 성능 지표

 

＊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를 향상

 

 

 

Main Memory Supporting Caches

캐시(SRAM)을 돕는 메인메모리(DRAM)

 

ㆁDRAM을 메인메모리로 사용

　＊고정된 사이즈(width) (e.g., 1word)

　　ㆍ고정된 사이즈의 데이터를 access

　＊fixed-width clocked bus에 연결되어 있음.

　　ㆍbus clock은 전형적으로 CPU clock보다 느리다.

 

ㆁcache block read의 예시로, 아래와 같은 조건이라면,

　＊address transfer에 1 bus cycle.

　＊DRAM access에 15 bus cycle.

　＊data transfer에 1 bus cycle.

 

ㆁ4-word 짜리 block을 access할 때, 1-word-wide(1번에 1word 단위로 access) DRAM에서,

　＊miss penalty = 1 + 4*15 + 4*1 = 65 bus cycles.

　＊bandwidth = 16 bytes / 65 cycles = 0.25 byte/cycle.

 

 

 

Increasing Memory Bandwidth

메모리의 대역폭을 늘려보자

(방금 본 예시에서, 1-word-wide DRAM은 a(맨 좌측)의 형태)

 

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

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

　ㆍmiss penalty = 1 + 15 + 1 = 17 bus cycles.

　ㆍbandwidth = 16 bytes / 17 cycles = 0.94 byte/cycle.

 

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

　ㆍ실제로 주로 사용하는 방식

　ㆍbank는 I/O이 독립적으로 이루어질 수 있는 단위.

　ㆍ메모리 접근은 여러 곳(bank)으로 동시에 접근(I/O가 모두 독립적으로 가능),

　　하지만 데이터 교환은 차례로 일어남.

　ㆍmiss penalty = 1 + 15 + 4*1 = 20 bus cycles.

　ㆍbandwidth = 16 bytes / 20 cycles = 0.8 byte/cycle.

 

＊성능은 b가 가장 좋지만, 많은 하드웨어 자원(큰 bus, ...)이 사용되므로,

　c 형태(bank interleaved memory)를 주로 사용.

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

 

---

<5.3 - The Basics of Caches>

 

 

 

Cache Memory

 

＊Cache Memory

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

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

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

　　(캐시에 순서대로 위치하는 것은 아니다)

 

＊데이터가 현재 캐시에 존재하는지 어떻게 알 수 있는가?

＊어디를 살펴봐야 하는가?

 

 

 

Caching: 간단한 첫번째 예제

ㆁ예시로는 메인메모리에 16개의 word blocks.

 

ㆁ하위 2bits는 word 안에서의 byte를 정의하는데 쓰이므로,

　한 word 자체(one word block)을 읽을 때는 신경쓰지 않음.

　(어차피 word째로 읽을거니까)

　앞의 4bits를 주목하면(예시에서는),

　＊총 6bits 중 중간 2bits는 Cache의 index에 쓰임.

　　ㆍ캐시의 어느 열(line)에 매핑되는지.

　＊상위 2bits는 Cache의 Tag에 쓰임.

 

ㆁ캐시는 메인메모리와 어떤식으로 매핑이 이루어지는가?

　＊메인메모리는 16blocks. 캐시는 4lines.

　　ㆍ캐시는 line별로,

　　　메인메모리의 block 중에서,

　　　각자 정해진(index가 일치하는) 4개의 word block 중 1가지를 매핑한다.

　＊메인메모리 주소의 그 다음 2bits(캐시의 index)로 캐시의 line위치를 결정한다.

　＊캐시의 tag와 메인메모리 주소의 상위 2bits를 비교하여, 캐시에 메모리 block이 있는지 알 수 있다.

　＊캐시에서, index 10인 line에는 0010xx, 0110xx, 1010xx, 1110xx 중 하나가 매핑되어 있을 것.

　　ㆍ이제 tag를 보고, 찾으려는 메모리 주소의 상위 2bits를 비교하여 찾는 데이터가 캐시에 있는지 확인.

　　ㆍ맞으면 hit.

　　ㆍ다르면 miss.

　＊메인메모리의 주소(block address)들을, 캐시의 block들의 수로 나머지 연산을 한 것이

　　index가 됨.

 

 

 

Direct Mapped Cache

직접 매핑 캐시

 

＊위치가 주소로 결정됨(Location determined by address).

　ㆍ위에서 본 방식임. 계속 보고 있는 것.

＊Direct mapped: only one choice????

　ㆍ(block address) % (캐시의 블록수)

※ 1%8 = 9%8 = 17%8 = 25%8 = 1.　 5%8 = 13%8 = 21%8 = 29%8 = 5.

＊block의 수는 2^n개이다.

＊최하위 n비트를 address bits로 사용한다.

 

 

 

Tag and Valid Bits

 

＊캐시의 위치에 매핑된 데이터가, 메모리의 어느 특정 block와 일치하는지 어떻게 알 수 있는가?

　ㆍ블록 주소를 데이터처럼 저장한다.

　ㆍ실제로는, 오직 상위 비트들만 필요하다.

　ㆍ이걸 tag라고 부른다.

 

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

　ㆍvalid bit가 1이면 존재하는 것, 0이면 없는 것.

　ㆍ처음엔 0으로 시작.

 

 

 

Cache 예제

 

＊8-blocks. 1 word/block. direct mapped.

 

＊초기 상태

 

＊(계속) 새로 들어옴 (miss)

 

＊(계속) 새로 들어옴 (miss)

 

＊(계속) 기존에 있던*2 (hit*2)

 

＊(계속) 새로*2 (miss*2), 기존*1 (hit*1)

 

＊(계속) 새로 들어옴 (miss) - index에 있던 다른 자료(11010) 대신 새로(10010) 쓰여짐.

 

 

 

MIPS Direct Mapped Cache 예제

 

＊1 word blocks. cache size = 1K words (or 4KB)

　ㆍ1024개를 위한 비트(index)는, 1024=2^10이므로, 10개의 비트.

　　최하위 2비트(0~1자리)를 뺀, 2~11자리의 10개의 비트를 사용.

　ㆍblock이 1word로 되어있으므로, 하위 2비트는 무시할 수 있음.

　　(2비트로 인한, 4가지 구성이, byte*4=32bits로, 1word가 됨.)

　ㆍ나머지 비트인 상위 20비트(12~31자리)가 tag가 됨.

　ㆍ캐시메모리에서, 데이터는 32bits, index는 10bits, tag는 20bits, valid는 1bit.

 

＊이 캐시는 어떤 locality(지역성)를 활용하고 있는가?

　ㆍteporal locality만 활용. 인접 데이터(spatial)가 아닌, 최근 데이터를 직접.

 

 

 

예제: Larger Block Size

 

ㆁ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

캐시의 블록에 여러 word가 저장.

(위의 예제도 4 words/block이었음. 위의 예제는 그냥 block number만 구하는 것이었고, 여기서 자세한 설명.)

 

ㆁ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할지 결정.

 

ㆁ이 캐시는 어떤 locality(지역성)를 활용하고 있는가?

　＊temporal locality: 최근 사용한 데이터를 직접.

　＊spatial locality: 최근 사용한 데이터의 주변 근접 데이터까지 함께.

 

 

 

Block Size Considerations

블록 크기 고려사항

 

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

　＊spatial locality 때문에. 한꺼번에 많이 저장하니까.

 

ㆁ하지만 캐시의 크기는 고정되어 있다(a fixed-sized cache).

　＊캐시의 크기는 고정되어 있는데, 블록의 크기가 커지면 → 캐시의 line(캐시의 블록)의 수는 줄어듦.

　　ㆍline이 줄어든다는 것은,

　　　하나의 line이 map해야 할 담당 메모리 위치가 늘어나게 된다는 것.

　　　(refresh가 자주 일어나고, 경쟁(competition)이 잦아진다.)

　　　→ miss rate를 증가시킨다.

　＊블록이 클 수록, 캐시의 line에 read/write가 자주 발생하면서 오염(pollution)된다.

　　→ refresh때 overhead가 더 커질 수 있음.

 

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

　＊miss가 발생했을 때, miss마다 한 번에 더 많은 block을 읽어와야 함.

　　ㆍmiss rate를 감소시키려다, 전체적인 성능은 더 구려질 수 있음.

　　ㆍearly restart and critical-word-first(refresh하려는 word들 중 target word만 우선 바로 보내서 먼저 시작)기법 등이 도움이 될 수는 있음.

 

 

 

Cache Misses

 

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

 

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

　＊CPU pipeline에 stall을 발생시킨다.

　＊메모리의 다음계층(lower level)에서 해당 block을 fetch해온다.

　＊Instruction cache miss였다면,

　　ㆍ다시 instruction fetch가 될 수 있도록 한다.

　＊Data cache miss였다면,

　　ㆍdata access를 완료한다.

 

 

 

Write-Through

write에 대해 캐시가 어떤 정책을 따르고 있는지

 

ㆁdata-write가 발생하면, 메모리가 아닌 캐시의 블록을 바로 업데이트할 수는 있다.

　＊하지만 그러면 메모리와 캐시의 일관성이 없어진다.

　　(원본 메모리는 old값인데, 캐시만 new값이 되어버리면..;;)

 

ㆁwrite-through policy(정책): 그러므로, 캐시와 함께 메모리 또한 업데이트한다.

　＊이러한 캐시를 write-through cache라고 함.

 

ㆁ하지만 그러면 write가 더 오래 걸린다.

　＊e.g., 만약 기본(base) CPI가 1이고, instruction의 10%가 store 명령어이고,

　　메모리에 write하는데 100 cycles가 걸린다면,

　　ㆍ유효(effective) CPI = 1 + 0.1*100 = 11.

 

ㆁ해결책(solution): write buffer

　＊메모리에 쓸 data를 여기서 가지고 있는다. 메모리에 write가 될 때까지.

　＊CPU는 즉시 계속 진행한다(write buffer에 있는 data를 사용).

　　ㆍ메모리에 write가 될 때까지 기다리지 않아도 됨.

　　ㆍwrite buffer가 이미 가득 차있을 때(빼서 메모리에 써야함)에만 stall이 발생한다.

 

 

 

Write-Back

write-through와는 다른 방식

 

＊대안책(alternative): 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하지 않고, 메모리만 직접 업데이트함.

　　ㆍ어떤 프로그램은 시작할 때 전체 메모리를 초기화하는데, 그 블록을 다시 사용할 경우가 낮아져서, miss가 발생해도 캐시에 올리기보다는 바로 메모리에 쓴다????

 

ㆁwrite-back의 대안(alternative)

　＊주로 fetch the block.

 

 

 

예제: Intrinsity FastMATH

 

＊Embedded MIPS processor

　ㆍ12-stage pipeline

　ㆍ각 cycle마다 instruction과 data의 access. 즉 access마다 1 cycle 소요.

 

＊Split cache: I-cache와 D-cache가 나뉘어져있음(separate).

　ㆍInstruction cache. Data cache.

　ㆍ각각 16KB: 256 blocks * 16 words/block

　ㆍD-cache: write-through or write-back

 

＊SPEC2000 miss rate

　ㆍI-cache: 0.4%

　ㆍD-cache: 11.4%

　ㆍ가중 평균(weighted average): 3.2%

 

위의 Multiword Block Direct Mapped Cache에서 본 모델

 

 

 

잠깐 복습,

"write through cache"의 정의는?

data write가 발생할 때, 캐시와 메모리의 데이터를 모두 업데이트.

On data-write hit, update the block in both cache and memory.

 

---

<5.4 - Measuring and Improving Cache Performance>

 

 

 

Measuring Cache Performance

캐시 성능을 측정

 

ㆁCPU time의 요소(종류)들(components)

　＊program executiuon cycles

　　ㆍcache hit time을 포함

　＊memory stall cycles

　　ㆍ주로 cache miss들로 부터 발생

 

ㆁ간결화 가정(simplifying assumption)을 해보면,

 

 

 

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배의 속도.

　(※ ideal은 말그대로 이상적인. miss가 0인. 초기상태를 생각해도 miss가 0일 순 없는데, 여튼 0에 한없이 가까운.)

 

 

 

Average Access Time

 

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

 

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

　＊AMAT = hit time + miss rate * miss penalty

 

ㆁ예제

　＊조건

　　ㆍ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가 점점 더 중요하게 여겨진다.

　ㆍ더 많은 비중을 차지하게 된다.

　ㆍCPU가 빨라지면, 총 시간 중에 "메모리에서 소요되는 시간"이 더 많이 차지하게 됨.

　　(총 시간 중에 프로세서에서 소요되는 시간이 줄어들어서)

 

＊base CPI를 줄이면,

　ㆍ총 시간 중에, 메모리 stall에 소요되는 시간의 비중이 더 커짐.

 

＊clock rate를 높이면(cycle time이 줄어서 더 자주 clock),

　ㆍ메모리 stall에 걸리는 CPU cycle이 더 많아짐.

 

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

 

 

 

Associative Caches

이제 그동안 본 것(Direct Map Cache. 캐시의 block(line)에 한 block이 들어감.)과는

다른 형태의 캐시를 볼 것임.

캐시의 set(line)에 여러 block이 들어감. 이 캐시의 line은 block이 단위가 아니라, set이 단위.

 

ㆁ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 예시

※ Fully associative는 set이 1개처럼.

 

 

 

Spectrum of Associativity

 

＊8개의 entry를 가진 캐시를 생각해보자.

　아래의 4가지 구조가 가능하다.

　ㆍentry는 tag와 data로 이루어져 있음. set 안에서 way 단위로 구분함.

　ㆍ1-way set associative는 direct mapped와 같음. set이 결국 block.

　ㆍset이 1개이고 그 안에 모든 entry가 속하는 구조는 결국 fully associative.

 

 

 

Associativity 예제

 

＊4-block의 캐시. 즉, 4개의 entry를 갖는 캐시들을 비교해보자.

　ㆍdirect mapped, 2-way set associative, fully associative의 3종류가 가능하다.

　ㆍblock access 순서: 0 - 8 - 0 - 6 - 8

 

＊Direct mapped

　ㆍ0%4=0, 8%4=0, 6%4=2. index.

　ㆍ5번의 access에 5번의 miss.

 

＊2-way set associative

　ㆍ0%2=0, 8%2=0, 6%2=0. 모두 set0에 들어가게 됨.

　ㆍ4번째에서, set0의 way0을 최근에 access했으므로 way1에 새로씀(refresh).

　ㆍ5번째에서, set0의 way1에 최근에 가져왔으므로 way0에 새로씀(refresh).

　ㆍ5번의 access에 4번의 miss, 1번의 hit.

 

＊fully associative

　ㆍfully associative는 set이 한 개. index가 없음.

　ㆍ캐시는 4칸이므로, 꽉 찼다면 access/write한지 오래된 것부터 제거하고 새로씀(refresh).

　ㆍ5번의 access에 3번의 miss, 2번의 hit.

 

 

 

How Much Associativity

어느 정도(몇-way)로 구성해야 하는가

 

＊associativity를 증가시킬 수록 miss rate는 낮아짐.

　ㆍ하지만 점차 그 효과는 낮아짐(효율이 낮아진다는 소리. 로그함수 그래프처럼)

 

＊16-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%

　ㆍ4-way나 8-way나 성능의 차이는 거의 없지만,

　　비용은 associativity가 커질 수록 점점 더 커지기 때문에,

　　비용대비 효율은 급감함.

 

 

 

Set Associative Cache Organization

set associative cache의 내부구조

아래는 4-way set associative cache.

 

 

 

Replacement Policy

교체 정책(방식)

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

 

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

 

ㆁset associative

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

　＊그 다음 조건(non-valid가 여럿이거나, valid만 있거나)으로는 아래 같은 방식..

 

ㆁLeast-Recently Used (LRU) 최근에 적게 사용된. 즉, 잘 안쓰는.

　＊장시간 잘 쓰지 않는 것을 고른다.

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

 

ㆁRandom

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

 

 

 

Multilevel Caches

지금까지는 한 계층의 캐시 메모리 모델을 봤었음.

실제로 사용하는 CPU는 여러 계층으로 되어있고,

최근에는 3레벨까지도 있음.

 

＊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의 블록 크기보다 작다.

 

 

 

Interactions with Advanced CPUs

발전된 프로세서에서 캐시의 상호작용

 

ㆁout-of-order(instruction을 순서 상관없이 실행하는) CPU는

　cache miss동안에도 instruction들을 실행할 수 있다.

　＊보류된 store 동작은 load/store unit에서 머무른다.

　＊miss한 것에 의존적인(dependent) instruction은 reservation station에서 대기한다.

　　ㆍ비의존적인(independent) 즉, miss와 관련없는 instruction은 계속 실행된다.

 

ㆁmiss의 효과(effect)는 프로그램의 data flow(프로그램이 어떻게 실행되는지)에 의존적이다(영향을 받는다).

　＊분석(analyse)이 훨씬 힘들다.

　＊모델 분석보다는 system simulation을 사용해서 분석한다.

 

 

 

Interactions with Software

ㆁmiss는 memory access 패턴에 의존적이다(영향을 받는다).

　＊algorithm behavior

　　ㆍ퀵정렬(quick sort)과 기수정렬(radix sort)는 동작 방식(패턴)이 다르기 때문에, 당연히 miss 패턴도 달라진다.

　＊컴파일러는 memory access를 최적화한다.

　　ㆍ이미 효율적인 access를 하는(혹은 최적화가 훨씬 잘 먹히는 동작인) 퀵정렬과는 다르게,

　　　기수정렬에서는 컴파일러의 최적화로, 더 많은 데이터를 정렬할 때 miss빈도가 감소하기도 한다.

　　　(항상 그런 것은 아니다. 최적화가 만능은 아닐테고, 한계도 있을테니.)

 

 

 

Software Optimization vis Blocking

 

 

 

DGEMM Access Pattern

 

 

 

Cache Blocked DGEMM

 

 

 

Blocked DGEMM Access Pattern

 

 

 

---

<5.5 - Dependable Memory Hierarchy>

 

 

 

The Hamming SEC Code

 

 

 

Encoding SEC

 

 

 

Decoding SEC

 

 

 

SEC/DED Code

 

 

 

---

<5.6 - Virtual Machines>

 

 

 

Virtual Machines

 

 

 

Virtual Machines Monitor

 

 

 

예제: Timer Virtualization

 

 

 

Instruction Set Support

 

 

 

---

<5.7 - Virtual Memory>

이제 캐시(SRAM)가 아닌,

메인메모리(DRAM)를 캐시처럼 사용하는 것에 대해

 

 

 

Virtual Memory

 

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

　ㆍstorage에서 많이 사용하는 것을 메인메모리에 올려서 사용하는.

　ㆍCPU(하드웨어)와 OS(소프트웨어)가 공동으로 관리한다.

　　(대부분의 기본적인 기능은 CPU가 제공, 실제 관리하는 역할은 OS가.)

 

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

　ㆍ각 프로그램들은 private한 virtual address space를 갖게되며, 자주 사용하는 code와 data를 여기에 두고 사용.

　ㆍ이 private한 영역들은 다른 프로그램으로부터 보호된다.

 

＊CPU와 OS는 virtual adress들을 physical(물리적) adress로 번역한다(translate).

　ㆍVM "block"은 page라고 불린다.

　ㆍVM translation "miss"는 page fault라고 불린다.

 

 

 

Address Translation

프로그램이 사용하는 주소는 virtual address,

실제 메인메모리(DRAM)의 주소는 physical address.

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

(하나의 page는 하나의 physical address에)

메인메모리에 mapping이 되는 것도 있지만,

storage(secondary memory)에 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 size는 4KB.

　ㆍ물론, 최근의 CPU는 다양한 크기(4KB, 8KB, 16KB, 1MB, ...)를 지원해 줌.

 

 

 

Virtual Addressing with a Cache

＊CPU가 사용하는 주소는 virtual address임.

　ㆍ즉, 프로그램이 사용하는 주소가 virtual address.

＊Cache가 사용하는 주소는 physical address임.

＊그러므로, CPU에서 사용하는 VA(virtual address)를

　캐시에 사용하기 위해서는 PA(physical address)로 바꿔주어야 함.

　ㆍ즉, 중간에 translation 과정이 필요함.

＊VA to PA의 translation 과정에, extra memory access가 필요함.

　ㆍtranslation 정보가 메인메모리에 존재하므로, 메인메모리에 access해야 함.

　ㆍ그런데, 메인메모리 access time은, 캐시에 비해 훨씬 느림.

　　캐시에 access하기 위해 매번 메인메모리에 access하는 것은 상당한 overhead를 발생.

　ㆍ이런식으로 실제로 2번의 access가 이뤄진다면 캐시에 access하는 것조차 굉장히 부담됨(very expensive).

＊하드웨어는 Translation Lookaside Buffer (TLB)를 사용하여이 문제를 해결한다.

　ㆍ매번 메인메모리의 page table을 탐색하지 않도록,

　　최근에 사용한(address translation한) 주소 mapping 정보를 보관하는 작은 캐시.

 

 

 

Page Fault Penalty

 

ㆁpage fault가 일어나면(access하고자 하는 page가 메인메모리에 없는 것),

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

　＊수백만(millions) clock cycle이 소요된다.

　＊OS code에 의해 처리된다.

 

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

　＊fully associative placement기법

　　ㆍ즉, 전체 page table의 translation 정보를 가져와서 갖고있는 것.

　＊smart replace algorithms

　　ㆍOS에서 아주 정교한 알고리듬을 사용.

 

 

 

Page Tables

 

＊placement(translation) 정보를 갖고있음

　ㆍpage table entry들이 배열로 되어있음. virtual page number로 색인화(index) 되어있음.

　ㆍCPU의 page table 레지스터가 page table이 존재하는 physical memory영역을 가리킨다.

　　(physical memory에 page table이 있고, 저 레지스터가 여기를 가리킨다)

 

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

　ㆍpage table entry(PTE)가 physical page number를 갖고있다.

　ㆍ그 외 다른 상태 정보들도 비트로 갖는다. (referenced, dirty, ...)

 

＊page가 메모리에 없다면,

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

 

 

 

2 Programs Sharing Physical Memory

 

＊프로그램의 address 공간은 page단위(모두 같은 fixed-size) 혹은 segemnt단위(다양한 size)로 나뉘어진다.

　ㆍ프로그램의 page table에는 각 page(메인메모리든 storage든)의 시작주소를 갖고있다.

　　(즉, translation 정보. 도착지 physical memory address.)

 

 

 

Translation Using a Page Table

 

 

 

Mapping Pages to Storage

 

어떤 page들은 메모리에 mapping되지만,

어떤 page들은 storage에 mapping됨.

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

　ㆍ메인메모리에 해당 영역이 있어서, 제대로 메인메모리의 해당 영역을 가리킴.

＊valid가 0(N)이라는 것은,

　ㆍ메인메모리에 해당 영역이 없어서, storage의 swap space의 장소를 가리킴.

 

 

 

Replacement and Writes

교체와 쓰기

 

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

　(※ 대표적인 clock replacement algorithm)

　ㆍ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).

　　(쓰는데 수백만 cycle이 소요되니까..)

　ㆍ그러므로, write-back 방식을 사용한다.

　ㆍ그러므로, page가 업데이트된걸 알기 위해 PTE에 dirty bit을 두고 표시한다.

 

 

 

Fast Translation Using a TLB

Translation Look-aside Buffer

 

＊원래라면, address translation은 추가적인 memory reference(메인메모리에)를 필요로 한다.

　ㆍPTE(page table entry)에 access할 때 (이게 추가적인. page table이 메인메모리에 있음)

　ㆍ실제로 memory access할 때

 

＊하지만, page table로의 access는 good locality를 활용할 수 있다.

　(cache에 비해서도 locality가 더 우수함)

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

　ㆍ이것을 Translation Look-aside Buffer (TLB)라고 부른다.

　ㆍ전형적으로:

　　TLB에는 16~512개의 PTE를 가지며,

　　hit에는 0.5~1 cycle, miss에는 10~100 cycle이 소요됨.

　　0.01~1% 수준의 miss rate를 보인다.

　ㆍmiss는 하드웨어와 소프트웨어에 의해 처리된다.

 

 

 

 

A TLB in the Memory Hierarchy

ㆁTLB miss가 발생하면,

　＊단순히 TLB miss(TLB에 원하는 translation 정보가 없는지)이거나,

　＊page fault(가리키는 page가 실제로 메인메모리에 없는지)일 수도 있다.

 

　＊page가 메인메모리로부터 load된다면(page fault가 아니라 단순 TLB miss여서),

　　page table에서 TLB로 translation 정보를 load시키면서

　　TLB miss가 처리될 수 있다(하드웨어와 소프트웨어가 처리).

　　ㆍpage table에서 정보를 찾고, TLB로 load시키는 데에 약 수십(10's)정도의 cycle이 소요된다.

　＊하지만 page가 메인메모리에 없다면(즉, 진짜 page fault라면),

　　ㆍpage fault를 처리하는데 수백만(million) cycle이 소요된다.

 

ㆁTLB miss가 true page fault보다는 아주 잦은 편이다.

　(true page fault는 TLB miss에 비해서는 아주 적게 일어난다.)

 

 

 

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가 (메인메모리에) 존재하지 않는 것.

 

＊대상 레지스터에 overwrite가 이뤄지기 전에(instruction이 진행 완료되기 전에????)

　TLB miss임을 알아차려야 한다.

　ㆍ그래서 exception을 발생시킨다.

 

＊handler는 메인메모리의 page table로부터 PTE를 TLB로 복사해온다.

　ㆍ그리고는 instruction을 재시작한다.

　ㆍ만약 page가 실제로 없다면, page fault가 발생할 것이다.

 

 

 

Page Fault Handler

 

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

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

 

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

 

＊교체할 page를 고른다.

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

 

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

 

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

　ㆍ실패한 instruction을 재시작한다.

 

 

 

TLB and Cache Interaction

ㆁ이전에 배운대로, physical address tag를 cache tag로 사용한다면,

　＊cache를 훑기 전에 translation이 필요하게 된다.

 

ㆁ다른 방식: virtual address tag를 사용한다. (실제로 사용하진 않음. 내용은 아래에.)

　＊그러면, cache를 훑을 때는 translation 과정이 필요하지 않다.

　　(cache access 이전 단계에 translation이 있을 필요는 없다.)

　　ㆍ이러면 access 시간을 줄일 수 있다.

　　ㆍ하지만, 대부분의 CPU는 이런 방식을 사용하지 않고 있음.

　＊aliasing 때문에 복잡해진다.

　　ㆍ다른 virtual address가 같은 physical address를 가리키는 것.

　　　(하나의 physical address가 여러개의 virtual address로 mapping될 수 있음)

　　ㆍ같은 데이터를 가리키는 정보가 캐시에 여러개 존재하면, 비효율적이고 복잡해짐..

　　ㆍ캐시의 3개가 같은 곳의 데이터를 가리킬 때,

　　　캐시 한 곳을 업데이트 하면, 실제 데이터(메모리의)도 반영하겠지만(write-through든, write-back이든),

　　　나머지 다른 곳은 모르니(dirty 정보 관리든).. 이런 문제 해결을 같이 고려하면 복잡해짐.

 

 

 

Memory Protection

 

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

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

　　ㆍe.g., 데이터 교환이나..

　　ㆍ하지만 잘못된 access는 일어나지 않도록 보호해야 한다.

　　ㆍOS의 보조(assistance)가 필요하다.

　　　(OS가 보호조치를 한다.)

 

ㆁ하드웨어는 OS protection을 위해, 하드웨어적인 지원(support)을 한다. (다음 기능들을 제공)

　＊privileged supervisor mode (aka. kernel mode)

　＊privileged instructions

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

　＊system call exception (e.g., syscall in MIPS)

 

---

<5.8 - A Common Framework for Memory Hierarchy>

 

 

 

The Memory Hierarchy

 

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

　ㆍcaching의 개념(notion)(자주 사용하는 것을 가까이에 두는.)에 의거하여(based on).

　ㆍ아래의 원칙들.

 

＊계층(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을 증가시켜버림.

　　　(한 set 안에는 동시에 검색해야 하므로, comparator가 여러개 설치되면..)

 

 

 

Finding a Block

associativity	location 방법	tag 비교
Direct mapped	index	1번
n-way set associative	index로 set을 찾고, 그 안의 entry들을 비교	n번
Fully associative	한 개뿐인 set에서 모든 entry들을 비교 (cache)	"entry 수"번
	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) 정보를 가지고 있어야 함.

 

＊virtual memory

　ㆍdisk write latency로 인해, write-back만 가능

 

 

 

Sources of Misses

miss의 원인

 

ㆁ의무적(compulsory) misses (aka. cold start misses)

　＊block에 첫 access를 할 때

 

ㆁ용량(capacity) misses

　＊유한한(finite) 캐시 사이즈 때문.

　　ㆍupper level이 lower level보다 작으니까.

　＊교체되는(replaced) 블록을 나중에 다시 access하려고 하면 캐시에는 없으니까 miss.

 

ㆁ충돌(conflict) misses (aka. collision misses)

　＊non-fully associative cache에서 발생(fully associativity가 아닌 캐시에서)

　＊set 안에서 entry끼리의 경쟁(competition)으로 발생.

　＊한 set가 캐시의 total size와 같은 fully associative cache에서는 일어나지 않음????

　＊fully associative cache가 아닌 n-way set associative cache에서 일어나는 miss만..????

 

 

 

Cache Design Trade-offs

Design change	miss rate에 영향	성능에 악영향
cache size를 늘림	capcacity miss를 줄임	아마 access time을 늘리게 됨.
associativity를 늘림	conflict miss를 줄임	아마 access time을 늘리게 됨.
block size를 늘림	compulsory miss를 줄임 (인접 데이터를 함께 가져오면, 첫 access도 가능하기도.)	miss penalty를 늘려버림. 아주 큰 블록 크기에서는, 아마 miss rate가 늘어날 것임(pollution 때문에).

 

---

<5.9 - Using a Finite-State Machine to Control a Simple Cache>

실제 캐시가 어떻게 동작하는지, 방식에 관한.

 

 

 

Cache Control

 

ㆁ예시로, 아래의 특징을 갖는 캐시를 생각해보자.

　＊Direct mapped, write-back, write allocate

　＊block size: 4 words (16 bytes = 2^4 bytes)

　＊cache size: 16KB (1024 blocks = 2^10 blocks)

　＊32-bit byte addresses

　＊block마다 valid bit과 dirty bit이 존재.

　＊blocking cache

　　ㆍCPU는 access가 완료될 때까지 기다림.

　　ㆍcass miss가 발생하면, access가 멈추고, 해결된 후에 다시 명령어가 실행되는.

 

 

 

Interface Signals

인터페이스 신호

 

 

 

Finite State Machines

＊control 단계 진행(sequence. 순서적 진행.)을 위해 FSM(Finite State Machine)을 사용한다.

＊state의 set(설정)과 transition(전이)를 각 clock edge마다 한다.

　ㆍstate값은 binary로 encode된다.

　ㆍ현재 state는 레지스터에 저장되어 있다.

　ㆍ다음 state는, fn(current state, current inputs)의 결과로 결정된다.

＊control output signals = f0(current state)

 

 

 

Cache Controller FSM

Finite State Machine

※ Compare Tag단계에서,

　clock cycle time을 줄이기 위해,

　각 state의 검토과정을 분리시킬 수 있다.

 

---

<5.10 - Parallelism and Memory Hierarchy: Cache Coherence>

 

 

 

Cache Coherence Problem

통일, 긴밀성

 

＊2개의 CPU core가 같은 physical address space를 공유한다고 가정해보자.

　ㆍ둘 모두 write-through(캐시와 원본에 같이 쓰는) 캐시를 가진다.

시간 순서	Event	CPU A의 캐시	CPU B의 캐시	메모리
0	-			0
1	CPU A가 X를 read	0		0
2	CPU B가 X를 read	0	0	0
3	CPU A가 X에 1을 write.	1	0	1

캐시에서,

같은 physical memory에 대해서,

서로 다른 데이터를 갖고 있게 되는 것.

 

 

 

Coherence Defined

 

ㆁinformally(우리가 원하는 바): 가장 최근에 쓰여진 값을 read.

 

ㆁformally(현실은):

　＊P writes X; P reads X (개입(interven) 없음)

　　→ 쓰여진 값을 제대로 읽음

　＊P1 writes X; P2 reads X (충분히 늦게)

　　→ 쓰여진 값을 제대로 읽음

　＊P1 writes X; P2 writes X

　　→ 모든 프로세서에서 같은 순서(same order)에 write하려고 하는 것을 보임.

　　　ㆍX에는 같은 최종값으로 마무리 됨????

 

 

 

Cache Coherence Protocols

 

ㆁ멀티프로세서 환경에서 캐시에 의해 동작하는 작업들은 coherence(통일성)를 보장해야 함.

　＊data를 local cache로 이식(migration)

　　ㆍ즉, data를 local cache에서 주고 받음.

　　ㆍ단, shared memory의 bandwidth가 줄어든다.

　＊read-shared data는 복제(replication)

　　ㆍread만을 위한 data는 여러 캐시에 올라가도 됨.

　　ㆍaccess를 위한 contention(경쟁)이 줄어든다.

 

ㆁsnooping(훔쳐보기) protocols

　＊각각의 cache가 bus reads/writes를 감시한다(monitor).

　　ㆍ그렇게 감시하다가, 자기 캐시에 있는 데이터가 업데이트되면, 자신도 업데이트할 수 있도록.

　＊bus share할 때에 많이 사용.

 

ㆁdirectory-based protocols

　＊directory에서 캐시와 메모리가 블록들의 sharing staus를 녹화한다(record).

　　ㆍdirectory에서 각각의 정보를 가지고 있고, 관리한다.

　＊core 수가 많거나, memory(bus????)가 모두 share되지 않는 경우에 적합.

 

 

 

Invalidating Snooping Protocols

 

ㆁ캐시는 블록에 값을 쓸 때, 독특한 access를 진행함.

　＊bus에 broadcast(전역방송)로 invalidate message를 뿌림.

　＊다른 캐시에서는 이후 read에서 cache miss가 발생(기존 데이터는 invalid하니까)

　　ㆍ값을 바꾼(owning, 소유한) 캐시에서 업데이트한 값을 공급해줌(supply).

　　ㆍ그리고, 이 때 메모리에도 값을 써 줌.

　　ㆍ혹은 owner entry가 replace당할 때..

　　ㆍ역시 더 복잡한 과정이 필요해짐.

CPU 행동	bus 행동	CPU A의 캐시	CPU B의 캐시	메모리
처음				0
CPU A가 X를 read	cache miss for X	0		0
CPU B가 X를 read	cache miss for X	0	0	0
CPU A가 X에 1을 write.	invalidate for X	1	- (invalid)	0
CPU B가 X를 read	cache miss for X	1	1	1

 

 

 

Memory Consistency

일관성

 

＊write는 언제 다른 프로세서에 의해 읽혀지는가(보여지는가, seen)?

　ㆍ여기서 "보여진다는(seen)"건 written value라는 return을 read하는 것.

　ㆍ단번에 순간적으로(instantaneously) 이뤄질 수는 없다.

 

＊가정(assumptions)

　ㆍwrite는 모든 프로세서가 그 값을 볼 수 있게 된 후(all processors have seen it)에서야 완료될(complete) 수 있다.

　ㆍ프로세서는 write를 다른 access들과 함께 재요청(reorder)할 수 없다????

　　a processor does not reorder writes with other accesses????

 

＊결과(consequence)

　ㆍP writes X then writes Y

　　→ 모든 프로세서에서, new Y와 new X를 모두 볼 수 있다.

　ㆍ프로세서가 read는 재요청(reorder)할 수 있지만, write는 그럴 수 없다.

 

---

<5.13 - Real Stuff: The ARM Cortex-A8 and Intel Core i7 Memory Hierarchies>

 

 

 

Multilevel On-Chip Caches

 

 

 

2-Level TLB Organization

 

 

 

Supporting Multiple Issue

 

 

 

---

<5.14 - Going Faster: Cache Blocking and Matrix Multiply>

 

 

 

DGEMM

 

 

 

---

<5.15 - Fallacies and Pitfalls>

 

 

 

Pitfalls

함정

 

ㆁbyte vs. word(4byte) addressing

　＊예시: 32-byte direct-mapped cache, 4-byte blocks.

　　ㆍbyte addressing: 36은 block 1에 mapping.

　　ㆍword addressing: 36은 block 4에 mapping.

 

ㆁmemory system을 고려하지 않고(무시하고) 코드를 작성하면,

　＊예시: 배열에서 row 단위로 반복 vs. column 단위로 반복

　＊poor locality가 되어 성능에 좋지 않다.

 

ㆁshared L2 or L3 캐시를 사용하는 멀티프로세서 환경에서,

　＊core 수보다 associativity를 적게하면, conflict miss가 잦게 발생한다.

　＊즉, core 수가 많아지면, associativity도 늘려야 한다.

 

ㆁout-of-order 프로세서의 성능을 평가하려면, AMAT(Average Memory Access Time)을 사용하면,

　＊AMAT 측정은 non-blocked access의 영향를 무시한다.

　　(non-blocked access: miss가 난 block을 제외하고 다른 것들을 실행)

　＊대신에, simulation을 통해 성능을 평가하는 것이 옳다.

 

ㆁpage가 아닌 segment라는 개념을 사용하여 address를 구역(range)화 한다면,

　＊e.g., Intel 80286

　＊하지만 segment가 항상 충분히 큰 것은 아니다(is not always big enough).

　＊주소 연산을 더 복잡하게 만든다.

 

ㆁvirtualization을 고려하지 않은 설계를 가진 ISA에서,

　VMM을 구현한다면,

　＊e.g., non-privileged instructions accessing hardware resources

　＊문제가 되는(problematic) instruction을 사용하지 않도록,

　　ISA를 확장하든(extend), guest OS가 필요해진다.

 

---

<5.16 - Concluding Remarks>

 

 

 

Concluding Remarks

 

＊빠른 메모리는 작고, 큰 메모리는 느리다.

　ㆍ바라는 이상향은 빠르고, 큰 메모리지만;;

　ㆍ캐싱(caching) 기법이 실제로 그렇지는 않아도, 마치 그런 것처럼 어느 정도 실현시켜준다.

 

＊locality 원리(principle)

　ㆍ프로그램은 memory space의 작은 영역(small part)를 자주(frequently) 사용한다.

 

＊memory hierarchy

　ㆍL1 cache↔L2 cache↔...↔DRAM memory↔disk

 

＊memory system 설계는 멀티프로세서에 아주 중요하다(critical).