[Computer Architecture] About Cache
Memory(메모리) 란,
data를 저장할 수 있는 모든 장치를 의미한다.
세상에 존재하는 메모리들은 속도와 크게 따라 여러 레벨로 구분할 수 있다.
우리는 이를 Memory Hierarchy(메모리 계층)으로 나눈다.
우리가 중점적으로 다룰 Cache는 register 보다는 하위, Main Memory(이하 MM)는 상위 레벨이다.
메모리 계층은 영원하지 않다. 새로운 기술이 나오면 언제든지 변할 수 있다.
(작고 크다는 것은 "같은 가격 대비 살 수 있는 메모리의 양"을 의미한다.)
Cache Memory 은
느린 메모리의 access time을 향상시키 위해 일시적으로 data를 저장해두는 빠르지만 작은 memory이다.
Transparent의 특성을 지니는데,
CPU는 Cache가 존재하는지에 대한 여부를 알 수 없다는 의미이다.
이를 CPU에 대해 transparent 하다고 이야기한다.
CPU와 Storage, 즉 Main Memory 사이에 Cache가 한 개 이상이 존재할 때
이 구조의 최종 목표는 Main Memory에 데이터를 원하는 송신이 닿지 않는 것이다.
누군가가 물어볼 수도 있다.
"그렇게 하지말고, Memory를 쓰지 않고 Cache를 처음부터 쓰면 해결되지 않나요?"
그렇다면 답변은,
"Cache가 더 비싸서 Cache만 쓸 수 없습니다." 이다.
소비자에게 일반 성능을 지닌 300만원짜리 컴퓨터를 판다면 구매하겠는가?
Cache가 Memory보다 비싸서 조금만 쓴다.
이러한 구조는 Correctness에는 영향을 주지 않는다.
그저, 성능에만 영향을 준다.
CPU와 Main Memory 사이에 cache가 늘어날수록,
memory로 갈 확률이 현저히 낮아진다.
Cache의 기본 원리 는 "Locality"라는 원리다.
이 원리는 두 개의 종류로 나뉜다.
"한 번 접근한 데이터에 조만간 다시 가는 경향이 존재한다."
-> Temporal locality
"가까이 두는데 자주 써야 의미가 있다."
-> Spatial locality
Cache 용어 를 이제 알아보자.
Block(or line)은 정보의 최소 단위를 의미한다.
즉, 캐시 관점에서 데이터를 주고 받는 단위를 말한다.
Hit은 데이터가 상위 레벨에 존재하는 경우를 말한다.
processor가 memory에 특정 주소의 data를 요청한다.
이 때 가장 높은 level의 memory에서 제일 먼저 찾는다.
여기에 processor가 요청한 데이터가 있다면 이를 Hit 이라고 한다.
그리고 upper level의 메모리, 즉 바로 다음 메모리에 원하는 값이 없다면 Miss 라고 한다.
Hit rate(hit ratio)은 읽기 시도 중 hit이 발생한 비율을 이야기한다.
반대로 miss 발생 비율을 Miss rate를 말한다.
Hit time은 Hit 하는데에 걸리는 시간을 이야기한다.
(이는 hit인지 miss인지 결정하는 시간도 포함한다.)
Cache가 중간에 있는 구조면 메모리까지 가지 않는 것이 목표인데,
Miss penalty이면 메모리까지 가는 것을 의미한다.
Cache에서 Miss가 발생하면 Main memory까지 가서 데이터를 가져온 다음,
Cache를 업데이트 하고, CPU까지 가져가야 한다.
이 때 걸리는 시간을 Miss penalty라고 한다.
Block size가 클수록 Miss penalty가 커진다.
miss는 거의 일어나지 않기 때문에,
miss penalty를 줄인다 하더라도 hit time을 줄이는 것에 비해 성능 향상 정도가 작다.
첫 번째, CPU는 한 번에 1 word씩 요청을 한다고 가정을 하자.
두 번째, blcok size가 1 word라고 가정을 하자.
memory에 access를 해서 가져온 data를 cache에 저장하는데 이 때 어떤 순서로 정할지에 대한 방법이 필요하다.
-> Cache placement issue
모두 다 차 있으면 누군가를 'evict'(쫓아냄) 해야 한다.
Direct-mapped cache 방법이 존재한다.
이 방법은 메모리 data를 더 높은 레벨인 cache로 올릴 때 어떻게 data를 배치할 것인가 대해 정한 방법 중 하나이다.
Cache location을 memory address의 LSB bits를 이용해 결정한다.
이로 인해 block이 cache에서 오직 정해진 곳만 갈 수 있다.
(이와 반대되는 방법이 fully associative cache)
Cache slot(캐시 내에서의 위치) = [word address = 메모리 내의 Block 위치] mod [# of cache blocks = 캐시의 Blcok의 개수]
(mod 는 나머지 계산)
일단, 말로 위 그림을 다시 설명해보자.
위에서 말했듯이 memoery address의 LSB bits를 이용해 Cache에 올릴 block의 위치를 정한다고 했다.
Cache는 3비트 주소를 사용하고, 메모리는 5비트를 사용한다.
Direct-mapped cache는 캐시의 특정 공간을 메모리의 특정 공간만 들어올 수 있도록 하는 것이다.
이 경우에는 메모리 주소의 하위 3비트가 block이 캐시로 올라갈 때 캐시에서의 주소가 된다.
즉, 위 그림에서 001, 101의 index 위치가 blcok의 캐시 위치가 된다.
이렇게 정렬을 해서 캐시 내에서 Hit/Miss 판단을 빠르게 한다.
(Direct-mapped cache에는 빈 공간이 발생해 공간 활용이 잘 되지 않는 단점이 존재한다.)
여러 개의 block의 cache의 한 location으로 mapping 된다.
00001, 01001, 10001, 11001은 Cache의 001 block으로 mapping이 된다.
Cache의 001 block에 저장된 value가 어디서 왔는지 알 방법도 필요하다.
따라서 이용하는 것이 tag bit 라는 것이다.
tag bit는 address의 high-order bits 즉, 최상위 비트이다.
00001, 01001, 10001, 11001 이다.
valid bit 는 Cache에서의 특정 박스에 유효한 값인지 확인해주는 bit이다.
valid bit가 1이 되면 실제 caching된 data이고,
valid bit가 0이 되면 garbage value가 된다.
Address Subdivision
address를 나타내는 비트는 tag part와 index part로 나누어진다.
cache slots(캐시의 index 개수, 칸 개수)의 숫자는 1024라고 가정을 한다.
cache slot을 구분할 수 있는 index part는 10 bit이기 때문이다.
(2의 10승은 1024가 되는데, 이와 연관 관계가 있다고 받아들이고 있는 중이다.)
byte size가 4 byte라고 가정을 해보자.
address는 byte 단위로 접근을 할 수 있어야 하기 때문에,
byte를 구분하는 byte offset은 size는 2 bit가 된다.
(위와 같이 이 경우도 2의 2승이 4이므로 그렇게 연관 관계가 있다고 받아들이고 있다.)
위 12bit는 cache에 저장하지 않는다.
이 비트들은 특정 byte를 지정하는 주소가 된다.
따라서, address의 64 bit 중 위 두 부분을 합친 12 bits를 제외한
나머지 52 bit가 tag part가 된다.
tag part는 cache 내의 위치를 가리킨다.
그리고 cache의 size는
저장할 수 있는 cache의 Data 부분의 size를 이야기한다.
위 그림을 예로 들자면,
Data 부분이 32bit, 즉 4 bytes가 된다.
따라서 위 cache의 sizesms 4KB가 된다.
적용할 겸에 문제도 한 번 풀어보자.
예제 1)
address의 비트 수는 64 bits이다.
cache slot의 개수가 1024이고,
cache size가 8KB 일 때,
tag part의 bit size는?
sol 1)
일단 cache slot의 개수가 1024이기 때문에 index part의 bit 개수는 10개이다.
cache size가 8KB 이므로, byte offset은 3 비트이다.
따라서 64-10-3 = 51 이 된다.
예제 2)
address의 비트 수는 64 bits이다.
cache size가 4KB 이고,
cache slot의 개수가 512 일 때,
tag part의 bit size는?
sol 2)
cache slot의 개수를 결정하는 것은 index part 인데,
512가 2의 9승이라 9 bit이다.
64-2-9 = 53이 된다.
block offset이라는 개념도 존재한다.
Cache 내 Data 영역에 1 word(4 btye) 크기의 data가 들어간다고 가정하면,
앞 전에서 이야기 했던 LSB 2bit가 byte offset이 된다.
그렇다면 Data 영역에 2 word(8 byte) 크기의 data가 들어간다고 가정하면,
LSB 3bit가 사용된다.
가장 왼쪽 두 개의 비트를 제외한,
다른 한 비트를 우리는 block offset이라고 한다.
아래를 참고해보자.
우리는 위의 정보들로
Cache의 총 bits 수를 알아볼 수 있다.
valid bit는 1bit,
tag bits는 64bit에서 index bits의 개수(좌측에선 n)와 block offset의 개수(좌측에선 m)와
byte offset의 개수, 2를 뺀 값이다.
data bits는 2의 m 승 곱하기 32의 값이다.
Cache의 총 bits 수는
2^n X (1+(64-(n+m+2))+2^m X32) 이다.
blcok size는 작지만, cache slot이 많은게 좋을까?
아니면,
block size는 크지만, cache slot이 작은게 좋을까?
Block SIze와 Miss Rate 에 연관된 사항들을 확인 해보자.
위 그래프를 보면,
cache size를 점점 크게 할 수록, miss rate의 감소율이 점점 줄어든다.
miss rate를 더 줄이기 위해 cache size를 무작정 크게 할 수는 없다.
계속 크게 해봐야 miss rate가 줄어드는 정도는 비효율적일 정도로 미미하다.
중간이 가장 좋다.
왜 중간이 좋냐고 물어보면, block size에 관련된 사항을 확인해보자.
block size가 작을수록, 주변의 data를 많이 저장하지 못하기 때문에 spatial locality의 활용도가 낮아진다.
blcok size가 클수록, 전체적인 data를 저장하지 못하기 때문에 temporal locality의 활용도가 낮아진다.
위 그래프를 봐도 확인할 수 있다.
위에서 이야기 했던 것인데,
miss penalty란,
main memory에서 cache로 block을 load하는데 걸리는 시간이다.
set-up time(메모리 안에서 찾는 시간) + transfer time 이다.
miss가 거의 발생하지 않더라도, 한 번이라도 발생하면 매우 많은 시간이 걸리기 때문에 miss penalty를 줄이는 것이 필요하다.
set-up time은 메인 메모리 내부에서 값을 찾고 하는 등의 시간이라 메인 메모리를 바꾸는 방법을 택하지 않는다면,
set-up time을 개선하기는 쉽지 않다.
그러면, 우리는 transfer time을 건드려봐야한다.
원래 이것도 고정된 값이라 실제로 줄이진 못하고 여러 방법을 통해 소모 시간을 줄일 수 있다.
우리는 transfer time을 숨기는 것이라고 이야기 한다.(hiding the transfer time)
첫 번째, early restart 기법이다.
main memory에서 block을 load 할 때,
첫 번째 data가 load되면 program을 시작해 실행 중에 나머지 data를 병렬적으로 load하는 기법이다.
instruction data와 같은 순차적으로 접근해야 하는 data에 적용하면 빠르다.
두 번째는 critical word first 기법이다.
early-restart 에서 첫 번째 word가 아닌,
필요한 즉, critical 한 word를 먼저 load 하는 기법이다.
instruction 말고 일반 data들은 순차적을 접근하지 않는 경우가 많아 중간의 값을 요구할 수 있다.
Intel core i7 Block Diagram 을 알아보자.
실제 Cache들은 이렇게 multiLevel로 구성된다.
각 process는 고유의 L1, L2 cache를 가지며, L3 cache를 공유한다.
L1, L2는 한 core가 전용으로 사용하고, L3 cache는 shared cache이다.
위에서 miss penalty를 줄이기 위한 기법 두 가지가 존재했는데,
그래서 L1을 보면 instruction data와 일반 data를 구분한 것을 볼 수 있다.
L1 cache는 instruction cache 와 data cache로 분리되어 있다.
Cache Miss Handling in Processor
instruction을 읽을 때 miss가 발생했을 경우 어떤 일이 발생하는지 보자.
(일반 data miss도 유사하다.)
instruction cache에서 miss 난 경우에는 instruction register의 내용은 invalid이다.
필요한 instruction을 가져오기 위해, 하위 계층의 memory에게 read를 수행하라고 명령해야함.
miss가 발생하기 이전 excution의 첫 번째 cycle에서 PC+4가 되었기 때문에,
PC-4가 필요한 instruction의 address이다.
하위 계층의 memory에 해당 address를 보내고,
data를 read 해오면 cache에 올린다.
순서 정리를 하면 다음과 같다.
1. 하위 계층의 memory에 PC-4를 전송
2. 하위 계층의 memory가 read를 수행하도록 명령
3. data가 준비될 때까지 대기
4. 가져온 data를 cache entry에 write, tag와 valid field 채우기
5. instruction address를 다시 memory에 전송 -> 이번에는 cache에 해당 address의 instruction이 존재 -> Hit!
Write Handling in Cache
Cache가 Write를 다루는 방법이 두 가지가 있다.
(Cache에 Data를 올리는 방법이다.)
write-through cache
sd instruction은 data cache에 data를 write한다.
이 때 data cache와 main memory와 다른 값을 가진다.
우리는 이를 cache와 memory가 inconsictent 하다고 한다.
cache와 memory를 consistent 하게 유지하는 방법은
cache와 memory 둘 다 모두 data를 write 하는 것이다.
write-through cache는 항상 cache와 main memory 둘 다 update 한다.
이를 통해 data consistency가 유지된다.
하지만 항상 main memory에 access를 하면 속도가 매우 느려져 write buffer를 사용한다.
MM에 접근하는 것은 Cache를 사용하는 이점이 사라진다는 단점으로 된다.
write-back cache
새로운 value가 cache에만 write 된다.
수정된 block은 교체될 때 main memory에 write 된다.
main memory에 매번 access 하지 않아도 되기 때문에, 빠르게 write 할 수 있다.
하지만 data consistency가 보장되지 않는다.
따라서 correctness 문제가 발생할 수 있다.
하지만 write-through 보다 구현하기 복잡하다.
dirty bit를 사용하여 메모리가 수정되었는지 확인한다.
cache performance 를 향상시키기 위한 방법 에는 두 가지가 존재한다.
(1) 두 개의 다른 block이 cache의 같은 location에 load 될 가능성을 줄여 miss rate를 줄인다.
(2) hierarchy에 추가적인 level을 더해 miss penalty를 줄임 -> multi-level caching
CPU time = total clock cycles x clock cycle time
여기서 우리가 배우고 있는 Cache를 추가한다면 Cache에서의 작업 처리를 위한 추가적인 cycle을 고려해야한다.
즉, total clock cycles = CPU execution cycles + Memory stall clock cycles
이 된다.
CPU execution cycle은 cache access가 hit 했을 때 소모되는 시간,
즉 cache hit time 또한 포함된다.
Memory stall clock cycles은 다음과 같이 또 나눠진다.
Memory stall cycles = Read stall cycles + Write stall cycles
Read stall cycles은 다음과 같이 계산할 수 있다.
read stall cycles = (reads/program) x read miss rate x read miss penalty
Write에서의 cycle 계산은 쉽지 않다.
write-through : write buffer가 가득 찬 경우, buffer에 자리가 날 때까지 stall
write-back : block이 replace 되는 경우, MM에 write 하는 동안 stall
write buffer를 예측하기 쉽지 않고, write-back 방식에서도 모두 고려할 수 없다.
따라서 복잡한 부분을 다 제외한 후 read와 write miss peanlty가 같다고 가정해서 간단하게 아래와 같이 계산한다.
memory stall cycles = N X (memory access / N) X miss rate X miss penalty
여기서 N은 instruction의 개수이다.
Associative Cache 의 종류에는 세 가지가 존재한다.
Direct-mapped cache / Set associative cache / Fully associative cache
이렇게 세 가지이다.
Direct-mapped cache는
block이 cache의 한 위치에만 load 될 수 있다.
Fully associative cache는
block이 cache의 어디에서나 load 될 수 있다.
block이 cache의 어디에나 갈 수 있기 때문에, cache의 모든 block의 tag를 찾아야한다.
Set associative cache는
block이 cache의 set 중 어디에서나 load 될 수 있다.
block이 set의 어디에나 갈 수 있기 때문에 set의 모든 element의 tag를 찾아야한다.
Fully associative cache와 Direct-mapped cache는
Set associative cache의 한 종류인 것을 알 수 있다.
direct-mapped은 1-way set associative cache가 되고,
fully associative는 n-way set associative cache가 된다.
Set associative cache는 쉽게 말해서 direct-mapped cahce를 옆으로 n개 이어붙였다고 생각하면 된다.
cache에서 한 Set의 크기를 n이라고 할 때 이를 associativity라고 한다.
이 n의 증가/감소에 따라 장단점이 존재한다.
일단 먼저 1-way set associative cache(directed-mapped)과
n-way set associative cache(fully associative)를 비교해보자.
각각의 cache가 동일한 개수의 data를 담는다고 가정할 때,
directed-mapped는 fully associative에 비해 비교적 비효율적으로 담을 가능성이 높다.
fully associative는 다 채운다고 해도, directed-mapped는 다 채우기도 전에 기존 data는 쫓아내고
그 위에 덮어쓰기를 할 수도 있다.
따라서, 같은 용량의 Cache라고 할지라도 fully associative가 더 많은 데이터를 담고 있을 확률이 높다.
이를 통해 associativity가 높을수록, Miss rate가 작다는 것을 알 수 있다.
Set의 크기가 늘어나면 Hit 판단을 위해 찾아야 할 Set 개수가 늘어남과 같다.
따라서 Hit time이 늘어나고, H/W cost 또한 증가한다.
associativity가 높을수록, Hit time이 증가하고, H/W cost 또한 증가한다.
Multi-level Cache
대부분의 현대 processor은 여러 level의 cache를 가진다.
여러 level의 cache를 사용하면 Miss penalty가 줄어든다.
L1이 CPU에 가장 가까운 Cache이고, L3은 MM와 가장 가까운 Cache이다.
L1부터 L3까지 모두 Cache이므로 SRAM을 기반으로 하지만, 종류에 따라 특성이 다르다.
L1 Cache : CPU와 가장 가까이 있기 때문에 hit time이 가장 빨라야 한다.
그래서 작고 빠른게 좋다.
miss penalty를 줄이기 위해 작은 block size를 사용한다.
주로 direct-mapped cache를 사용한다.
L2 Cache : 속도보다는 miss rate가 낮아야하기 때문에, 큰 block size를 사용한다.
주로 set-associative cache 또는 fully associative cache이다.
L3 Cache : MM과 가장 가까워 큰 것이 좋다. 속도의 중요성은 위 Cache보다 조금 떨어진다.
MM으로 넘어가지 않게 하는 것이 중요하기 때문에
조금 느려도 miss rate를 줄이는 것이 좋기 때문에 full associative cache가 적합하다.
Multi-level Cache 성능을 계산해보자.
먼저 조건은 위와 같다.
먼저 L1 Cache만 존재하는 경우를 알아보자.
Avg CPI = 1 cycle x 1.0(<-확률을 의미) + 400 cycles(Clock rate x Main memory access latency) x 0.02(L1의 Miss rate) = 9
miss penalty는 100ns이고, 이를 clock cycle 개수로 바꿔보면,
clock rate가 4GHz 이므로 400 cycle이 mis penalty 임을 알 수 있다.
다음으로 L2 Cache도 존재하는 경우를 알아보자.
L1 -> L2로 접근하는 시간 : 5 ns
L2 -> MM으로 접근하는 시간 : 100 ns
L1 miss rate : 2%
L2 miss rate : 0.5%
(전체 instruction 중 0.5% 인지, 아니면 L2 cache로 들어온 instruction 중 0.5% 인지 구분하는 것이 중요하다.)
Avg CPI = 1 cycle x 1.0 + 20 cycles(4GHz x 5ns) x 0.02 + 400 cycles(4GHz x 100ns) x 0.005 = 3.4
두 가지 경우를 비교하면
9 / 3.4 = 2.6
L2 Cache가 존재하는 경우가 L1 Cache만 존재하는 경우보다 2.6배 빠르다.