11. 캐시 메모리 (2/4) 사상(mapping)

캐시는 메모리보다 용량이 작기 때문에, 캐시 미스가 발생할 수 밖에 없다.

따라서, 메모리 블록을 어떻게 교체할 지에 대한 전략들이 있다.

 

교체 방식에는 대표적으로 3가지가 있다.

1. 직접 매핑 : 오직 1:1

2. 완전 연관 매핑 : 아무데나 사상 가능

3. 집합 연관 매핑 : 1 2번의 절충안으로, 정해진 블록의 집합내 어디서든 사상 가능

 

예를 들자면,

빅 엔디안 기반인 환경에서,

512바이트의 메모리와, 128바이트의 캐시를 가지고 있다.

16바이트의 블록을 가지고 있고, 워드는 4바이트다.

 

계산해보면

메모리 주소는 512 = 2^9 이므로, 9비트

캐시 주소는 128 = 2^7 이므로 7비트다.

여기서 블록이 16 = 2^4 이므로, 각각의 주소에 4비트를 차지한다.

 

정리하면.

메모리 주소

캐시 주소

메모리의 블록 번호 5비트는 매핑을 통해 캐시의 블록 번호 3비트에 매치된다.

 

1. 직접 사상

직접 사상은 모듈로(Modulo)연산을 통해 메모리 블록을 정해진 캐시 블록에만 매핑한다.

 

캐시 블록 번호 = 메모리 블록 번호 mod 캐시 블록 개수

 

대충 캐시 블록 번호는 3비트이므로, 메모리 블록 번호의 하위 3비트를 인덱스로 쓴단 얘기다.

이런 식이다.

직접 사상의 메모리 비트 구조

 

캐시 블록 번호가 3비트이므로 캐시 블록 범위는 이진수 000~111 까지 8개고

메모리는 00000, 01000, 10000, 11000 같이 하위 3비트가 000인 메모리 블록들은

캐시 블록 번호 000에 매핑된다.

 

그런데, CPU는 캐시 블록 번호 000에 있는 데이터가 메모리 블록번호 00000 인지 01000인지 구분할 수 없다.그렇기 때문에, 메모리 블록을 적재할 때, 메모리 블록의 태그 비트를 태그 메모리에 저장한다.만약 이미 다른 블록이 있다면? 그냥 교체해버리면 된다.

 

이렇기 때문에, 직접 사상은 교체 방식을 신경쓸 필요가 없어서,HW구현이 단순하고, 접근속도가 빠르다.하지만 매번 교체를 하기 때문에, 동일 캐시 블록에 매핑되는 다른 메모리가번갈아 실행되면 매우 낮은 적중률을 보여준다.

 

2. 완전 연관 사상

위에선 지정된 위치에 매핑하기 위해 인덱스가 필요했지만, 여기엔 그런 건 없다. 그냥 빈 자리 들어가면 끝

 

그렇기에, 캐시 블록 번호는 메모리 블록 번호와 무관하고,메모리 블록의 어떤 정보도 포함하지 않는다.

 

그렇기에, 메모리 블록 비트 전부를 캐시 태그로 사용한다.

 

다만 자유자재로 매핑이 되다보니, 블록 교체 방식을 신경 쓸 필요가 있다.이 부분은 다음 장에서 알아본다.

 

이 방식의 문제는, CPU가 요청한 태그를 모든 캐시 태그와 비교해야 하기 때문에,

병렬 비교가 필수이고, 고가의 메모리가 필요하다.

여기서는 8개의 인덱스를 병렬로 비교해야 하니 8 개의 비교기가 필요하다.교체 방식만 적절하게 정해준다면, 직접 사상에 비해 높은 캐시 히트를 보인다.

 

3. 집합 연관 사상

위의 1번과 2번을 절충한 방식이다.

 

직접 사상처럼 메모리 블록은 정해진 인덱스에만 들어갈 수 있지만, (직접 사상)이번에는 블록이 여러개의 집합으로 이루어져, 그 집합 내에 아무 자리나 들어가면 된다. (완전 연관 사상)

 

N개 이상의 블록으로 구성된 집합을N-방향 집합 연관 사상이라고 한다.

 

집합 연관 사상은 다음 모듈로 연산으로 캐시 집합을 결정한다.

 

캐시 집합 번호 = 메모리 블록 번호 % 캐시 집합의 개수

 

예시에서는 캐시 블록이 8개이고, 2-방향 연관사상이면,

집합의 크기가 2개이므로, 캐시 집합의 개수는 4개이다.

정리하면, 메모리 블록의 하위 2비트를 인덱스 필드로 사용한단 얘기다.

집합 연관 사상의 메모리 비트 구조

 

예를 들면,

00000, 00100, ... 11100 은 하위 2비트가 각각 00이므로,

동일한 캐시 집합에 매핑된다.

 

집합 연관 사상은 전체 태그 대신, 일부 태그에 대해 탐색을 수행하기 때문에,

비교 횟수가 적다.  (비교기 2개만 필요)

 

 

출처 : 컴퓨터 아키텍처 컴퓨터 구조 및 동작 원리 (한빛 아카데미)