캐시 메모리, 캐싱에 대한 이해

DRAM vs SRAM

DRAM과 SRAM은 모두 전원이 끊기면 데이터가 사라지는 휘발성 메모리지만, 데이터를 저장하는 구조와 용도가 다르다.

구분	DRAM	SRAM
비트당 가격	저렴하다	비싸다
접근 속도	상대적으로 느리다	빠르다
리프레시	전하가 누설되므로 주기적인 리프레시가 필요하다	전원이 공급되는 동안 별도의 리프레시가 필요 없다
주요 용도	메인 메모리	CPU 캐시 메모리

메모리 계층 구조

초기 컴퓨터의 저장장치는 주로 CPU 레지스터, 메인 메모리, 디스크의 세 계층으로 구성되었다. 이후 CPU와 메인 메모리 사이의 속도 차이가 커지면서 그 간격을 줄이기 위해 캐시 메모리가 추가되었다.

메모리 계층의 위쪽으로 갈수록 CPU와 가깝고 빠르지만, 용량이 작고 비트당 가격이 비싸다. 반대로 아래쪽으로 갈수록 느리지만 더 많은 데이터를 저렴하게 저장할 수 있다. 이러한 가격·속도·용량의 절충 관계 때문에 메모리 계층은 피라미드 형태를 이룬다.

CPU가 요청한 데이터가 상위 계층에 있으면 곧바로 사용할 수 있다. 이를 **캐시 적중(cache hit)**이라고 한다. 데이터가 없다면 **캐시 미스(cache miss)**가 발생하며, 하위 계층에서 해당 데이터가 포함된 블록을 가져와 상위 계층에 복사한다.

계층을 여러 단계 거치면 오히려 느릴 것처럼 보이지만, 실제 프로그램은 최근에 사용한 데이터나 인접한 데이터를 다시 사용할 가능성이 높다. 이러한 성질을 각각 **시간 지역성(temporal locality)**과 **공간 지역성(spatial locality)**이라고 한다. 지역성 덕분에 대부분의 메모리 요청은 빠른 상위 계층에서 처리된다.

CPU가 메모리 주소를 읽거나 쓸 때는 먼저 캐시를 확인한다. 원하는 데이터가 캐시에 있다면 메인 메모리까지 접근할 필요가 없으므로 실행 시간을 줄일 수 있다. 캐시에 없다면 하위 계층에서 블록을 가져온 뒤 요청을 처리한다.

레지스터와 캐시의 관계

레지스터와 캐시를 소프트웨어가 순서대로 검색하는 것은 아니다. 연산에 필요한 값이 이미 레지스터에 있다면 메모리 접근 자체가 발생하지 않는다. 반면 load나 store 명령이 실행되면 CPU가 캐시에 주소를 전달하고, 캐시 미스가 발생한 경우에만 하위 메모리에서 블록을 가져온다.

해시와 주소 매핑

캐시는 넓은 메모리 주소 공간을 제한된 수의 캐시 집합에 대응시켜야 한다. 캐시의 집합 인덱스는 주소의 일부 비트를 사용해 저장 위치를 결정한다는 점에서 해시 테이블의 주소 매핑과 비슷한 역할을 한다. 다만 일반적인 해시 함수를 계산하는 것은 아니며, 주소 비트를 직접 나누어 사용한다.

일반적으로 **해시 함수(hash function)**는 임의 길이의 입력을 고정된 길이의 값으로 매핑하는 함수다.

• 키(key): 해시 함수에 입력하는 원본 데이터
• 해시 값(hash value): 해시 함수가 계산한 결과
• 해싱(hashing): 키를 해시 값으로 변환하는 과정
• 해시 테이블(hash table): 해시 값을 이용해 키와 값을 저장하고 탐색하는 자료구조

임의 길이의 데이터를 해싱하면 고정된 길이의 해시 값을 얻을 수 있다.

해싱 과정의 예시

해시를 사용하는 이유

해시 테이블은 해시 값을 이용해 데이터가 들어갈 **버킷(bucket)**의 인덱스를 결정한다. 전체 데이터를 처음부터 순회하지 않고 해당 버킷부터 확인할 수 있어 평균적으로 빠른 탐색이 가능하다.

서로 다른 키가 같은 버킷에 대응하는 해시 충돌이 발생할 수 있으므로, 실제 해시 테이블은 체이닝이나 개방 주소법 등의 방법으로 충돌을 처리한다.

해시 함수와 충돌 처리 방법에 대한 자세한 내용은 해시 함수 정리를 참고한다.

캐시 메모리의 구성

캐시는 $S=2^s$개의 **집합(set)**으로 구성되고, 각 집합은 $E$개의 **캐시 라인(cache line)**을 가진다. 각 캐시 라인에는 $B=2^b$바이트 크기의 데이터 블록과 유효 비트(valid bit), 태그(tag)가 저장된다.

태그와 유효 비트 같은 메타데이터를 제외한 캐시의 데이터 용량 $C$는 다음과 같다.

$C=S\times E\times B$

메모리 주소는 다음 세 부분으로 나뉜다.

• 태그(tag): 선택한 캐시 라인이 요청한 메모리 블록인지 확인한다.
• 집합 인덱스(set index): 데이터를 찾을 캐시 집합을 선택한다.
• 블록 오프셋(block offset): 캐시 라인의 데이터 블록 안에서 필요한 바이트의 위치를 선택한다.

Direct Mapped Cache (E = 1)

**직접 매핑 캐시(direct-mapped cache)**는 각 집합에 캐시 라인이 하나만 있는 구조다. 따라서 하나의 메모리 블록이 들어갈 수 있는 캐시 라인이 정확히 하나로 정해진다.

1. 주소의 집합 인덱스로 캐시 라인을 선택한다.
2. 유효 비트가 설정되어 있고 태그가 일치하는지 확인한다.
3. 두 조건을 만족하면 캐시 적중이며, 블록 오프셋으로 필요한 데이터를 선택한다.

직접 매핑 캐시는 구조가 단순하고 구현 비용이 낮다. 그러나 같은 집합에 대응하는 메모리 블록을 번갈아 접근하면 기존 라인이 반복해서 교체되는 **충돌 미스(conflict miss)**가 발생하기 쉽다.

E-way Set Associative Cache (E > 1)

**E-way 집합 연관 캐시(E-way set associative cache)**는 하나의 집합에 $E$개의 캐시 라인을 둔다. 먼저 집합 인덱스로 집합을 선택한 다음, 집합 안에 있는 모든 라인의 태그를 병렬로 비교한다. 직접 매핑 캐시보다 충돌 미스를 줄일 수 있지만, 비교 회로가 복잡해져 접근 시간과 구현 비용이 증가할 수 있다.

블록 오프셋은 블록의 시작 위치를 지정하는 값이 아니라, 선택된 블록 내부에서 필요한 바이트나 워드의 위치를 지정하는 값이다.

**완전 연관 캐시(fully associative cache)**는 집합이 하나뿐이어서 메모리 블록을 어느 캐시 라인에나 저장할 수 있다. 충돌 미스를 최소화할 수 있지만 모든 라인의 태그를 비교해야 하므로 하드웨어 비용이 높다. 이 때문에 큰 범용 캐시보다는 라인 수가 적은 구조에 주로 사용한다.

교체 정책

집합 안의 모든 캐시 라인이 사용 중인 상태에서 새 블록을 저장하려면 기존 라인 하나를 선택해 교체해야 한다.

• LFU(Least Frequently Used): 일정 기간에 참조 횟수가 가장 적었던 라인을 교체한다.
• LRU(Least Recently Used): 가장 오랫동안 참조되지 않은 라인을 교체한다.
• Random: 교체할 라인을 임의로 선택한다.

정확한 LRU는 연관도가 높아질수록 구현 비용이 커지므로 실제 하드웨어에서는 근사 LRU 정책을 사용하기도 한다.

Cache Write

Write Hit

쓰기 대상 블록이 캐시에 있다면 캐시와 메인 메모리의 일관성을 유지하는 방법을 결정해야 한다.

• Write-through: 캐시와 메인 메모리를 동시에 갱신한다. 구현이 단순하지만 메모리 버스 트래픽이 증가한다.
• Write-back: 우선 캐시만 갱신하고, 해당 라인이 교체될 때 변경된 블록을 메인 메모리에 기록한다. 캐시와 메인 메모리의 내용이 다르다는 사실을 표시하기 위해 **더티 비트(dirty bit)**가 필요하다.

Write Miss

쓰기 대상 블록이 캐시에 없다면 해당 블록을 캐시로 가져올지 결정해야 한다.

• Write-allocate: 하위 메모리에서 블록을 캐시로 가져온 뒤 캐시를 갱신한다. 같은 주소에 대한 후속 접근이 많을 때 유리하며, 일반적으로 write-back과 함께 사용한다.
• No-write-allocate(write-around): 블록을 캐시로 가져오지 않고 하위 메모리만 갱신한다. 일반적으로 write-through와 함께 사용한다.

실제 캐시 메모리

캐시는 프로그램 데이터뿐만 아니라 명령어도 저장할 수 있다.

• i-cache(instruction cache): 명령어를 저장한다.
• d-cache(data cache): 프로그램 데이터를 저장한다.
• unified cache: 명령어와 데이터를 함께 저장한다.

현대 프로세서는 일반적으로 L1 캐시를 i-cache와 d-cache로 분리한다. 이 구조에서는 명령어와 데이터를 동시에 읽을 수 있어 두 접근이 서로 경쟁하는 일을 줄일 수 있다. 하위 레벨 캐시는 통합 캐시로 구성하는 경우가 많다.

Cache Performance

캐시 성능을 평가할 때는 다음 지표를 사용한다.

• 적중률(hit rate): 전체 메모리 참조 중 캐시 적중이 발생한 비율
• 미스율(miss rate): 전체 메모리 참조 중 캐시 미스가 발생한 비율. 1 - 적중률과 같다.
• 적중 시간(hit time): 캐시에서 원하는 라인을 찾고 CPU에 전달하는 데 걸리는 시간
• 미스 페널티(miss penalty): 캐시 미스가 발생했을 때 하위 계층에서 블록을 가져오는 데 추가로 드는 시간

평균 메모리 접근 시간(AMAT)은 다음과 같이 나타낼 수 있다.

$\text{AMAT}=\text{Hit time}+\text{Miss rate}\times \text{Miss penalty}$

캐시 용량이나 집합 연관도를 높이면 대체로 미스율을 낮출 수 있다. 그러나 캐시가 커지거나 비교해야 할 라인이 많아지면 적중 시간과 하드웨어 비용이 증가할 수 있으므로, 실제 설계에서는 이 요소들의 균형을 맞춰야 한다.