[Computer Architecture] Cache Memory: Block Mapping

+ 한국항공대학교 길현영 교수님의 컴퓨터구조론 과목 내용을 정리한 글입니다.

블록 사상 (Block Mapping)

캐시는 메모리보다 용량이 작기 때문에 다수의 메모리 블록이 동일한 캐시 블록에 사상(위치)한다.
 
1. 직접 사상
=> 메모리 블록을 정해진 하나의 캐시 블록에만 사상할 수 있다. (정해진 한 곳에만 위치 가능)
 
2. 완전 연관 사상
=> 메모리 블록을 어떤 캐시 블록에도 사상할 수 있다. (아무대나 위치 가능)
 
3. 집합 연관 사상 (직접 사상과 완전 연관 사상 절충)
=> 메모리 블록을 정해진 블록의 집합 내 어디든 사상할 수 있다. (정해진 여러 곳에 위치 가능)
 

< 가정 > - 시험

메모리 크기 = 512 byte
캐시 크기 = 128 byte
블록 크기 = 16 byte
워드 크기 = 4 byte
 
< 블록 개수 계산 >
=> 메모리 블록 개수: 512 byte ÷ 16 byte = 32개
=> 캐시 블록 개수: 128 byte ÷ 16 byte = 8개
 
< 표현하기위해 필요한 비트 수 >
1. 메모리 크기가 512(= 2^9) byte이므로 바이트 주소로 9bit가 필요하다.
2. 메모리 블록이 32개 이므로 블록 번호는 5bit가 필요하다.
3. 캐시 크기는 128(=2^7) byte이므로 바이트 주소로는 7bit가 필요하다.
2. 캐시 블록이 8개 이므로 블록 번호는 3bit가 필요하다.
 
< 오프셋 >
메모리와 캐시에서 하나의 블록은 동일하게 16byte이므로 블록 오프셋은 4bit이다.
- 블록 내에서 1byte를 선택하려면 블록 오프셋 4bit를 사용하고, 1 워드를 선택하려면 블록 오프셋의 상위 2bit를 사용해야한다.

 

+ 메모리 주소 = 메모리 시작 주소

가정에서의 주소와 메모리 구성

---

직접 사상 (Direct Mapping)

메모리 블록을 modulo(나머지)연산을 사용하여 정해진 캐시 블록에만 사상한다.
 
(저장할) 캐시 블록 번호 = (저장되어 있던) 메모리 블록 번호 mod 캐시 블록 개수
 

예제 직접 사상

 
< 예제 >
(캐시 메모리에 사상할) 블록 번호는 메모리 블록 번호를 8로 나눈 나머지이다.
- 메모리 블록 주소 중 나머지에 해당하는 하위 3bit (인덱스 필드)에 해당하는 캐시 블록 번호에 사상한다.
- 상위 2bit는 몫에 해당하므로 캐시 블록 번호와 무관하다.
ex) 메모리 블록 번호 00100, 01100, 10100, 11100가 캐시 블록 번호 100에 사상된다.
 
캐시 태그 메모리에 메모리 블록번호 상위 2bit를 저장한다.

---

직접 사상: 캐시 동작 과정

< 주소 010100000의 데이터 a 참조 (캐시 초기화 단계) >

+ 초기에 모든 유효 비트가 0이므로, 무조건 Miss가 발생한다. (초기에는 거의 실패: Cold Start)
 
1. CPU가 주소 010100000을 생성하여 캐시 메모리에 데이터를 요청한다.


2. 캐시는 주소를 CPU 태그(01), 인덱스(010), 블록 오프셋(0000)으로 분할한다.
+ CPU 태그: CPU에서 요청한 메모리 주소 태그
 
3. 인덱스 필드(010)가 가리키는 캐시의 태그를 추출한다.
 
4. CPU 태그와 캐시 태그를 비교한다.
(캐시 메모리의 해당 인덱스(010) 주소에 요청한 CPU 태그(01)이 저장되어있는지 확인 + 유효 비트 확인)
 
5. 유효 비트가 0이므로 캐시 실패 (Miss)가 발생한다.
- 모든 제어는 CPU가 할 수 있기 때문에 CPU에 알린다.
 
6. CPU는 메모리에 동일한 주소를 보내 데이터를 요청한다. (+ R/W 제어신호)
 
7. 메모리는 데이터 a가 있는 메모리 블록(주소: 01010)을 복사하여 캐시 메모리로 전송한다.
 
8. 메모리 블록을 인덱스 필드(010)가 가리키는 캐시 블록으로 사상하고 캐시 태그를 01로 갱신한 뒤 유효 비트를 1로 설정한다.
 
9. 블록 오프셋(0000)을 사용하여 캐시 블록에서 데이터 a를 추출하고 CPU에 전송한다.
 

a 참조 동작 과정

< 주소 010100100의 데이터 b 참조 >

1 ~ 4 과정은 a 참조와 유사하다.
 
5. 유효 비트가 1이며, 두 태그가 일치하므로 캐시가 적중(Hit)이 발생한다.
 
6. 블록 오프셋(0100)을 사용하여 캐시 블록에서 데이터 b를 추출하고 CPU에 전송한다.
 

b 참조 동작 과정

< 주소 000100000의 데이터 e 참조 >

+ 데이터 a와 e의 메모리 블록은 하위 3bit가 동일하므로 충돌이 발생한다.
 
1 ~ 4 과정은 a 참조와 유사하다.
 
5. 두 태그가 일치하지 않으므로 캐시 실패 (Miss)가 발생한다. (CPU에 알림)
 
6. CPU는 메모리에 동일한 주소를 보내어 데이터를 요청한다.
 
7. e가 있는 메모리 블록(주소: 00010)에 접근한다.
- 사상할 캐시 블록에 데이터 a를 가진 블록(주소: 01010)이 존재하므로 데이터 a를 포함하는 캐시 블록의 갱신 여부를 파악하고 쓰기 정책에 맞게 처리한다.
 
8. e를 포함하는 메모리 블록(주소: 00010)을 캐시 블록(010)으로 사상하고 태그를 00으로 갱신한다.
+ 유효 비트는 유지한다.
 
9. 블록 오프셋(0000)을 사용하여 캐시 블록에서 데이터 e를 추출하고 CPU에 전송한다.

e 참조 동작 과정

 

< 직접 사상의 장단점 >

장점
1. 태그의 길이가 짧다. (들어갈 방이 하나이기 때문)
2. CPU 태그를 하나의 캐시 태그와 비교하기 때문에 하나의 비교기만 있으면 가능하다.
3. 메모리 블록이 사상될 캐시 위치가 정해져 있어, 교체 방식이 필요없다.
=> 하드웨어 구현이 단순하고, 접근 속도가 빠르다.
 
단점
=> 적중률이 저조하다.
+ 동일한 캐시 블록에 사상되는 다른 메모리 블록을 번갈아 참조할 때, 캐시 블록에 심각한 충돌이 발생한다.
 
따라서 대용량 캐시 메모리일 경우에만 주로 직접 사상 방식을 이용한다.

---

완전 연관 사상 (Fully - Associative Mapping)

메모리 블록은 어떤 캐시 블록에도 사상이 가능하다.
 
캐시 블록 번호는 메모리 블록 번호와 무관하고, 메모리 블록의 어떤 정보도 포함하지 않는다.
 
캐시 블록이 어느 메모리 블록에 대응하는지 알기 위해 메모리 블록 번호 모두 태그로 사용한다.

예제 완전 연관 사상

 
< 예제 >
메모리 블록 번호 00100, 01100, 10100, 11100가 어느 캐시 블록 번호에도 사상될 수 있다.
ex) 메모리 블록 01100이 캐시 블록 번호 100에 사상되면, 캐시 블록 번호 100에 대응하는 태그는 01100이다.
 
캐시 태그 메모리에 메모리 블록번호를 모두 저장한다.

---

완전 연관 사상: 캐시 동작 과정

< 주소 010100000의 데이터 a 참조 (캐시 초기화 단계) >

1. CPU가 주소 010100000을 생성하여 캐시 메모리에 데이터를 요청한다.


2. 캐시 메모리는 주소를 CPU 태그(01010)과 블록 오프셋(0000)으로 분할한다.
 
3. CPU 태그와 모든 캐시 태그를 비교한다.
(캐시 태그 메모리에 요청한 CPU 태그(01010)이 저장되어있는지 확인 + 유효 비트 확인)
 
4. 모든 캐시 태그의 유효 비트가 0이므로 캐시 실패 (Miss)가 발생한다. (CPU에 알림)
 
5. CPU는 메모리에 동일한 주소를 보내 데이터를 요청한다. (+ R/W 제어신호)
 
6. 메모리는 데이터 a가 있는 메모리 블록(주소: 01010)을 복사하여 캐시 메모리로 전송한다.
 
7. 메모리 블록을 임의의 캐시 블록으로 사상하고 캐시 태그를 01010로 갱신한 뒤 유효 비트를 1로 설정한다.
(첫 번째 빈 캐시 블록으로 사상되었다고 가정)
 
9. 블록 오프셋(0000)을 사용하여 캐시 블록에서 데이터 a를 추출하고 CPU에 전송한다.

a 참조 동작 과정

< 주소 010100100의 데이터 b 참조 >

1 ~ 3 과정은 a 참조와 유사하다.
 
4. 유효 비트가 1이며, 일치하는 태그가 존재하므로 캐시가 적중(Hit)이 발생한다.
 
6. 블록 오프셋(0100)을 사용하여 캐시 블록에서 데이터 b를 추출하고 CPU에 전송한다.
 

b 참조 동작 과정

< 주소 000100000의 데이터 e 참조 >

1 ~ 3 과정은 a 참조와 유사하다.
 
4. 두 태그가 일치하지 않으므로 캐시 실패 (Miss)가 발생한다. (CPU에 알림)
 
5. CPU는 메모리에 동일한 주소를 보내어 데이터를 요청한다.
 
6. 데이터 e가 있는 메모리 블록(주소: 00010)에 접근하여 캐시 메모리로 가져온다.
 
7. 메모리 블록을 비어 있는 임의의 캐시 블록으로 사상한다. (두 번째 캐시 블록으로 메모리 블록을 사상)
 - 대응하는 두 번째 캐시 블록의 태그를 00010으로 갱신한다.
- 만약 빈 캐시 블록이 없으면, 캐시 교체 방식과 쓰기 정책에 따라 사용 중인 블록을 처리한다.
 
8. 블록 오프셋(0000)을 사용하여 캐시 블록에서 데이터 e를 추출하고 CPU에 전송한다.

e 참조 동작 과정

< 완전 연관 사상의 장단점 >

장점
직접 연관 사상보다 적중률이 높다. (시간적 Locality)
ex) a -> e -> a -> e (직접 연관 사상과 비교)
 
단점
1. CPU가 요청한 태그를 모든 캐시 태그와 병렬로 비교해야 하므로 8개의 비교기가 필요하다.
(직렬로 연결 시, 시간이 더 소요된다.)
2. 태그의 길이가 길다.
3. 직접 사상에 비해 속도가 느리고, 추가적인 하드웨어가 필요하다.
 
따라서 고가의 연관 메모리일 경우에만 주로 완전 연관 사상 방식을 이용한다.

---

집합 연관 사상 (Set - Associative Mapping)

메모리 블록은 정해진 장소들 내 어느 블록에나 위치 가능하다. (직접 사상 + 완전 연관 사상)
 
2개 이상의 블록으로 구성된 집합 구조이다.
 
n- 방향 집합 연관 사상
= 캐시 집합의 크기가 n개인 블록 (집합 연관도 = n)
ex) 2- 방향 집합 연관 사상은 2개의 캐시 블록 중 어디에든 메모리 블록을 사상할 수 있다.

예제 집합 연관 사상

캐시 집합 번호 = 메모리 블록 번호 mod 캐시 집합의 개수
 
< 예제 >
2- 방향 집합 연관 사상이고, 캐시 블록은 8개이므로 캐시 집합의 개수는 4개이다.
 
메모리 블록을 캐시 집합에 사상하려면 메모리 블록 번호를 4로 나눈 나머지 값을 사용한다.
- 메모리 블록 번호의 하위 2bit를 인덱스 필드로 사용한다.
- 인덱스 필드는 하나의 집합을 색인하므로, 집합 번호(set number)리고도 불린다.
 
메모리 블록 번호의 상위 3bit는 태그로 사용된다.

---

집합 연관 사상: 캐시 동작 과정

< 주소 010100000의 데이터 a 참조 (캐시 초기화 단계) >

1. CPU가 주소 010100000을 생성하여 캐시 메모리에 데이터를 요청한다.

2. 캐시 메모리는 주소를 CPU 태그(010)과 블록 오프셋(0000)으로 분할한다.
 
3.인덱스 필드가 가리키는 캐시 메모리의 태그 2개를 추출한다. (집합을 가리키므로)
 
4. CPU 태그와 2개의 캐시 태그를 비교한다.
(캐시 태그 메모리에 요청한 CPU 태그(01010)이 저장되어있는지 확인 + 유효 비트 확인)
 
5. 유효 비트가 0이므로 캐시 실패 (Miss)가 발생한다. (CPU에 알림)
 
6. CPU는 메모리에 동일한 주소를 보내 데이터를 요청한다. (+ R/W 제어신호)
 
7. 메모리는 데이터 a가 있는 메모리 블록(주소: 01010)을 복사하여 캐시 메모리로 전송한다.
 
8. 메모리 블록을 인덱스 필드가 지시하는 캐시 집합에 사상하고 캐시 태그를 010로 갱신한 뒤 유효 비트를 1로 설정한다.
(하나의 캐시 집합이 2개의 블록이므로, 편의상 첫 번째 빈 캐시 블록에 사상한다.)
 
9. 블록 오프셋(0000)을 사용하여 캐시 블록에서 데이터 a를 추출하고 CPU에 전송한다.

a 참조 동작 과정

< 주소 010100100의 데이터 b 참조 >

1 ~ 4 과정은 a 참조와 유사하다.
 
5. 2개의 캐시 태그 중 일치하는 태그가 존재하므로 캐시가 적중(Hit)이 발생한다.
 
6. 블록 오프셋(0100)을 사용하여 캐시 블록에서 데이터 b를 추출하고 CPU에 전송한다.

b 참조 동작 과정

 

< 주소 000100000의 데이터 e 참조 >

1 ~ 4 과정은 a 참조와 유사하다.
 
5. 일치하는 캐시 태그가 없으므로 캐시 실패 (Miss)가 발생한다. (CPU에 알림)
 
6. CPU는 메모리에 동일한 주소를 보내어 데이터를 요청한다.
 
7. 데이터 e가 있는 메모리 블록(주소: 00010)을 복제하여 캐시 메모리로 가져온다.
 
8. 데이터 e를 포함한 메모리 블록을 인덱스 필드(10)가 지시하는 캐시 집합 내 빈 블록에 사상하고, 캐시 태그를 000으로 갱신한다.
- 캐시 집합에 빈 캐시 블록이 없으면, 캐시 교체 방식에 따라 블록 하나를 추출하고, 쓰기 정책을 적용한다.
 
9. 블록 오프셋(0000)을 사용하여 캐시 블록에서 데이터 e를 추출하고 CPU에 전송한다.

e 참조 동작 과정

< 집합 연관 사상의 장단점 >

장점
1. 완전 연관 사상에 비해 전체 태그 대신 일부 태그에 대해 연관 탐색을 수행한다.
2. 적은 개수의 비교기가 필요하다.

3. 태그의 길이가 짧다.

 

=> 완전 연관 사상에 비해 비용이 저렴하고 속도도 빠르다.=> 완전 연관 사상보다 적중률이 떨어지지만 직접 사상보다는 적중률이 높다.

 
직접 사상과 완전 연관 사상은 집합 연관 사상의 일종이다.
- 하나의 캐시 집합에 1개 블록만 있다면 직접 사상, 전체 캐시 블록이 하나의 캐시 집합이라면 완전 연관 연관 사상이다.