캐시는 CPU 가까이에 둔 작고 빠른 메모리입니다. 메모리 주소를 태그, 인덱스, 오프셋으로 쪼개서 어느 칸에 들어갈지 정하고, 같은 블록을 다시 찾으면 메인 메모리까지 가지 않고 바로 꺼냅니다.
메모리 주소가 캐시의 어느 칸에 들어가고 적중하거나 실패하는지 보여 주는 시뮬레이터
1. 매핑 방식과 접근 순서를 고르세요 (캐시 4칸, 블록 4바이트, 주소 8비트)
같은 접근 순서를 매핑 방식만 바꿔 실행해 보세요. [충돌하는 두 주소]는 직접 사상에서 계속 실패하고, [블록 5개 반복]은 완전 연관에서도 LRU 때문에 모두 실패합니다.
주소를 세 조각으로 나눕니다
블록이 4바이트이므로 주소의 아래 2비트(오프셋)는 블록 안의 몇 번째 바이트인지를 뜻합니다. 그 위 비트 중 일부(인덱스)로 캐시의 어느 집합에 넣을지 정하고, 나머지(태그)는 그 칸에 지금 어느 블록이 들어 있는지 구별하는 이름표로 저장합니다. 집합당 칸 수(way)가 늘어날수록 인덱스 비트는 줄고 태그 비트는 늘어납니다.
세 가지 매핑 방식
직접 사상은 블록마다 들어갈 칸이 하나로 정해져 있어 찾기는 빠르지만, 같은 칸을 쓰는 두 블록을 번갈아 쓰면 서로 계속 쫓아냅니다. 완전 연관은 아무 칸에나 넣을 수 있어 충돌이 없지만, 찾을 때 모든 칸의 태그를 동시에 비교해야 해서 하드웨어가 비쌉니다. 실제 CPU는 그 중간인 집합 연관(보통 4~16-way)을 씁니다.
코드에서 체감하는 캐시: 지역성
방금 쓴 데이터를 곧 다시 쓰는 시간 지역성과, 근처 주소를 이어서 쓰는 공간 지역성이 좋을수록 적중률이 오릅니다. 2차원 배열을 a[i][j] 순서(행 우선)로 돌면 메모리에 붙어 있는 값을 차례로 읽어 빠르고, a[j][i] 순서로 돌면 매번 멀리 떨어진 주소를 읽어 느려집니다. 연결 리스트보다 배열이 빠른 이유도 같습니다.