Cache

Directed mapped cache

<값 구하기>

• Block address = memory address / block size
  • 여기서 block size는 byte 단위임
• Block number = block address % block 개수
• offset bit 수 = block 당 byte의 지수 값 (Ex. 8이면 offset bit 수는 3)
• index bit 수 = block의 개수의 지수 값 (64 blocks 면 index bit 수는 6)
• Tag bit 수 = 32 - index bit 수 - offset bit 수

tag : 보다 확실한 정보를 위해 앞쪽 비트 정보도 필요해서 기록하는 것

valid bit : 이 정보가 정말 유효한 정보인지 확인하는 것

Ex) 예제

8-blocks, 1 word / block, direct mapped of blocks in cache : 2^3, 4bytes / block

앞에 byte offset (block 당 4bytes이므로 2bit) 2bit를 제외하고 index bit 수는 block 수가 8이므로 3, 나머지가 tag bits (27bits)

** valid 가 0이면 무조건 Miss이다.

 

Block size에 대하여

---

• larger block

block 크기가 더 클 수록 miss rate를 낮춘다. 크기가 크면 내 프로그램이 한 block에 있을 가능성이 높기 때문

but 고정된 크기의 캐시에서는 오히려 안 좋을 수 있다.

block 크기가 클수록 block 개수가 줄어들고, 메모리가 차지하기 위한 경쟁이 증가하여 오히려 miss rate 가 늘어날 수도 있다. → 즉, 메모리 낭비가 될 수도 있다.

• smaller block

너무 잘게 쪼개져 있어서 hit이 잘 안 될 가능성이 있다. (없으면 다시 main memory 가야 해서 시간이 너무 오래 걸림)

• Larger miss penalty

block 크기가 크면 클 수록 copy 시간이 증가한다. (내가 필요한 부분은 일부분일텐데 다 복사해야 해서 시간이 오래 걸림) → 공간낭비이다.

** large 와 small의 optimal point는 CPU, 프로그램에 따라 다르다.

 

Cache (Read) Misses

• hit

CPU는 정상 실행된다.

• Miss

pipeline stall 필요

main memory로 가서 필요한 내용을 cache에 복사해온다.

• instruction cache miss

PC value를 -4 해서 IF를 다시 실행한다. (PC + 4가 이미 진행된 상태이므로 이전 process를 다시 실행하려면 -4를 해야 함)

• data cache miss

data access를 완료한다. (아까 main memory에서 복사해서 가져온거 쓰면 됨)

 

Cache (write) Misses

read miss와 유사하지만, 추가 과정이 필요하다.

data-write hit → cache 안에 있는 값을 변경하면 된다.

그런데 store instruction으로 cache에 값을 저장하게 되면 cache에만 변경 사항이 기록되고 main에는 old value 가 있게 된다. → inconsistency

⇒ Write-through VS Write-back

 

Write-Through

항상 cache와 memory를 동시에 업데이트 한다.

먼저 cache에 쓰고, memory에 쓴다. (간단함)

다만 memory에도 쓰기 때문에 시간이 오래걸린다.

• Ex. base CPI 가 1이고, instruction의 10%가 store이며, memory에 쓰는데 100 cycles이 소요되면 Effective CPI = 11이 된다. (1 + 100 * 0.1)

해결책 : write buffer 사용하기. memory에 쓰여지기를 기다리고 있는 data를 저장한다. CPU는 즉시 진행되고, write 할 때 write buffer가 이미 꽉 찼을 때만 stall이 발생한다.

 

Write-back

캐시에만 업데이트하고, 업데이트할 메모리가 달라지게 되면 그 전 메모리의 마지막 값을 main memory에 저장한다.

Ex. x에 a, b, c를 저장한 후, cache에만 업데이트 하고 x에는 c만 남아있다. 그러다 CPU가 y에 d를 저장하라고 하면 main의 x에 c를 쓴다. (x에서 y로 저장할 cache memory가 달라짐)

• data-write hit
• cache 안에 있는 block만 업데이트
• 쓰는 메모리가 변경될 때
• main memory에 아까 쓴 내용들을 저장한다. 여기서도 write buffer를 사용함.

보통 더 빠르지만 더 복잡하다. (쓰기 전에 이전 값이 있었는지 확인해야 하기 때문에 먼저 감지하고 써야 한다.)

 

Write allocation

write miss가 발생했을 때

• write-through
  • allocate on miss : block 정보를 main에서 가져온다.
  • write around : block을 가져오지 않고 바로 main에 써버린다.
• write-back
• 보통 block을 main에서 가져온다.

** Intrinsity FastMATH

MIPS processor 중의 하나임.

12-stage pipeline으로 구성되어 있고, 각 cycle의 instruction, data에 접근하는 역할을 한다.

I-cache, D-cache로 나뉘어 있다.

각각 16KB로, 256blocks * 16 words / block 으로 구성되어 있다.

16KB = 16 * 1024 Bytes = 2^14 bytes

256 blocks = 2^8 blocks

16 words / block = 2^6 bytes / block

D-cache는 write-through 방식 혹은 write-back 방식을 사용한다.

주로 I-cache miss rate 보다 D-cache miss rate 가 더 크다.

 

Cache Performance 측정

CPU time = CPU 실행 시간 + memory-stall 시간

• program execution cycles (cpu execution time)
• cache hit time 포함
• memory stall cycles
• cache miss로 인한 stall cycle

data memory stall cycles

= data memory accesses / Program * Miss rate of data memory * Miss penalty by main memory

instruction memory stall cycles

= all instructions / Program * Miss rate of instruction memory * Miss penalty by main memory

Ex. I-cache miss rate

Miss cycle per instruction

• I-cache = I-cache miss rate * Miss penalty
• D-cache = D-cache miss rate * Load&stores' ratio of insturctions * Miss penalty

Actual CPI

= base CPI + I-cache miss cycles + D-cache miss cycles

(여기서 miss penalty의 크기가 큰 영향을 끼친다.)

1GHz → 2GHz ⇒ 100 cycles → 200 cycles

 

Average Memory access Time

AMAT (Average Memory Access Time) = HIt time + Miss rate * Miss penalty

 

Associative Caches

Direct-mapped 방식은 다른 곳이 다 비어있어도 정해진 곳에만 들어갈 수 있었음

• Fully Associative더 유연하고, miss rate가 감소한다.
• but 모든 공간들을 한 번 확인해야 함 → 많은 circuit, 비교가 필요하다.
• 어떤 cache 부분에도 들어갈 수 있다.
• M-way AssociativeBlock number가 어디 set을 봐야 하는지 결정한다. (Block number % number of sets in cache)Fully associative 보다는 비용이 더 싸다.
• 모든 entries들은 한 번씩 확인해야 한다.
• 각 memory는 M entries로 구분되어 있다.

 

Replacement Policy

Direct-mapped : 오로지 겹치는 위치를 대체하는 것만 가능

Set associative

• 일단 빈 것부터 채운다.
• 다 차있는 경우
  • Least-recently used (LRU) - 가장 덜 쓰인 것
  • 가장 오래 전에 사용됐던 것을 선택 (bit를 이용해서 가능한데, 정교한 시간 측정을 위해 bit를 더 많이 사용하게 되면 오히려 메모리 낭비가 된다.)
  • Random - 랜덤으로 삭제

 

Encoding / Decoding

• offen used forencryption / decryptionmodulation / demodulation
• compression / decompression
• error detection / correction
• error가 발견되었을 경우
  • 에러 고치기
  • 처음부터 다시 시도하기

original data - encoding → encoded code - storage or communication → received code → if error : ditect error

 

The Hamming Code

Hamming distance

두 bit patterns 중에 다른 부분이 몇 곳 있는지 표현

Minimum distance = 2

하나의 bit가 에러가 났을 때 감지 가능

맨 마지막에 parity bit 추가. (1이 짝수면 0, 1이 홀수 개면 1)

🤔 2bit 동시 에러, 짝수 개의 bit가 에러, 2개 이상의 bit 에러는 감지할 수 없다.

Minimum distance = 3

1개 비트가 오류나면 고칠 수 있고, 2개 비트가 오류나면 감지할 수 있다. ( 그 이상은 불가능)

→ Hamming ECC code

 

Encoding Hamming ECC code

data bits 는 d로, parity bits는 p로 표시한다.

parity bits의 위치는 2의 제곱 번째이다.

각 parity bit는 자신의 위치부터 시작해서 2, 4, 8 ... 부분을 확인한다.

Ex. p1 : 1,3, 5, 7, 9, 11 → 1개씩 확인

p2 : (2, 3), (6, 7), (10, 11) → 2개씩 확인

... → 4개씩 확인

** 마찬가지로 parity bit는 1의 개수를 짝수로 맞춰주는 역할을 한다.

 

Decoding Hamming SEC

parity bits를 decoding 한다.

parity bit 담당 부분의 1을 세어서 홀수면 1, 짝수면 0을 넣는다.

모두 0이면 정상이다.

그런데 만약 오류가 생겨서 parity bits의 값이 0111 이라는 결과가 나온 경우, 7번째 bit가 문제가 있다는 것을 알 수 있다. (2진수로 계산)

 

Two-bit errors in Hamming SEC

error가 2개 bit에서 발생하면 parity bit가 0000이 아니라서 에러임은 확인할 수 있으나, 더 이상 parity bit로는 어디에서 에러가 났는지 알 수 없다.

 

SEC/DED code

추가적으로 parity bit 한 개를 더 쓴다. (Pn → 맨 끝에 위치)

Pn은 전체 코드의 1의 개수를 세는 parity code이다.

H = SEC parity bits 일 때,

H 짝수 H 홀수

Pn 짝수	에러 없음	double error
Pn 홀수	Pn 에러	수정 가능한 1개 에러

parity bits 개수 계산

p : parity bits 개수, d : 확인해야 할 data bits 수

2^p ≥ p + d + 1 ← 여기서 1은 마지막 DED 코드 parity 의미

p ≥ log(p+d+1)

ECC DRAM은 SEC/DED를 사용한다. (64bits 당 parity code 8개)

Ex. 8 bits data ⇒ 12 bits code

 

Problems

** 지금까지는 main에서 프로그램 1개만 돌린다고 가정하였음.

1. 똑같은 프로그램이 두 개의 창에서 동시에 돌아갈 경우, 한 프로그램의 메모리를 공유해야 한다.
2. → 어떻게 할 것인가?
3. 동일한 프로그램을 환경이 다른 (RAM이 작거나, 큰 경우) 컴퓨터에서 돌아가게 하고 싶다.
4. → 즉 actual memory address 없이 프로그램을 만들 수 있을까? (프로그램에서 메모리 크기를 신경쓰지 않고 메모리에 쓰고 싶다!)

Ex.

32bit computer로 가정했을 때, memory address는 4GB까지 가능하다.

Program A와 B 모두 4GB 메모리가 최대이다.

main memory에 가져올 수 있는 프로그램의 크기는 한정적이다. (컴퓨터마다 다름)

→ 그러므로 가져올 수 있는 만큼만 가져오고 나머지는 disk의 fake main memory에 담는다. 해당 부분이 필요할 때만 여기에 접근하여 찾는다.

 

Virtual Memory

가상 메모리를 사용하면 모두 해결 가능하다.

main memory를 disk를 위한 cache로 사용한다고 가정한다. 여러 program들에서 사용되는 가상 메모리의 주소 값은 겹칠 수 있으나, 실제 physical memory address 값은 절대 겹치지 않는다. (OS에 의해 가능) 한정된 프로그램만 main memory에 가져오고, 나머지는 disk 의 fake main memory에 따로 담아놓는다.

Program은 개인 가상 주소 공간을 각각 가지고 있다. 가상 주소는 physical address로 변경된다.

CPU, OS는 가상 주소를 physical 주소로 변경한다.

block of virtual memory : page

miss of virtual memory : page fault

page fault 나면 disk까지 갔다 와야 돼서 시간이 엄청 오래 걸린다.

• Relocation
• ? 뭔소린지 모르겠음

 

Address Translation

page offset 크기 : page의 bytes 크기 (Ex. page 크기가 4KB면 12 bit)

Physical address는 주로 30bit 정도로 주어지는 듯? (아닐 수도 있음)

 

Page Tables

virtual page number로 index된다.

Page table register는 physical memory에 있는 page table을 가리킨다.

• page가 메모리 안에 존재할 경우그 외 valid, dirty, referenced..
• Page table entry는 physical page number를 저장
• page 가 메모리 안에 존재하지 않는 경우 (page fault)
• disk 안에 있는 swap space에서 위치를 가져온다.

** 유의 **

프로그램 마다 페이지 테이블이 존재한다.

page table register는 어떤 페이지 테이블로 가야하는지를 가리킨다.

Replacement and Writes

page fault rate를 낮추기 위해서는 LRU replacement를 채택하면 좋다.

사용했는지 여부를 표시하는 bit를 page에 접근할 때 1로 바꾸고, 시간이 지날 때마다 0으로 변경한다.

write-through는 너무 느리므로 write-back을 사용하는 것이 좋다.

Fast Translation Using a TLB

Page table이 main memory에 있어서 엄청 느리다. → TLB라는 page table 전용 cache를 사용한다.

page table의 일부를 저장하여 access 속도를 빠르게 한다.

TLB Misses

• TLB missmemory에서 값을 가져와서 TLB에 복사한 후 instruction 재시작
• OS, HW에서 처리할 수 있다.
• page가 메모리 안에 있지만, TLB 안에는 없음
• page fault
• page가 memory 안에 존재하지 않음. OS는 page를 disk에서 가져오고, page table을 업데이트 한다.
• Page Fault Handler (OS가 수행)disk에서 page 찾기memory에서 page읽어오고, page table 업데이트 하기
• faulting instruction 부터 재시작하기
• 대체할 page 선택하기 (write back 사용)
• use faulting virtual address to find PTE

TLB and Cache Interaction

TLB hit → Cache hit → 빠름

TLB miss → Page table hit → Cache hit → 느림 (page table 때문에)

이를 해결하기 위해 Cache의 주소는 virtual address tag 를 사용하게 한다. (but virtual address가 모든 process에서 같은 주소를 가질 수 있기 때문에 어떤 process의 주소값인지를 구분하는 게 필요 → 복잡함)

Cache Coherence Problem

CPU core는 각각 자기 만의 Cache를 갖지만, main memory는 공유한다.

이때 A에서 Cache에 write-through 방식으로 data를 쓴다면, A의 Cache와 Memory는 값이 같지만 다른 core B는 Memory와 다른 값을 갖고 있을 수도 있다.

→ Invalidating Snooping Protocols (모든 core에서 해당 데이터를 제거하고 다시 쓴다)

 

 

 

 

여담)

이번 학기 컴구 공부에 많이 소홀해서 제대로 공부하지 못한 것 같다.

만약 재수강 가능하면 다시 듣고 싶다.