[Computer Architecture] Cache Memory: 블록 교체 & 블록 갱신

+ 한국항공대학교 길현영 교수님의 컴퓨터구조론 과목 내용을 정리한 글입니다.

블록 교체

캐시 공간이 없는 상황에서, 어느 캐시 블록을 비울 것인지 결정이 필요하다.

상황 1. 캐시의 모든 블록이 사용 중일 경우

상황 2. 일부 캐시 블록이 비어 있으나 불록 사상 방식에 따라 이미 사용중인 캐시 블록에 위치해야할 경우

---

블록 교체 전략 (Replacement Policy)

Belady의 MIN 알고리즘

가장 이상적인 블록 교체 방식으로, 가장 오랫동안 참조되지 않을 블록을 교체한다.

- 미래 예측이 필요하다. (거의 구현이 불가능하다.)

LRU 방식(Least Recently Used) - 가장 많이 사용

가장 오래전에 참조된 블록을 교체한다.

 

MIN 알고리즘에 근접할 정도의 최고 적중률을 보인다.

 

모든 블록에 대해 최근에 참조된 정보를 포함해야 하므로 구현비용이 높다.

(가장 오래 전에 참조된 블록을 결정하기 위해)

무작위 방식 (Random)

임의의 블록을 선택하여 교체한다.

 

효율성은 보장하기 어렵지만, 구현 비용이 저렴하고 간단하다.

선입 선출 방식 (FIFO, First In First Out)

캐시 메모리에 먼저 적재된 블록을 교체한다.

 

효율성을 보장하기 어렵지만, Time Locality 기반으로 구현 비용이 저렴하다.

---

블록 갱신

Write 연산에 의해 Main Memory와 그 Cache Memory가 불일치(inconsistent)할 경우 갱신이 필요하다.

- 메인 메모리와 캐시의 동일 블록(같은 주소)에 다른 값을 갖는 현상이다.

- 데이터를 캐시에만 쓰고 메인 메모리에는 쓰지 않는 경우 발생한다.

 

즉시 쓰기 (Write Through)

Write 연산 시, 항상 데이터를 메모리와 캐시에 같이 쓰는 방식이다.

 

메인 메모리까지 접근하는 데 시간이 오래 걸리기 때문에 캐시 메모리를 사용하는데, 쓰기 위해 메인 메모리를 접근해야하므로 성능 저하가 발생한다.

 

ex) 쓰기 연산은 최소 100개의 clock cycle을 사용하고, 명령어의 10%가 store라고 가정할 때, 캐시 실패가 없는 경우의 CPI = 1이라고 가정하면,

CPI = 1.0 + 100 * 0.1 = 11

 

성능 저하를 완화하기 위해, 쓰기 버퍼(Write Buffer)를 사용할 수 있다.

- 캐시에 Write 연산 시에 Hit라면, 쓰기 버퍼에 함께 Write하고 프로세서는 수행을 계속한다.

- Write 연산이 폭주하여 쓰기 버퍼가 모두 차 있으면 지연이 발생할 수 있으므로 가능한 큰 버퍼가 필요하다.

나중 쓰기 (Write - Back)

Write 연산 시, 새로운 값은 캐시 내 블록에만 쓰고, 나중에 블록 교체에 의해 캐시에서 나가는 블록이 발생했을 때, 하위 레벨의 메모리에 수정된 데이터를 갱신한다.

 

캐시 블록의 수정 여부를 표시하기 위해 갱신 비트를 사용한다.

 

속도가 빠르고, 메모리 트래픽이 감소한다.

 

즉시 쓰기보다 설계/구현이 복잡하다.

 

캐시와 메모리 사이의 데이터 불일치 문제가 발생하는 기간이 길어진다. (consistent ↓)

- 입출력장치가 데이터를 요구했을 때, 어느 것이 유효한 데이터인지 알기 위해 캐시 메모리를 체크해야한다.

 

CPU와 캐시에 문제가 발생시, 데이터 복구가 어렵다.