캐시 성능 향상
- Direct mapped 캐시의 문제점 : 같은 인덱스에 자주 사용하는 주소가 매핑되면 캐시 미스 발생 증가
- Associativity : 각 인덱스가 여러 슬롯(way)를 가지도록 설계한다.
- Associativity을 늘린다는 것은 장점은 miss rate가 줄어든다는 것이고, 단점은 hit time이 늘어난다는 것이다.
- Set associative : 1개의 인덱스 → 2개의 슬롯 사용 가능
- Full associative : 1개의 인덱스 → 모든 슬롯 사용 가능
- Multi-level 캐시
- 작은 캐시는 빠르지만, 캐시 미스율이 높아 성능이 저하된다.
- 큰 캐시는 느리지만 hit time이 느려져서 성능이 저하된다.
- 해결책 : multi-level(다단계) 캐시 구조를 사용함
- L1 : 작고 빠름, L2 : L1보다 크고 약간 느림, L3 : 더 크고 느림
- Software Optimization : 소프트웨어 최적화(전략적으로 데이터 접근 전략 짜기)
- 공간적 지역성, 시간적 지역성 등등을 이용하여 데이터 접근의 패턴을 최적화
Associative Caches
- 기존의 direct mapped랑 비교해서 보기
-
Fully Associative Cache
- 캐시의 어느 위치로든 block이 저장될수 있다.
- 따라서, 모든 위치가 동시 탐색되어야 함, 비교기(comparator)이 많이 필요하므로 cost가 비싸다!
- 캐시의 어느 위치로든 block이 저장될수 있다.
-
n-way Set Associative Cache (direct와 fully의 중간정도)
- 캐시를 여러 set로 나누고, 각 set는 n개의 슬롯(블럭)을 포함한다.
- 위에서 set associative는 2개의 슬롯
- Set Index=블럭 주소 mod set의 개수
- 비교기가 n개가 되고(같은 set에서만 비교하면 되니까), n은 2의 거듭제곱이 아닐수도있다.
- 예시 그림보면 이해하기 쉬울 것임
- 캐시를 여러 set로 나누고, 각 set는 n개의 슬롯(블럭)을 포함한다.
예시로 알아보자~!
- Direct mapped (block 개수가 4개)
- 2-way set (set의 수가 2개)
- Fully associative = 어디든 들어갈 수 있다.
- Associativity 연관성이 높아질수록(fully로 될수록)
- miss rate가 줄어든다! (hit많아짐)
Set Associative Cache Organization
-
4KB 캐시, 1word/block → offset = 2bit
- 4KB = 2^12B / 4B = 2^10B → 4way니까 / 4 해줌 → 2^8개의 인덱스(set인덱스 개수)
- Hit는 OR로 연결됌(4개중에 하나만 Hit이어도 되니까) (Mux를 통해 데이터 출력)
Replacement Policy
-
direct : 선택권이 없다.
-
set associative : non-valid(empty)위치가 있는 경우에 선택함 그렇지 않으면 set의 블럭 중 하나를 victim으로 선택해야 한다.
- 희생자의 선택에 최고의 선택은 가장 먼 미래에 사용될 block(안 쓰일 것 같은) → 현실적이지 x, 알기 어렵다.
-
1번째 policy
- LRU : 가장 오랫동안 사용되지 않았던 놈을 고른다!
- cost : n! (LRU를 파악하기 힘들기에 사용 순서의 모든 가능한 순열을 관리해야하므로)
- Pseudo LRU(for 4+ ways)
-
사용 순서를 모두 관리하지 않고 근사치를 사용하는 것이다. Like Tree구조처럼
-
cost : n ways → n-1개의 bit 필요
- 1bit LRU를 여러개 사용하고 1bit LRU는 가장 덜 최근에 사용한 요소의 위치를 나타낸다. 가장 덜 최근에 사용한 요소가 위의 요소면 0, 아래의 요소면 1
-
예시 (0,1,2,3 가 있다 가정, 0 → 3 순서로 접근)
-
초기 상태
-
0에 접근한다고 하면
- 다음과 같이 업데이트 됨
-
그 후 3에 접근한다고 하면
- 다음과 같이 업데이트 됨
- 3이 가장 최근 0이 그 다음 최근이니까 1과 2가 LRU의 대상이
- 다음과 같이 업데이트 됨
-
-
- LRU : 가장 오랫동안 사용되지 않았던 놈을 고른다!
-
2번째 policy
- Sequencial (Round Robin) : 순서가 정해진
- Random : 랜덤하게
- 둘다 n이 커지면 커질수록 교체확률(hit rate)이 작아진다.
-
캐시 예시 (연관성 적용)
- 그림을 잘 봐라!
- LRU : 1(위(0)의 값을 최근에 access해서), V : 1(empty), D : 1(Write-Back 이라서!)
- 1단계씩 알아보자!
- index가 64 (set index)이기에 set 64에 저장해줬고, Load는 D = 0(변화x), 새로운 값을 저장하는 Store는 D = 1
- set64에 tag = 2000이 저장되어 있었기에 Hit!
- set64의 아래 값이 D = 1이기에 아래 값을 접근할때 메모리에 저장해주면서 D = 0으로 바꿈(load라 0, store면 1로 set)
다단계 캐시
다단계 캐시 계산 예시
Multi-level Cache Considerations 다단계 캐시 고려사항
Virtual Memory
가상 주소
Page Table Entry(PTE)
Page Fault Handler
