캐시 매핑 방식과 연관도가 만드는 성능·비용의 균형

주소의 어느 비트가 캐시 위치를 정하는가

캐시는 주기억장치 데이터 일부를 담아 두는 고속 버퍼다. 메모리 블록이 캐시에 들어올 때 핵심은 어느 라인에 둘지를 정하는 규칙이며, 이 규칙이 충돌 가능성, 태그 비교 회로, 전력 소비를 함께 좌우한다.

⤢✕

주소는 태그, 인덱스, 오프셋으로 나뉜다. 태그는 메모리 블록을 고유하게 구분하고, 인덱스는 캐시 안의 위치 또는 세트를 고른다. 오프셋은 캐시 라인 내부의 바이트를 지정한다.

블록 크기가 일반적으로 64바이트이면 오프셋은 6비트가 된다. 캐시 전체 용량은 인덱스 비트 수에 영향을 준다. 캐시가 메모리보다 훨씬 작기 때문에 공간 제약은 피할 수 없고, 주소만으로 빠르게 위치를 찾으면서 같은 위치를 요구하는 블록의 충돌도 처리해야 한다. 이때 검색·비교 회로의 복잡도와 비용, 히트율 사이에서 선택이 필요하다.

한 위치로 고정하는 직접 매핑

직접 매핑에서는 각 메모리 블록이 들어갈 수 있는 캐시 위치가 하나로 정해진다. 블록 주소를 캐시 라인 수로 나눈 나머지가 인덱스가 된다.

⤢✕

인덱스 비트는 log₂(캐시 라인 수) 비트이고, 오프셋 비트는 log₂(블록 크기) 비트다. 상위 나머지 비트는 태그가 된다. 매핑 함수는 다음과 같다.

캐시 인덱스 = (블록 주소) mod (캐시 라인 수)

인덱스 계산 뒤 태그를 한 번만 비교하면 되므로 구조가 단순하고, 비교기 1개로 구현할 수 있다. 단순한 회로는 전력 소비를 낮추며 동작도 결정적이다.

반대로 서로 다른 블록이 같은 인덱스를 요구하면 계속 서로를 밀어낸다. 규칙적인 접근 패턴에서는 캐시 스래싱이 생길 수 있고, 다른 슬롯이 비어 있어도 해당 블록은 정해진 위치 외에는 사용할 수 없다. 이 구조에서는 교체 정책을 선택할 여지도 없다.

캐시 크기: 8개 라인 (인덱스 3비트)
블록 크기: 64바이트 (오프셋 6비트)

메모리 블록 0, 8, 16, 24... → 캐시 라인 0
메모리 블록 1, 9, 17, 25... → 캐시 라인 1
메모리 블록 7, 15, 23, 31... → 캐시 라인 7

모든 라인을 후보로 두는 완전 연관 매핑

완전 연관 매핑은 메모리 블록을 캐시의 어느 라인에나 둘 수 있다. 인덱스 비트는 없으며, 빈 라인이나 교체 대상으로 선택된 라인에 배치한다.

⤢✕

오프셋은 log₂(블록 크기) 비트이고, 인덱스를 제외한 나머지 비트가 태그가 된다. 강제된 위치가 없으므로 직접 매핑에서 발생하는 충돌을 줄이고 캐시 라인을 고르게 쓸 수 있다. LRU, FIFO 같은 교체 정책도 선택할 수 있다.

대신 모든 태그를 동시에 비교해야 한다. 캐시 라인 수가 N개라면 비교기도 N개 필요하다. 병렬 비교를 하더라도 회로 지연이 늘고, 모든 태그를 활성화하는 전력 부담도 커진다. 따라서 대용량 캐시에는 비실용적이다.

TLB(Translation Lookaside Buffer)처럼 가상 주소와 물리 주소 변환을 캐시하는 구조, 라인 수가 8-64개 정도인 소형 캐시, 미스 비용이 매우 큰 특수 목적 캐시와 빠른 키-값 검색 구조에 적용할 수 있다. 비용보다 성능을 우선하는 경우에도 후보가 된다.

세트 안에서만 연관 검색하는 방식

세트 연관 매핑은 캐시를 여러 세트로 나누고, 각 세트에 여러 웨이를 둔다. 주소 인덱스로 세트를 먼저 정한 뒤 그 안에 있는 N개 웨이의 태그만 병렬 비교한다.

⤢✕

세트는 캐시를 분할한 그룹이며, 웨이는 한 세트에 속한 캐시 라인 수다. 인덱스는 log₂(세트 수) 비트로 세트를 선택하고, 그 세트 안에서만 N개 태그를 비교한다. 일반 구성으로는 2-way, 4-way, 8-way, 16-way가 있다.

예시: 4-way 세트 연관, 16개 세트, 64바이트 블록

[태그 비트] [인덱스: 4비트] [오프셋: 6비트]
    |              |                |
    블록 식별      세트 선택        바이트 위치

직접 매핑보다 충돌을 줄이면서도, 완전 연관처럼 모든 라인을 비교할 필요는 없다. 필요한 비교기는 웨이 수 N개이며 대용량 캐시에도 적용할 수 있다. 현대 프로세서에서 표준적인 방식으로 쓰이는 이유다.

다만 직접 매핑보다 하드웨어가 복잡하고, 같은 세트에 속하는 블록 간 경쟁은 남아 있다. 웨이 수가 늘수록 비교 회로와 전력 소비도 늘기 때문에 적절한 연관도를 골라야 한다.

⤢✕

연관도가 달라지면 달라지는 선택

직접 매핑은 접근 시간이 가장 빠르고 하드웨어 비용과 전력 소비가 가장 적다. 완전 연관은 히트율이 가장 높지만 접근 시간은 느리고 비용과 전력 소비가 가장 크다. 4-way 세트 연관은 그 중간에 놓인다.

항목	직접 매핑	4-way 세트 연관	완전 연관
히트율	낮음	중간-높음	최고
접근 시간	가장 빠름	중간	느림
하드웨어 비용	가장 저렴	중간	가장 비쌈
전력 소비	가장 적음	중간	가장 많음
확장성	우수	우수	제한적

원본의 성능 데이터에서는 직접 매핑 히트율이 85-90%, 4-way가 93-96%, 8-way가 95-97%, 완전 연관이 97-99%로 제시된다. 8-way 이상에서는 개선이 미미한 수확 체감을 고려해야 한다.

캐시 계층과 제약 조건도 선택에 관여한다. L1 캐시는 속도와 성능의 균형을 위해 8-way 세트 연관, L2는 히트율을 중시해 8-16-way, L3는 대용량 특성 때문에 12-20-way 구성이 제시된다. 엔트리 수가 적은 TLB는 완전 연관 또는 높은 연관도를 쓸 수 있으며, 비용과 전력 제약이 큰 임베디드 환경에서는 직접 매핑 또는 2-way가 대상이 된다.

교체 대상을 정하는 정책

세트 연관과 완전 연관에서는 미스가 발생했을 때 어느 블록을 내보낼지도 결정해야 한다. LRU(Least Recently Used)는 가장 오래 사용하지 않은 블록을 고르고, Pseudo-LRU는 하드웨어를 간소화한 LRU 근사 방식이다. FIFO(First-In-First-Out)는 가장 먼저 들어온 블록을, Random은 무작위 블록을, LFU(Least Frequently Used)는 사용 빈도가 낮은 블록을 교체한다.

⤢✕

현대 프로세서에서는 Intel이 Pseudo-LRU 또는 변형을, AMD가 유사 LRU 정책을, ARM이 랜덤 또는 간단한 LRU를 사용한다. 접근 비트와 카운터로 하드웨어가 이를 지원하며, 접근 패턴에 따라 동적으로 바뀌는 적응형 정책도 있다.

직접 매핑은 단순성과 접근 속도를 얻는 대신 충돌에 취약하다. 완전 연관은 배치 자유도와 히트율을 얻는 대가로 비교 회로의 비용을 감수한다. 세트 연관은 이 둘 사이에서 검색 범위를 세트로 제한해, 성능과 비용을 함께 조정하는 방식이다.