캐시 주소·매핑·교체

프로그램이 주소 0과 16을 번갈아 읽는다고 합시다. 캐시에 빈자리가 넉넉한데도 접근할 때마다 주기억장치까지 가야 하는 경우가 있습니다. 캐시가 얼마나 큰지만으로는 이 현상을 설명할 수 없고, 어떤 블록을 캐시의 어느 자리에 둘 수 있는지가 문제입니다. 이 글에서는 메모리 계층과 주기억장치의 캐시가 주소로 자리를 찾는 방법과, 자리가 찼을 때 무엇을 내보낼지 정하는 방법을 다룹니다. 주소 하나가 1바이트를 가리키고 캐시는 처음에 비어 있으며, 실제 CPU의 여러 단계 캐시나 가상 주소는 아직 생각하지 않겠습니다.

주소를 세 부분으로 나눈다

캐시에서 블록 하나와 그 블록을 알아보는 정보를 담는 자리를 라인(line)이라고 합니다. 블록 크기 B가 4바이트이고 캐시의 데이터 용량 C가 16바이트이면 라인은 C / B = 4개입니다. 블록을 알아보는 태그나 유효 비트 같은 관리 정보는 이 용량에 넣지 않습니다. 주소 21을 읽는 과정은 세 단계로 나눌 수 있습니다.

먼저 주소를 블록 크기로 나누어 블록 번호와 그 블록 안의 위치를 구합니다. 블록 번호는 21 // 4 = 5이고, 블록 안의 바이트 위치인 오프셋(offset)은 21 % 4 = 1입니다. 블록 5에는 주소 20부터 23까지가 들어 있습니다. 다음으로 블록마다 들어갈 라인이 하나로 정해진 직접 매핑에서는 블록 번호를 라인 수로 나눈 나머지 5 % 4 = 1이 라인 번호, 곧 인덱스(index)입니다. 마지막으로 그 몫 5 // 4 = 1이 태그(tag)인데, 같은 라인 1에 들어올 수 있는 블록 1, 5, 9, … 가운데 어느 것인지를 구별하는 값입니다.

블록 크기와 라인 수가 2의 거듭제곱이면 이 나눗셈은 주소의 비트를 잘라 내는 것과 같습니다. 진법과 고정 길이 정수에서 본 것처럼 $2^k$로 나눈 몫과 나머지가 시프트와 아래 k비트이기 때문입니다. 서로 다른 $2^p$가지를 구별하는 데는 p비트가 필요하므로, 오프셋은 블록 크기 4에 2비트, 인덱스는 라인 수 4에 2비트이고, 8비트 주소에서 남는 4비트가 태그입니다. 그래서 21 = 0001 01 01은 태그 1, 인덱스 1, 오프셋 1로 읽힙니다.

캐시는 인덱스로 라인 하나를 골라, 그 라인의 유효 비트가 1이고 저장된 태그가 요청한 태그와 같을 때만 적중(hit)으로 판단합니다. 인덱스가 같다는 것은 같은 라인을 들여다본다는 뜻일 뿐, 그 안에 있는 블록이 내가 찾는 블록이라는 뜻은 아닙니다. 거꾸로 필드에서 주소를 되찾으려면 (태그 × 라인 수 + 인덱스) × B + 오프셋 = (1 × 4 + 1) × 4 + 1 = 21처럼 계산해야 하며, 세 값을 그냥 더하는 것이 아닙니다.

직접 매핑과 충돌 실패

직접 매핑(direct mapping)은 블록마다 들어갈 라인을 하나로 정합니다. 태그를 하나만 비교하면 되어 단순하고 빠르지만, 같은 라인으로 가는 블록을 번갈아 쓰면 서로를 쫓아냅니다. 위의 캐시에서 주소 0, 16, 0, 16을 읽어 보겠습니다.

실제로 쓰는 블록은 두 개뿐이고 나머지 세 라인은 비어 있지만, 두 블록 모두 라인 0에만 갈 수 있어서 네 번 모두 실패합니다. 실패는 원인에 따라 셋으로 나눕니다. 블록을 처음 읽어서 생기는 실패는 최초 실패(compulsory miss)이고, 처음 두 접근이 여기에 해당합니다. 같은 자리를 두고 다투느라 생기는 실패는 충돌 실패(conflict miss)이며 뒤의 두 접근이 그렇습니다. 쓰는 데이터 전체가 캐시 용량보다 커서 어떻게 배치해도 생기는 실패는 용량 실패(capacity miss)입니다.

세트 연관과 완전 연관

라인 여러 개를 묶어 세트(set)로 만들고, 블록이 자기 세트 안의 어느 라인에든 들어갈 수 있게 하면 충돌이 줄어듭니다. 세트마다 라인이 두 개이면 2-way 세트 연관(set associative) 캐시라고 합니다. 같은 16바이트 캐시를 2-way로 만들면 세트가 두 개이므로, 세트 번호는 블록 번호 % 2이고 태그는 블록 번호 // 2입니다. 블록 0과 4는 둘 다 세트 0에 가지만 서로 다른 라인에 함께 머물 수 있어서, 같은 접근은 실패, 실패, 적중, 적중이 됩니다.

필드의 비트 수는 라인 수가 아니라 세트 수로 정해집니다. 세트 수는 C / (B × way 수)이므로, 2-way에서는 세트 2개에 인덱스 1비트, 태그 8 − 2 − 1 = 5비트입니다. 블록이 어느 라인에나 들어갈 수 있는 완전 연관(fully associative) 캐시는 세트가 하나뿐이라 인덱스가 0비트이고, 블록 번호 전체가 태그가 됩니다. 연관도를 높이면 충돌 실패는 줄지만, 한 번에 비교해야 할 태그가 늘어 회로가 커지고 적중 시간이 길어질 수 있습니다.

무엇을 내보낼까

세트가 가득 찬 상태에서 실패하면, 그 세트의 라인 가운데 하나를 내보내고 새 블록을 넣어야 합니다. LRU(least recently used)는 그 세트에서 가장 오랫동안 쓰지 않은 블록을 내보내므로, 적중할 때마다 그 블록을 가장 최근에 쓴 것으로 순서를 고칩니다. FIFO(first in, first out)는 가장 먼저 들어온 블록을 내보내므로, 적중해도 순서가 바뀌지 않습니다. 같은 2-way 캐시에서 주소 0, 16, 0, 32, 16을 읽으면 블록은 0, 4, 0, 8, 4이고 모두 세트 0으로 갑니다. 처음 세 접근 뒤 두 정책의 세트 0은 담긴 블록이 같지만, 적중한 블록 0을 LRU는 최근 쪽으로 옮기고 FIFO는 그대로 둡니다. 그래서 넷째 접근의 블록 8이 들어올 때 LRU는 블록 4를, FIFO는 블록 0을 내보내고, 다섯째 접근의 블록 4는 LRU에서 실패, FIFO에서 적중이 됩니다.

def bits_for(choices):
    bits = choices.bit_length() - 1
    if choices <= 0 or 1 << bits != choices:
        raise ValueError("선택 수는 2의 거듭제곱이어야 합니다")
    return bits


def fields(address_bits, block_size, capacity, ways):
    sets = capacity // (block_size * ways)
    offset, index = bits_for(block_size), bits_for(sets)
    return offset, index, address_bits - offset - index


def cache_trace(addresses, block_size, capacity, ways, policy="LRU"):
    sets = [[] for _ in range(capacity // (block_size * ways))]
    result = []
    for address in addresses:
        block = address // block_size
        group = sets[block % len(sets)]
        hit = block in group
        if hit and policy == "LRU":
            group.remove(block)
            group.append(block)
        elif not hit:
            if len(group) == ways:
                group.pop(0)
            group.append(block)
        result.append("H" if hit else "M")
    return "".join(result), sets[0]


print(fields(8, 4, 16, 1), fields(8, 4, 16, 2), fields(8, 4, 16, 4))
print(cache_trace([0, 16, 0, 16], 4, 16, 1))
print(cache_trace([0, 16, 0, 16], 4, 16, 2))
for policy in ("LRU", "FIFO"):
    print(policy, cache_trace([0, 16, 0, 32, 16], 4, 16, 2, policy))

(2, 2, 4) (2, 1, 5) (2, 0, 6)
('MMMM', [4])
('MMHH', [0, 4])
LRU ('MMHMM', [8, 4])
FIFO ('MMHMH', [4, 8])

bits_for는 2의 거듭제곱인 선택 수를 구별하는 비트 수를 구하고, fields는 오프셋, 인덱스, 태그의 비트 수를 돌려줍니다. 첫 줄은 같은 16바이트 캐시를 직접 매핑, 2-way, 4-way(완전 연관)로 만들 때의 필드이며, way가 두 배가 될 때마다 인덱스가 1비트 줄고 태그가 1비트 늘어납니다. cache_trace의 각 세트 목록은 앞쪽이 내보낼 차례인 블록이고 뒤쪽이 최근 블록이며, 실패하면 꽉 찬 세트에서 맨 앞을 꺼내고 새 블록을 뒤에 붙입니다. LRU만 적중한 블록을 뒤로 옮깁니다. 결과 문자열의 H와 M은 적중과 실패, 뒤의 목록은 마지막 상태의 세트 0입니다.

둘째 줄과 셋째 줄은 앞의 두 표와 같은 결과이고, 마지막 두 줄이 교체 정책의 차이입니다. 이 예에서는 FIFO가 더 나았지만, 접근 순서에 따라 LRU가 나은 경우도 많으므로 어느 정책이 언제나 좋다고 말할 수는 없습니다. 실제 CPU는 완전한 LRU를 기록하는 비용이 커서, 이를 흉내 내는 간단한 근사 방식을 쓰는 경우가 많습니다. 이 시뮬레이터는 읽기만 다루며, 실행 시간으로 실제 캐시의 속도를 잴 수는 없습니다.

더 깊이: 내 컴퓨터의 캐시 구성 읽기

Linux에서는 실제 CPU의 캐시 구성을 파일로 읽을 수 있습니다. 커널의 sysfs ABI 문서에 따르면 /sys/devices/system/cpu/cpu0/cache/ 아래의 index0, index1 같은 디렉터리가 캐시 하나씩에 해당하고, 그 안의 파일이 이 글의 매개변수를 알려 줍니다. level은 몇 단계 캐시인지, type은 명령어용(Instruction), 데이터용(Data), 둘을 함께 담는 통합(Unified) 가운데 무엇인지, size는 전체 용량을 kB 단위로 보여 줍니다.

나머지 파일은 주소를 나누는 데 쓰는 값입니다. coherency_line_size는 메모리에서 캐시로 한 번에 옮기는 최소 바이트 수, 곧 이 글의 블록 크기이고, number_of_sets는 세트의 수, ways_of_associativity는 블록 하나가 들어갈 수 있는 자리의 수입니다. 이 값들을 본문의 식에 넣으면 오프셋, 인덱스, 태그가 각각 몇 비트인지 계산할 수 있습니다. shared_cpu_list는 그 캐시를 함께 쓰는 논리 CPU의 목록이므로, 단계마다 캐시를 몇 개의 CPU가 나누어 쓰는지도 알 수 있습니다.

정리

• 주소는 블록 크기로 나누어 블록 번호와 오프셋으로, 블록 번호는 세트 수로 나누어 태그와 인덱스로 나뉘며, 크기가 2의 거듭제곱이면 비트를 잘라 얻습니다.
• 적중은 인덱스로 고른 자리의 유효 비트가 1이고 태그가 같을 때만이며, 인덱스가 같다고 같은 블록은 아닙니다.
• 직접 매핑은 블록마다 자리가 하나라 단순하지만 충돌 실패가 생기고, 세트 연관과 완전 연관은 충돌을 줄이는 대신 비교할 태그가 늘어납니다.
• 실패는 처음 읽어서 생기는 최초 실패, 자리를 다투는 충돌 실패, 용량이 모자라 생기는 용량 실패로 나눕니다.
• LRU는 가장 오래 쓰지 않은 블록을, FIFO는 가장 먼저 들어온 블록을 내보내며, 적중한 뒤에는 두 정책의 순서가 달라질 수 있습니다.

연습 문제

1. 같은 용량, 다른 매핑

8비트 주소, 블록 8바이트, 데이터 용량 32바이트인 캐시에서 주소 0, 32, 0, 8, 32, 0을 읽습니다. 직접 매핑일 때의 필드 비트 수와 적중 결과를 구하고, 같은 용량의 2-way LRU 캐시에서도 구하세요.

2. 먼저 들어온 것과 오래 쓰지 않은 것

본문과 같은 블록 4바이트, 용량 16바이트, 2-way 캐시에서 주소 0, 16, 32, 16, 48을 읽습니다. 마지막 접근에서 LRU와 FIFO는 각각 어떤 블록을 내보내나요? 그다음에 주소 16을 읽으면 각 정책에서 적중인가요?

3. 2-way에서 주소 나누기

블록 4바이트, 용량 16바이트인 2-way 캐시에서 8비트 주소 21의 태그, 인덱스, 오프셋을 값과 비트로 구하세요.

캐시 문제는 주소를 먼저 블록 번호로 바꾸고, 블록 번호에서 세트와 태그를 구한 뒤 세트마다 목록을 적어 가며 풀면 실수가 줄어듭니다. 캐시 구조는 MIT 6.004의 캐시 강의에서도 더 볼 수 있습니다. 다음 글 쓰기 정책·보조기억장치에서는 데이터를 고쳐 쓸 때 그 내용이 아래층에 언제 전해지는지 다룹니다.