캐시 메모리는 CPU와 RAM 사이에 위치하며, 메모리 계층구조에 따라 RAM보다 빠르며, 작은 저장공간을 가집니다.
계층구조 상 더 빠른 캐시에 CPU가 원하는 데이터가 있는 경우가 더 빠르므로, 앞선 포스트에서 말했듯 지역성의 원리를 가지는 데이터들을 캐시에 저장합니다.
이때, CPU가 원하는 데이터가 이미 캐시에 있는 경우를 캐시 적중이라고 합니다. 이 캐시 적중률(Hit ratio)는 다음 식으로 구할 수 있습니다.
H = 캐시에 적중되는 횟수 / 전체 기억장치 액세스 횟수
그리고 원하는 데이터가 캐시에 없을 확률인 미스율(Miss ratio)는 1 - H가 됩니다.
이 값들을 통해 평균 기억장치 액세스 시간을 구할 수 있습니다.
Ta = H * Tc + (1 - H) * Tm (Tc = 캐시 액세스 시간, Tm = 주기억장치 액세스 시간, Ta = 평균 기억장치 액세스 시간)
사상 방식
사상 방식이란, 주기억장치 블록이 어느 캐시라인에 적재될 수 있는지 정해주는 알고리즘입니다.
사상 방식에는 크게 다음 3가지로 분류됩니다.
- 직접 사상
- 완전 - 연관 사상
- 세트 - 연관 사상
먼저 직접 사상은 주기억장치의 블록들이 지정된 하나의 캐시 라인으로만 사상되는 방식을 의미합니다.
캐시 라인 번호 i는 나머지 연산을 통해서 결정됩니다. 같은 캐시 라인을 공유하는 블록들은 태그 필드의 값을 통해 구분합니다. 만일 태그값이 일치하지 않아 캐시가 미스가 난다면, 주기억장치에서 한 블록을 인출해서 지정된 캐시라인에 적재하고 주소의 태그 비트들이 해당 캐시라인의 태그 필드에 저장됩니다. 이때, 그 라인을 공유하는 다른 블록이 이미 적재되어 있다면, 원래의 블록이 지워지고 덮어쓰여집니다.
완전 - 연관 사상은 주기억장치의 블록이 캐시의 어떤 라인으로든 적재될 수 있게끔 허용해서 직접 사상 방식의 단점을 보완한 방식입니다. 따라서, 라인필드는 따로 존재하지 않고 태그필드와 단어필드만 존재합니다.
해쉬 함수의 선형조사법 방식처럼, 캐시에 빈 라인이 있다면, 그대로 주기억장치에서 가져온 블록을 적재합니다. 단, 모든 라인이 사용중이라면, 적절한 교체 알고리즘을 선택하여 라인들 중 하나를 선택해서 새로운 블록을 적재합니다.
세트 - 연관 사상은 직접 사상 방식과 완전 - 연관 사상 방식의 장점만을 취하기 위한 선택안입니다. 이 경우 캐시를 v개의 세트로 나누고, 각 세트는 k개의 라인으로 구성됩니다. 따라서, 태그 필드와 세트 필드, 단어 필드가 존재합니다.
세트 내에 라인 수에따라 k-way 세트 - 연관 사상 캐시라고 부릅니다.
이 방식을 통해 주기억장치의 블록은 지정된 세트 내에 어떤 라인으로든 사상될 수 있습니다. 따라서, 세트 i를 정하고, 태그필드의 값을 통해 세트 i 내의 라인에서 사상하여 적중한다면 그대로 사용하고, 미스라면 주기억장치 액세스를 시작합니다.
교체 알고리즘
캐시에서 적중하지 못하여 새로운 블록이 주기억장치로부터 캐시로 올라왔을 때, 모두 사용중인 캐시 라인 중 하나를 선택해야합니다. 이때, 적절한 라인을 선택하기 위해서 교체 알고리즘을 사용합니다. 교체 알고리즘에는 대표적으로 다음 2가지가 있습니다.
- Least Recently Used (LRU)
- First In First Out (FIFO)
LRU는 가장 오랫동안 사용되지 않은 블록을 교체하는 방식이고, FIFO는 캐시에 적재된지 가장 오래된 블록을 교체하는 방식입니다.
쓰기 정책
캐시에 적재되어 있는 데이터가 다른 내용으로 변경되는 경우 캐시에 있는 데이터는 복사본에 불과하기 때문에, 데이터 동기화를 이해 주기억장치에 있는 데이터 또한 갱신해주어야합니다. 하지만, 주기억장치에 접근하는 것은 CPU 입장에서 시간이 많이 걸리므로, 캐시에 적재된 데이터를 새로운 값으로 변경할 때, 주기억장치에 갱신하는 시기와 방법을 결정하기 위한 쓰기 정책이 있습니다.
쓰기 정책중 하나인 Write - Through는 모든 쓰기 동작들이 캐시 뿐만아니라 주기억장치로도 동시에 행해집니다. 이 장점으로는 캐시와 주기억장치의 데이터가 항상 일치한다는 장점이 있지만, 쓰기 시간이 증가한다는 단점도 존재합니다.
반면, Write - Back은 데이터가 수정됐을 때, Modified bit(M Bit)를 세트하고, 캐시가 교체됐을 때, M Bit가 세트된 라인 전체가 주기억장치에 갱신된 다음 교체됩니다. 따라서, 쓰기 시간이 줄어드는 효과가 있지만, 일시적으로 캐시와 주기억장치 사이에 데이터가 불일치한 경우가 있고 캐시 쓰기를 위한 추가 제어회로 또한 필요로 합니다.
Write - Through에서 평균 읽기 시간은 H1 * T1 + H2 * T2 로 구할 수 있고,
평균 쓰기 시간은 T2, 평균 접근 시간은 읽기 확률 * 평균 읽기 시간 + 쓰기 확률 * T2로 구할 수 있습니다.
Write - Back에서 평균 접근 시간은 H1 * T1 + H2 * (T2 + 수정 된 백분율 * T2) 로 구할 수 있습니다.
온 - 칩 캐시
온 - 칩 캐시는 캐시를 CPU 칩 내부에 포함 시키는 방식을 의미합니다.
이 경우에서 기억장치 전체에 대한 적중률은 다음과 같습니다.
H1 * TL1 + (H2 - H1) * TL2 + (1 - H2) * Tm (H1 = 계층1 적중률, TL1 = 계층1 액세스 시간, Tm = 주기억장치 액세스 시간)
L1에서 Miss가 발생한 경우의 L2 적중률은 다음과 같습니다.
H1 * TL1 + M1 * H2 * TL2 + (M1 - M1 * H2) * Tm (M1 = 계층1 Miss 확률 = 1 - H1)