캐시 주소·매핑·교체

프로그램이 주소 0과 16을 번갈아 읽는다고 합시다. 캐시 공간은 충분한데 매번 주기억장치에 가야 할 수 있습니다. 저장 용량만으로는 이 현상을 설명할 수 없습니다. 어느 블록을 어느 자리에 둘 수 있는가가 중요합니다.

이 절은 비트·바이트·주소와 메모리 계층의 개념을 사용합니다. 여기서는 주소 하나가 1바이트를 가리키고 캐시는 처음에 비어 있다고 가정합니다. 실제 프로세서의 여러 캐시·가상주소·선인출은 아직 섞지 않습니다.

주소를 세 가지 질문으로 나누기

캐시의 라인(line)은 데이터 블록 하나와 그 블록을 구별하는 정보를 담는 자리입니다. 블록 크기 B가 4바이트이고 캐시 데이터 용량 C가 16바이트라면 라인은 C / B = 4개입니다. 태그·유효 비트 같은 관리 정보는 이 용량 계산에서 제외합니다.

주소 a = 21을 읽는 과정을 먼저 나눕니다.

1. 블록 번호 b = a // B = 21 // 4 = 5입니다.
2. 블록 안의 바이트 위치인 오프셋(offset)은 a % B = 1입니다. 블록 5에는 주소 20–23이 들어 있습니다.
3. 직접 매핑에서는 라인 번호 s = b % 4 = 1입니다.
4. 태그(tag)는 b // 4 = 1입니다. 같은 라인에 갈 수 있는 다른 블록과 구별합니다.

선택 수에서 필드 비트 수로 넘어가기

1비트의 패턴은 0·1의 2개, 2비트는 00·01·10·11의 4개, 3비트는 000–111의 8개입니다. 비트를 하나 늘릴 때마다 구별하는 수가 2배가 되므로 2ᵖ개를 구별하는 데 p비트가 필요합니다. 이 p를 log₂(선택 수)라고 쓰기도 하지만 로그 계산기를 외울 필요 없이 1에서 몇 번 2배 했는지 셀 수 있습니다. 이 절의 비트 필드 모델은 블록 크기·세트 수가 2의 거듭제곱인 경우입니다.

따라서 8비트 주소는 오프셋 2비트, 라인 인덱스 2비트, 태그 4비트로 나뉩니다. 21 = 0001 01 01에서 각 필드가 방금 계산한 태그·라인·오프셋 1·1·1입니다. 역으로 ((태그×세트 수)+세트 번호)×B+오프셋 = ((1×4)+1)×4+1 = 21이 됩니다. 단순히 필드 값을 더하는 식이 아닙니다.

way를 늘릴 때에는 라인 수가 아니라 세트 수 C/(B×way)에서 인덱스 비트를 구합니다. 같은 16바이트를 2-way로 만들면 세트 2개이므로 인덱스 1비트, 태그는 8−2−1=5비트입니다. 완전 연관은 세트 1개라 인덱스 0비트이고 한 가지 선택에 비트가 필요 없다는 뜻입니다. 주소 단위가 바이트가 아니라면 B도 그 단위로 고쳐야 합니다.

def choice_bits(choices):
    if choices <= 0:
        raise ValueError("선택 수는 양수입니다")
    size, bits = 1, 0
    while size < choices:
        size *= 2
        bits += 1
    if size != choices:
        raise ValueError("이 필드 모델은 2의 거듭제곱 선택 수입니다")
    return bits

def field_widths(address_bits, block_bytes, capacity_bytes, ways):
    if ways <= 0 or block_bytes <= 0 or capacity_bytes <= 0:
        raise ValueError("크기와 way는 양수입니다")
    if capacity_bytes % (block_bytes * ways):
        raise ValueError("용량은 블록 크기 × way 수의 배수입니다")
    offset = choice_bits(block_bytes)
    index = choice_bits(capacity_bytes // (block_bytes * ways))
    tag = address_bits - offset - index
    if tag < 0:
        raise ValueError("주소 폭보다 많은 필드를 요구했습니다")
    return offset, index, tag

assert [choice_bits(v) for v in (1, 2, 4, 8)] == [0, 1, 2, 3]
assert field_widths(8, 4, 16, 1) == (2, 2, 4)
assert field_widths(8, 4, 16, 2) == (2, 1, 5)
assert field_widths(8, 4, 16, 4) == (2, 0, 6)
print(field_widths(8, 4, 16, 1))

cache_fields.py로 실행하면 오프셋·인덱스·태그 순서의 (2, 2, 4)를 출력합니다. 아래 LRU 실행기는 몫·나머지로 블록을 관리하므로 이 비트 필드 계산 코드와 담당하는 질문이 다릅니다.

적중(hit)하려면 해당 자리의 유효 비트가 1이고 저장된 태그가 요청 태그와 같아야 합니다. 인덱스만 같다는 것은 같은 자리를 검사한다는 뜻입니다. 그 데이터가 같은 블록이라는 뜻은 아닙니다.

직접 매핑과 충돌

직접 매핑(direct mapping)은 블록마다 들어갈 라인을 하나로 제한합니다. 단순하고 검사할 태그가 하나지만, 같은 라인으로 가는 블록을 번갈아 쓰면 서로 쫓아냅니다.

위 캐시에서 주소 0, 16, 0, 16을 읽으면 다음과 같습니다.

실제로 쓰는 데이터는 두 블록뿐입니다. 나머지 세 라인이 비어 있어도 두 블록은 모두 라인 0에만 갈 수 있습니다. 첫 0·16 접근은 그 블록을 처음 읽는 최초 실패(compulsory miss)입니다. 다시 0·16을 읽을 때 서로 쫓아낸 결과로 실패하는 것이 충돌 실패(conflict miss)입니다. 전체 작업 데이터가 같은 용량의 완전 연관 캐시에도 남지 못하는 용량 실패(capacity miss)와도 구분합니다.

세트 연관과 완전 연관

2-way 세트 연관(set associative)은 한 세트에 라인을 두 개 둡니다. 같은 16바이트 용량을 유지하면 라인 4개는 세트 2개가 됩니다. 세트 번호는 b % 2, 태그는 b // 2입니다. 블록 0과 4는 세트 0에 가지만 서로 다른 way에 함께 놓일 수 있습니다. 이때 같은 접근열의 결과는 실패, 실패, 적중, 적중입니다.

완전 연관(fully associative)은 블록을 어느 라인에나 둘 수 있습니다. 세트 인덱스가 없고 태그는 블록 번호가 됩니다. 자유로운 배치에는 여러 태그 비교와 교체 후보 선택의 비용이 따릅니다. 연관도를 높이면 언제나 프로그램이 더 빨라진다고 단정할 수는 없습니다.

세트가 꽉 차면 무엇을 내보낼지도 정해야 합니다. LRU(Least Recently Used)는 그 세트 안에서 가장 오래 사용하지 않은 라인을 고릅니다. 접근 때마다 순서를 갱신합니다. FIFO는 가장 먼저 들어온 라인을 고르므로 적중 때 순서가 바뀌지 않습니다. 둘은 서로 다른 정책입니다.

적중이 교체 순서를 바꾸는 사례

이제 빈자리가 없어 실제 교체가 일어나는 접근열을 봅니다. 앞과 같은 B=4바이트·C=16바이트·2-way를 사용합니다. 주소 0,16,0,32의 블록은 0,4,0,8이고 모두 세트 0에 갑니다. 아래 LRU 목록은 가장 오래 사용한 블록→최근 사용한 블록, FIFO 목록은 먼저 들어온 블록→나중에 들어온 블록 순서입니다. 다른 세트에 빈자리가 있어도 이 세트의 두 way만 교체 후보입니다.

처음 네 접근의 적중열은 둘 다 M,M,H,M이지만 최종 저장 내용은 다릅니다. 한 번 더 주소 16을 읽으면 LRU는 블록 4가 없어 M, FIFO는 남아 있어 H입니다. LRU가 모든 접근열에서 FIFO보다 좋은 것은 아닙니다. 어떤 이력을 정책이 기억하는지를 비교한 예제입니다. 아래 함수에 cache_trace([0,16,0,32,16],4,16,2)를 넣으면 LRU 결과 ['M','M','H','M','M']을 얻어야 합니다. 이 함수에는 FIFO 구현이 없으므로 그 출력으로 FIFO를 검증했다고 기록하지 않습니다.

손 계산을 실행으로 확인하기

Python이 설치돼 있다면 아래 코드를 cache_trace.py에 저장하고 python cache_trace.py로 실행합니다. 주소·크기·way 수는 모두 정수라는 전제입니다. //는 정수 몫, %는 나머지이며 list는 순서가 있는 목록입니다. 각 세트 목록은 오래된 항목부터 최신 항목 순으로 블록 번호를 저장합니다. 코드는 읽기 전용 접근·실패 시 블록 적재·LRU만 모델링합니다.

def cache_trace(addresses, block_size, capacity, ways):
    if block_size <= 0 or capacity <= 0 or ways <= 0:
        raise ValueError("크기는 양수여야 합니다")
    if capacity % (block_size * ways):
        raise ValueError("용량이 블록 크기 × way 수로 나누어져야 합니다")
    sets = [[] for _ in range(capacity // (block_size * ways))]
    result = []
    for address in addresses:
        if address < 0:
            raise ValueError("음수 주소는 지원하지 않습니다")
        block = address // block_size
        group = sets[block % len(sets)]
        hit = block in group
        if hit:
            group.remove(block)
        elif len(group) == ways:
            group.pop(0)
        group.append(block)
        result.append("H" if hit else "M")
    return result

print(cache_trace([0, 16, 0, 16], 4, 16, 1))
print(cache_trace([0, 16, 0, 16], 4, 16, 2))
assert cache_trace([0, 1, 3, 4], 4, 16, 1) == ["M", "H", "H", "M"]
assert cache_trace([], 4, 16, 1) == []
for addresses, block_size, capacity, ways in [([-1], 4, 16, 1), ([0], 4, 15, 2), ([0], 0, 16, 1)]:
    try:
        cache_trace(addresses, block_size, capacity, ways)
    except ValueError:
        pass
    else:
        raise AssertionError("잘못된 입력을 거부해야 합니다")

출력은 ['M', 'M', 'M', 'M']와 ['M', 'M', 'H', 'H']입니다. 주소 0·1·3은 같은 블록이므로 서로 다른 주소라도 적중할 수 있습니다. 이 프로그램의 실행 시간으로 실제 CPU 캐시 속도를 측정하지는 않습니다.

직접 풀기: 용량을 유지한 비교

8비트 주소, 8바이트 블록, 32바이트 데이터 용량을 가진 캐시에서 0, 32, 0, 8, 32, 0을 읽습니다.

1. 직접 매핑의 오프셋·인덱스·태그 비트 수와 적중열을 구하세요.
2. 같은 용량의 2-way 캐시를 LRU로 운용할 때 적중열을 구하세요. 세트 0의 마지막 내용을 쓰세요.

힌트

먼저 주소를 블록 0, 4, 0, 1, 4, 0으로 바꾸세요. 직접 매핑은 세트 4개, 2-way는 세트 2개입니다. LRU 교체는 세트가 이미 두 블록으로 꽉 찬 실패에서만 필요합니다.

풀이와 오개념 점검

직접 매핑은 오프셋 3비트, 인덱스 2비트, 태그 3비트입니다. 블록 0과 4가 라인 0을 번갈아 차지하므로 M, M, M, M, M, M입니다. 블록 1의 접근은 별도 라인 1을 사용하지만 처음 읽으므로 실패합니다.

2-way는 오프셋 3비트, 세트 인덱스 1비트, 태그 4비트입니다. 세트 0에 블록 0·4가 함께 남고 블록 1은 세트 1로 갑니다. 결과는 M, M, H, M, H, H이며 마지막 세트 0은 LRU 순서로 [4, 0]입니다.

“같은 인덱스면 적중”이나 “주소가 바뀌면 반드시 실패”라고 생각했다면 태그와 블록의 역할을 다시 확인하세요. 나눗셈의 관계식은 b = 세트 수 × 태그 + 세트 번호입니다. 몫·나머지를 그냥 더하는 식이 아닙니다.

독립 문제: 먼저 적재한 것과 오래 사용하지 않은 것

같은 B=4·C=16·2-way의 빈 캐시에서 주소 0,16,32,16,48을 읽습니다. 블록열과 세트 번호를 구하고, 각 접근 뒤 세트 0의 LRU·FIFO 목록을 적으세요. 마지막 접근에서 각 정책은 무엇을 내보내나요? 그다음 주소 16 접근은 각 정책에서 H인가요, M인가요?

교체 문제 힌트

블록열은 0,4,8,4,12입니다. 세 번째 접근에서는 두 정책이 같은 블록을 내보내고, 네 번째 적중에서 순서가 갈라집니다.

교체 문제 풀이

모두 블록 번호가 짝수이므로 세트 번호는 0입니다. LRU 목록은 [0]→[0,4]→[4,8]→[8,4]→[4,12]입니다. FIFO 목록은 [0]→[0,4]→[4,8]→[4,8]→[8,12]입니다. 세 번째는 둘 다 블록 0을 내보내지만, 마지막은 LRU가 8, FIFO가 4를 내보냅니다. 따라서 다음 주소 16, 즉 블록 4는 LRU에서 H, FIFO에서 M입니다. “가장 먼저 들어온 블록”과 “가장 오래 접근하지 않은 블록”은 적중 뒤에 서로 달라질 수 있습니다.

다음 쓰기 정책·보조기억장치에서는 읽기 적중뿐 아니라 수정한 데이터가 아래 계층으로 언제 전달되는지 살펴봅니다. 개념 비교 자료는 MIT의 캐시 강의 구성에서 확인할 수 있습니다.