CSAPP (p.650 ~ 675)
6.4 Cache Memories
캐시에서 데이터를 찾는 과정
set selection:set index bits를 사용해서 데이터 블록이 매핑되는set을 찾음line matching:valid bit와tag bits를 사용해서 캐싱 라인을 찾음word selection: 데이터가 포함된 캐싱 라인이 존재하는 경우block offset bits를 사용해서data word를 찾음
캐시 종류
캐시는 하나의 set에 캐싱 라인이 몇 개 포함되느냐(E 값)에 따라 나눠짐
1. Direct-Mapped Cache (E = 1)
Direct-Mapped Cache의 경우 conflict miss에 취약함, 같은 set에 속한 캐시 블록을 반복해서 load/evict하는 상황인 thrashing이 발생할 수 있음
2. Set Associative Cache (1 < E < C/B)
캐시 내부의 각 set은 key가 valid bit+tag bits, value가 block contents인 작은 associative memory로 볼 수 있음
Line Replacement에는 지역성의 원리를 적용해서 LFU, LRU와 같은 알고리즘을 적용
이러한 알고리즘을 적용하면 추가적인 시간과 하드웨어가 필요하지만 memory hierarchy에서 아래로 갈수록 miss penalty가 커지므로 좋은 교체 알고리즘을 선택하는 것이 중요해짐 (알고리즘 동작에 소요되는 시간은 penalty에 비해 작음)
3. Fully Associative Cache (E = C/B)
오직 하나의 set만 존재함
쓰기와 관련된 문제들
이미 캐시된 word w를 쓰는 경우(write hit), 다음 낮은 레벨의 저장장치에 w의 복사본을 어떤 방식으로 업데이트할 것인가에 대한 문제
- write through
바로w가 포함된 캐시 블록을 다음 레벨에 업데이트
간단하지만 쓰기 시마다 버스 트래픽 발생 - write back
w가 포함된 블록이교체될 때까지업데이트를 미룸
버스 트래픽을 낮추지만더티 비트를 추가로 필요로 하고, 메모리-캐시 간데이터 불일치가 발생하는 등 복잡도가 올라감
쓰려고 하는 word w가 캐시에 없는 경우(write miss), w가 포함된 블록을 캐시에 적재할 것인지 여부에 대한 문제
- write-allocate
다음 레벨에서 데이터 블록을 가져와서캐시에 적재하고 캐시 블록 업데이트
공간 지역성을 활용할 수 있으나 매번miss가 발생할 때마다 데이터 블록을 가져와야 함 - no-write-allocate
캐시를 우회(bypass)해서 바로 다음 레벨에w를 씀
write-through 캐시의 경우 주로 no-write-allocate이고, write-back의 경우 주로 write-allocate임
Anatomy of a Real Cache Hierarchy
i-cache: 명령어만 저장하는 캐시d-cache: 프로그램 데이터만 저장하는 캐시unified cache: 명령어와 데이터 모두 저장하는 캐시
i-cache와 d-cache를 나누는 이유
- 명령어와 데이터를 동시에 읽을 수 있음
- 명령어 캐시와 데이터 캐시의 액세스 패턴이 다른 점을 반영해서
block size,associativity,capacity를 다르게 설정함으로써 각각 최적화 가능 - 명령어에 대한 접근과 데이터에 대한 접근이 서로
conflict miss를 발생시키지 않음 (하지만 캐시를 둘로 나눴으므로capacity miss에 대한 가능성은 높아짐)
Cache Performance Metrics
miss rate: 메모리 참조 중 캐시 미스가 발생하는 비율 (# misses / # references)hit rate: 캐시 히트 비율 (1 - miss rate)hit time: 캐시로부터CPU로word를 가져오는 데 걸리는 시간 (set selection,line matching,word selection에 사용하는 시간 포함)miss penalty: 캐시 미스가 발생해서 추가적으로 드는 시간
여러 캐시 파라미터가 성능에 미치는 영향
-
캐시 사이즈
캐시 사이즈가 커지면hit rate는 높아지지만속도는 느려짐 -
블록 사이즈
블록 사이즈가 커지면 공간 지역성을 활용해서hit rate를 높일 수 있음
그러나 전체 캐시 사이즈가 고정된 상황에서는 블록 사이즈를 키우면 캐시 라인 수가 적어지고, 공간 지역성보다 시간 지역성을 더 활용하는 프로그램의 경우hit rate가 떨어질 수 있음
또한 블록 사이즈가 커지면 전송 시간이 길어지므로miss penalty가 증가함 -
Associativity (set 하나당 캐싱 라인 수)
캐싱 라인 수가 많으면conflict miss로 인한thrashing가능성이 감소함
그러나 구현 난이도가 올라가고 속도가 느려짐
추가적인LRU state bit,control logic을 필요로 함
높아진 복잡도로 인해hit time,miss penalty증가
낮은 레벨의 저장장치의 경우miss penalty가 크므로 캐싱 라인 수를 늘림 (miss rate을 줄이기 위해,access time = hit time + miss rate * miss penalty) -
Write Strategy
write-through의 경우 구현이 간단하고 캐시와 독립적으로 작동하는write buffer를 메인 메모리 업데이트에 사용할 수 있음
또한read miss의 경우 메모리 쓰기를 발생시키지 않음
write-back의 경우 데이터 전송 횟수가 감소하고,DMA를 수행하는I/O 장치에 메모리로의 대역폭을 더 많이 할당할 수 있음
또한hierarchy아래로 갈수록 전송 시간이 길어지므로 전송 횟수를 줄이는 것이 중요함, 따라서 낮은 레벨 저장장치에서는write-back을 주로 사용
