캐시란?
프로세서에게 데이터를 빠르게 전달하기 위한 보조 저장장치이다.
미래의 요청에 대비하여 데이터를 미리 저장하는 방법으로 프로세서에게 데이터를 빨리 전달할 수 있다.
보통 프로세서와 메인 메모리 사이 계층에 존재하며 메모리 계층 구조에서 가장 높은 곳에 위치한다.
Direct mapped cache
메모리 주소에 따라 캐시 내 위치를 지정한다.
데이터를 저장할 위치는 아래 연산에 따라 주소를 구한다.
(block address) modulo (캐시 내 블록 개수)
따라서 주소를 정할 때 무조건 한 가지 경우의 수밖에 없다.
이 때 tag 와 valid bit 를 이용해서 특정 블럭에 캐시 데이터가 있는지 없는지를 구분한다.
tag
만약 크기 8 캐시에 데이터를 저장하려는데 본래 주소가 9였다면 캐시의 001 위치를 고르게 된다. 그런데 캐시 입장에서 보면 원래 주소가 9인지 17인지 구별할 수 없다.
따라서 원래 어느 주소에서 데이터가 왔는지 저장해야 한다.
주소의 모든 비트를 저장할 필요는 없고, 상위 비트 몇 개만 저장하면 된다. 이것을 tag라고 한다.
valid bit
tag가 garbage값인 경우가 존재하므로 해당 캐시 블록에 실제로 데이터가 존재하는지 아닌지 구분하기 위해 valid bit 를 활용한다.
캐시 테이블 작성
- 블럭 인덱스 확인(하위 3비트)
- 태그 확인(상위2비트)
- 둘 다 맞으면 hit, 틀리거나 데이터가 없으면 miss
- 기재하려는 데이터 내용 작성
- 사용할 수 있는 데이터면 valid bit를 Y로 변경
address subdivision
Multiword cache
한 개의 캐시 블럭을 멀티워드 로 구성해서 한 번에 많은 데이터를 가져와 오버헤드를 줄이는 방법이다.
효율적으로 보일 수 있지만 가져온 데이터를 전부 사용하지 않는 경우 비효율적일 수도 있다.
- 범위에 속하는 데이터를 가져오는데, 대부분이 프로그램이 spatial locality를 따르므로 정확한 데이터를 가져올 가능성이 높다.
- 캐시의 크기는 무한하지 않다는 제약이 있다.
- 블럭 크기가 줄어들면 블럭 개수가 줄어들고 더 많은 데이터가 단일 블럭에 집중된다. 이 때
competition이 증가해 데이터를 잘못 가져올 확률이 높다, - 캐시에 사용되지 않는 데이터가 쌓인다. 즉
pollution이 높아진다. - 캐시가 미스되었을 때 패널티가 커진다.
miss rate 는 캐시 사이즈에 따라 점점 줄어들다가 일정 수준 이상에서 오히려 증가한다.
Instruction cash fetch steps
- 명령어 캐시에 주소값을 보낸다.
- 해당하는 엔트리의 tag, valid 조건이 만족하는지 확인한다.
- cash hit인 경우 데이터를 돌려주고 miss인 경우 하위 레벨 메모리에서 데이터를 가져올 때까지 기다린다.
- 메모리를 가져온 경우 캐시 테이블을 업데이트한다.
- instruction fetch를 재개한다.
데이터 캐시 write
만약 데이터에 무언가를 write하려는 상황에 해당 데이터가 이미 캐시에 존재한다면 다른 절차 없이 바로 블록을 업데이트하면 된다. 그런데 이 경우 캐시의 데이터와 하위 메모리의 데이터가 일치하지 않게 되는 문제가 생긴다.
해결 방법에 대해 알아보자.
Cache hit의 경우
- 메모리를 곧바로 업데이트한다. (write-through)
실행시간이 길어지는 문제가 있다. - write buffer를 활용한다.
이 경우 DRAM에 데이터를 반영할 때까지 기다리지 않고 버퍼에 맡기는 것이다. 하지만 언젠가 write buffer의 용량이 다 찬다면 역시 비슷한 문제가 발생할 수 있다. - 캐시만 업데이트한다. (write-back)
dirty bit를 도입해서 캐시와 메모리의 데이터가 다르다는 것을 명시한다.
해당 블록을 다른 메모리 블록으로 교체하려고 할 때 하위 메모리를 업데이트한다.
Cache miss의 경우
프로세서가 캐시에 데이터를 작성하려고 했는데 해당 캐시가 데이터 캐시에 존재하지 않는 경우 먼저 하위 메모리에서 데이터를 가져오는 과정을 거쳐야 한다.
이것을 write allocation 이라고 한다.
이 경우 캐시에 데이터를 불러오지 않고 바로 메모리에 데이터를 업데이트할 수도 있다. (no write allocation 또는 write around)
캐시의 성능 측정
CPU 타임은 기본적으로 프로그램 실행 시간 + stall 시간으로 이루어져 있다.
이 중 memory stall cycles = miss 개수 * miss 패널티
miss penalty란?
한 번 미스가 발생할 때마다 걸리는 시간을 말한다.
이 때 miss 개수는 전체 메모리 접근 * miss rate이다.
따라서 식을 정리하면 다음과 같다.
Memory accesses Miss rate Miss penalty
= #Inst #Miss/#Inst Miss penalty
예를 들어 base CPI=2, I-cache miss rate = 2%, D-cache miss rate = 4%,
miss penalty = 100 cycles, L/S가 전체 명령어의 36%라고 해보자.
전체 명령어 개수를 I라고 하자.
먼저 명령어 miss의 경우 I 0.02 100(penalty) = I 2
데이터 miss의 경우 I 0.36 0.04 100 = I * 1.44
I-cache의 경우 명령어 miss이므로 모든 명령어에 해당,
D-cache의 경우 데이터 관련 명령어에만 miss이므로 전체 명령어 * 0.36 해줘야 함
그러면 CPI = 2 + I 2 + I 1.44 가 되는데, CPI라는 것이 명령어 당 사이클을 의미하므로 I는 수식에서 제외한다. 따라서 2 + 2 + 1.44 = 5.44
메모리 접근 시간 + clock frequency가 주어진 경우 둘을 곱하면 miss penalty이다.
캐시 성능 개선
Associative caches
direct-mapped 방식은 miss rate가 높은 편이다.
왜냐하면 여러 개의 메모리 블록이 하나의 캐시 슬롯에 매핑되어 서로 충돌하기 때문이다.
캐시에 자리가 많이 남아 있는데 여러 블록이 한 자리를 두고 경쟁하면 miss rate가 높아진다.
이럴 때 사용할 수 있는 것이 Fully Associative 캐시이다.
이 방식을 활용하면 메모리 블록을 아무 캐시 엔트리에나 매핑할 수 있다.
특정 블록이 캐시의 어느 부분에 들어가있는지 확인하기 어렵다는 단점이 있다.
n-way set associative
어떤 메모리 블록이 들어갈 수 있는 캐시 슬롯이 n개라는 뜻이다.
direct mapped와 fully associative의 중간에 있는 개념이다.
예를 들어 2-way라면 하나의 슬롯 당 2칸을 가진다.
캐시 사이즈가 8이라면 0-1, 0-2, 1-1, 1-2...같은 식으로 4개 슬롯이 존재한다.
만약 메모리 주소가 12라면 12 mod 4를 해서 0번 슬롯의 1번째 혹은 2번째 칸에 들어갈 수 있다.
Replacement policy
캐시 슬롯이 차있을 경우 기존 슬롯의 데이터 중 어떤 것을 삭제할지 정하는 방법을 알아보자.
LRU
가장 오래전에 접근한 데이터를 삭제한다.
temporal locality를 살릴 수 있지만, 데이터에 언제 접근했는지 기록하고 비교해야 하기 때문에 n-way에서 n값이 커질수록 구현이 어려워진다.
Random
랜덤한 데이터를 삭제한다.
슬롯 크기가 커질수록 랜덤 구현이 더 효율적일 수도 있다.
