[컴퓨터 구조] 캐시 메모리 (Cache Memory) (1)
주기억장치로 사용되는 반도체 기억장치 부품들의 액세스 속도가 최근 크게 개선되었지만, 여전히 CPU의...
blog.naver.com
https://hyeo-noo.tistory.com/308
[컴퓨터 구조] 캐시 메모리
캐시 메모리 CPU와 주기억장치의 속도차이를 보완하기 위하여 그 사이에 설치하는 반도체 기억장치. 용어 정리 CPU가 원하는 데이터가 이미 캐시에 적재되어 있는 상태를 캐시 적중(cache hit)이라
hyeo-noo.tistory.com
위 블로그글을 공부한 내용입니다. 자세한 내용은 위 블로그의 시리즈글을 참고해주세요.
캐시 메모리란?
CPU와 주기억장치의 속도차이를 보완하기 위해 그 사이에 설치하는 반도체 기억장치
CPU의 성능과 비교했을 때 주기억장치에 접근하여 명령어와 데이터를 인출하는 과정은 시간 비용이 상대적으로 높습니다.
캐시 메모리를 사용하면 주기억장치까지 가지 않고 자주 사용하는 데이터를 사용할 수 있으므로 CPU 의 사용효율을 높일 수 있습니다.
또한 CPU에는 이러한 캐시 메모리가 2~3개 정도 사용됩니다. (L1, L2, L3 캐시 메모리라고 부른다)
속도와 크기에 따라 분류한 것으로, 일반적으로 L1 캐시부터 먼저 사용됩니다. (CPU에서 가장 빠르게 접근하고, 여기서 데이터를 찾지 못하면 L2로 감)
캐시 용어
- 캐시 적중(cache hit) : 원하는 데이터가 이미 캐시에 적재되어 있는 상태
- 캐시 미스(cache miss) : 원하는 데이터가 이미 캐시에 없는 상태
캐시 미스 경우 3가지
Cold miss
캐시가 처음 비어 있는 상태에서 cache miss 가 발생하는 경우
Capacity miss
캐시의 용량이 부족해서 발생하는 miss
Conflict miss
캐시의 용량은 충분하지만, 같은 캐시 메모리 주소에 할당을 해야하는 경우 발생하는 miss
캐시 적중률
캐시 적중률은 CPU가 원하는 데이터가 캐시에 있을 확률입니다.
반대로 1-H 는 캐시 미스율이 됩니다.
평균 기억장치 액세스 시간
Tc는 캐시 액세스 시간이고, Tm은 주기억장치 액세스 시간을 나타냅니다.
이러한 식에 근거하여 캐시 적중률이 높아질 수록 평균 액세스 시간은 캐시의 액세스 시간에 접근하게 된다는 것을 알 수 있습니다.
그런데, 캐시 적중률은 프로그램과 데이터의 '지역성(locality)'에 크게 의존합니다.
지역성의 원리 (principle of locality)
- 시간적 지역성(temporal locality) : 최근에 엑세스된 프로그램 코드나 데이터가 가까운 미래에 다시 엑세스될 가능성이 높아지는 특성입니다. 예를 들어 반복 루프 프로그램이나 서브루틴들은 반복적으로 호출되며, 공통 변수들도 빈번히 엑세스 됩니다.
- 공간적 지역성(spatial locality) : 기억장치 내에 서로 인접하여 저장되어 있는 데이터들이 연속적으로 엑세스될 가능성이 높아지는 특성을 말합니다. 예를 들어, 표나 배열 데이터들이 저장되어 있는 기억장치 영역은 그들에 대한 연산이 수행되는 동안에 집중적으로 엑세스됩니다.
- 순차적 지역성(sequential locality) : 분기가 발생하지 않는 한, 명령어들은 기억장치에 저장된 순서대로 인출되어 실행됩니다. 일반적인 프로그램에서는 순차적 실행과 비순차적 실행의 비율이 대략 5:1 정도인 것으로 알려져 있습니다.
캐시 설계의 공통적인 목표
- 캐시 적중률의 극대화 : CPU가 원하는 정보가 캐시에 있을 확률을 높여야 합니다.
- 캐시 액세스 시간의 최소화 : 캐시 적중 시에 캐시로부터 CPU로 정보를 인출해오는데 걸리는 시간을 가능한 한 단축시켜야 합니다.
- 캐시 실패에 따른 지연시간의 최소화 : 캐시 미스가 발생한 경우에 주기억장치로부터 캐시로 정보를 읽어오는데 걸리는 시간을 최소화 시켜야합니다.
- 주기억장치와 캐시간의 데이터 일관성 유지 및 그에 따른 오버헤드의 최소화 : CPU가 캐시의 내용을 변경하였을 때, 주기억장치에 그 내용을 갱신하는 절차 때문에 발생하는 지연시간을 최소화 시켜야합니다.
캐시 설계에 고려해야할 요소
캐시용량
캐시의 용량이 커질수록 적중률이 높아집니다. 그러나 비용도 같은 비율로 상승하기 때문에 캐시의 용량은 비용과 상호 조정을 통해 적절히 결정해야합니다.
또한 캐시 용량이 커질 수록 주소 해독 및 정보 인출을 위한 주변회로가 더 복잡해지는 문제도 발생합니다.
인출 방식
주기억 장치로 부터 정보를 인출해오는 방식도 캐시 적중률에 많은 영향을 줍니다.
- 요구 인출(demand fetch) : 필요한 정보만 인출해오는 방법
- 선인출(prefetch) : 필요한 정보 외에 앞으로 필요할 것으로 예측되는 정보도 미리 인출해는 방법입니다. 즉 CPU가 원하는 정보를 인출할때 그 정보와 근접한 위치에 있는 정보들을 함께 인출하여 캐시에 적재합니다.
캐시 내부 구조
직접 사상 (Direct Mapping)
직접 사상 방식에서는 주기억장치들의 블록이 어느 한 캐시 라인으로만 매핑 될 수 있습니다.
이러한 방식을 구현하기 위해, 주기억장치 주소는 다음과 같이 세 개의 필드로 구성됩니다.
위 주소의 상위 (T+L) 비트들은 주기억장치의 2^(T+L)개의 블록들 중 하나를 지정합니다. 그리고 최하위 W 비트 들은 2^W개의 단어들로 구성된 각 블록 내의 단어들을 구분하는데 사용됩니다.
캐시 제어기(cache controller) 는 최상위 T개의 비트들을 태그 번호로 해석하고 , L개의 비트는 라인 번호로 해석합니다.
라인번호는 캐시의 2^L개의 라인들 중 주기억장치의 블록이적재 될 수 있는 위치를 알려줍니다.
태그번호는 같은 캐시 라인을 공유하는 주기억장치들을 서로 구분하는데 사용됩니다.
캐쉬 라인 번호 = 주기억 장치 블록 번호 mod 캐시 라인 수
이제 주기억장치와 캐시가 아래와 같은 용량을 가진다고 가정해보겠습니다.
- 주기억장치의 용량은 128바이트이고, 바이트 단위로 주소를 지정하면 2^7 을 가지므로 주기억 장치의 주소는 7비트일 것 입니다.
- 단어의 길이는 한 바이트인 것으로 가정합니다.
- 주기억장치의 블록 크기를 4단어로 합니다. 따라서 블록의 수는 128/4 = 32개가 됩니다.
- 캐시의 크기는 32바이트 입니다.
- 주기억장치의 블록 크기가 4 바이트 이므로 캐시 라인의 크기도 4바이트가 되어야하며, 결과적으로 라인의 수 m = 32/4 = 8개가 됩니다.
블록 내의 단어의 수가 4개이기 때문에 각 단어를 구분하기 위해 W = 2 비트가 필요하고, 라인의 수(m)가 8개 이므로 L = 3 비트 , 태그 필드는 나머지 2비트를 가지게 됩니다.
캐시 라인의 수 m = 8 이므로 각 기억장치 블록이 공유하게 될 캐시 라인의 번호는 i mod 8에 의해 결정됩니다.
위처럼 하위 3비트가 111 인 경우 모두 캐시의 7번 라인에 저장 될 수 있게됩니다. 이때 태그 비트가 사용되어 캐시 라인에 어떤 블록이 저장되었는지 구분할 수 있게 해줍니다.
위 예시에선 00 이 첫번째 블록, 01 이 두번째블록, 10 이 세번째블록 , 11이 네번째 블록이 되겠습니다.
위 예시는 하나의 데이터가 4바이트를 가지며, 한 블록은 32 바이트이고 따라서 128바이트의 주기억 장치에서 4개의 블록을 가지게 됩니다.
그럼 위 예시를 사용하여 한번 문제 풀듯이 개념을 적용해 봅시다.
1. 0101000
캐시 미스가 발생합니다. 0101000 은 010 = 2번 라인을 가르키며 현재 2번 라인에는 11 태그인 데이터가 있으므로 , 데이터 필드를 'info' 로 대체하고 태그를 01 로 변경합니다.
2. 0001101
캐시 적중이 발생합니다. 011 라인에 저장될 수 있고 태그 또한 일치하기 때문입니다.
장단점
- 장점 : 간단하고 빠르며 구현하는 비용이 적게든다.
- 단점 : Conflict Miss가 발생한다.
유효비트
위 예시에는 나와있지 않지만 캐시 블록이 유효한 정보를 가지고 있는지 판단할 수 있는 방법이 필요합니다.
예를 들어 컴퓨터를 처음 켜서 프로세서가 작업을 시작할 때 캐시에는 아무런 값이 없어야 하지만 사실은 쓰레기 값들로 채워져 있을 것입니다.
이때 캐시 전체를 0 으로 초기화 하여 사용하기보다, 해당 캐시가 유효한 데이터인지 아닌지 확인하는 비트 사용하는 방식이 더 효율적입니다.
즉, 캐시 엔트리마다 유효 비트(Valid bit)를 추가해서 엔트리에 유효한 데이터를 가지고 있는지 아닌지를 표시하는 방법을 많이 사용합니다.
해당 비트가 0인 경우 해당 엔트리에 들어있는 데이터는 유효하지 않은 것으로 판단합니다.
완전-연관 사상 (Fully-associative Mapping)
비어있는 캐시 메모리가 있으면, 마음대로 주소를 저장하는 방식입니다.
조건이나 규칙이 없어서 특정 캐시 Set 안에 있는 모든 블럭을 한번에 찾아 원하는 데이터가 있는지 검색해야 합니다.
CAM 이라는 특수한 메모리 구조를 사용함으로 가격이 매우 비쌉니다.
이제 주기억장치와 캐시가 아래와 같은 용량을 가진다고 가정해보겠습니다.
- 주기억장치의 용량은 128바이트이고, 바이트 단위로 주소를 지정하면 2^7 을 가지므로 주기억 장치의 주소는 7비트일 것 입니다.
- 단어의 길이는 한 바이트인 것으로 가정합니다.
- 주기억장치의 블록 크기를 4단어로 합니다. 따라서 블록의 수는 128/4 = 32개가 됩니다.
- 캐시의 크기는 32바이트 입니다.
- 주기억장치의 블록 크기가 4 바이트 이므로 캐시 라인의 크기도 4바이트가 되어야하며, 결과적으로 라인의 수 m = 32/4 = 8개가 됩니다.
완전 연관 사상 방식에서 7비트 길이의 기억장치 주소는 다음과 같이 두개의 필드로 나누어진 것으로 해석됩니다.
즉 주기억장치의 주소는 5비트 태그 필드와 2비트 단어 필드로 구성됩니다.
그럼 위 예시를 사용하여 한번 문제 풀듯이 개념을 적용해 봅시다.
1. 1011000
3번 라인에 해당 블록이 적재되어 있으므로 캐시 적중이 발생합니다.
2. 0010110
캐시 라인에 해당 블록이 존재하지 않기 때문에 캐시 미스가 발생하며 첫번째 빈 라인인 5번 라인에 적재됩니다. 태그는 00101이 됩니다.
장단점
- 장점 : 캐시에 적재할 라인선택이 자유롭다.
- 단점 : 조건이나 규칙이 없어서 특정 캐시 Set 안에 있는 모든 블럭을 한번에 찾아 원하는 데이터가 있는지 검색해야 한다. CAM 이라는 특수한 메모리 구조를 사용함으로 가격이 매우 비싸다.
세트 연관 사상 (Set Associative Mapping)
직접 사상 방식(Direct Mapping)과 완전 연관 사상 방식(Fully Associative Mapping)의 중간형입니다.
Direct에 비해 검색 속도는 느리지만, 저장이 빠르고 Fully에 비해 저장이 느린 대신 검색이 빠릅니다.
세트 연관 사상은 각 세트에 두개 이상의 라인이 구성 됩니다. 예시를 들어 설명해보겠습니다.
- 주기억장치의 용량은 128바이트이고, 바이트 단위로 주소를 지정하면 2^7 을 가지므로 주기억 장치의 주소는 7비트일 것 입니다.
- 단어의 길이는 한 바이트인 것으로 가정합니다.
- 주기억장치의 블록 크기를 4단어로 합니다. 따라서 블록의 수는 128/4 = 32개가 됩니다.
- 캐시의 크기는 32바이트 입니다.
- 주기억장치의 블록 크기가 4 바이트 이므로 캐시 라인의 크기도 4바이트가 되어야하며, 결과적으로 라인의 수 m = 32/4 = 8개가 됩니다.
위 예시에서 라인 수는 8개 이며 세트 당 2개씩의 라인을 둔다고 가정하면 세트수는 8/2 = 4개가 됩니다.
세트 필드의 2비트는 4개의 캐시 세트들 중 하나를 선택하는데 사용되고, 태그 필드가 3비트이므로 각 캐시 세트는 8개의 주기억장치 블록들에 의해 공유되며 그들 중 두개가 동시에 그 세트내에 적재 될 수 있습니다.
이와 같이 각 세트에 라인이 두개가 있는 경우를 2way 세트 연관 사상이라고 말하며, 4개가 있는 경우를 4way 세트 연관 사상이라고 말합니다. 즉, 세트당 라인이 k개씩 있으면 k-way 세트 연관 사상이라고 부릅니다.
k-way 세트 연관 사상에서 같은 세트를 공유하는 블록들 중 k개는 세트 내 k개 의 라인들 중 어느곳에든 동시에 적재 될 수 있습니다.
만약 세트 내의 어느 태그도 주소의 태그와 일치하지 않는다면, 캐시 미스가 발생한 것이므로 주기억장치 액세스가 시작되고 교체 알고리즘에 의하여 k개의 라인 중 하나를 선택한 다음 그 라인에 새로운 블록이 적재 됩니다.
다음은 2 - way 세트 연관 사상의 기억장치 주소 입니다.
아래 예시를 사용하여 문제를 풀어보도록 하겠습니다.
1. 1011010
10(2번) 세트를 가르키고 태그가 101 로 일치하는 라인이 존재합니다. 따라서 캐시 적중 입니다.
2. 1110101
01(1번) 세트를 가르킵니다. 해당 세트에 블록이 존재하지만 태그가 111과 일치하지 않습니다. 따라서 캐시 미스가 발생하며 비어있는 라인에 블록이 적재됩니다.
3. 1000000
00(0번) 세트를 가르킵니다. 해당 세트의 태그 들과 100 태그와 일치하는 것이 없습니다. 따라서 교체 알고리즘에 의하여 둘중 하나의 블록과 새로운 블록이 교체 됩니다.
세트당 두개씩의 라인을 가지는 2 way 조직이 가장 보편적으로 사용되고 있는 세트-연관 조직입니다. 이 조직을 사용하면 직접 사상보다 적중률이 훨씬 더 높아집니다. 4 way 세트 연관은 비교적 적은 추가 비용으로 성능을 더 향상시킬 수있으나, 세트당 라인을 그 이상으로 증가시키더라도 효과는 별로 더 높아지지 않는 것으로 알려져 있습니다.
사상 방식의 확장
위 내용까지는 실제로는 사용될 수 없는 매우 작은 용량의 주기억장치와 캐시를 가정하여 설명하였습니다.
이번에는 실제 사용될만한 예시를 사용하여 세트-연관 사상 방식으로 캐시 조직을 구성하고 분석해봅니다.
- 주기억장치의 용량은 16M(2^24)바이트이고, 따라서 주기억 장치의 주소는 24비트일 것 입니다.
- 주기억장치는 4바이트 크기의 블록들로 구성됩니다. 따라서 블록의 수는 2^24/2^2 = 2^22개가 됩니다. 단어의 길이는 한 바이트입니다.
- 캐시의 크기는 64K(2^16)바이트 입니다.
- 주기억장치의 블록 크기가 4 바이트 이므로 캐시 라인의 크기도 4바이트가 되어야하며, 결과적으로 라인의 수 m = 2^16/2^2 = 2^14개가 됩니다.
캐시에는 전체적으로 2^14 개의 라인들이 있지만, 이들이 2^13개의 세트들로 나누어지므로 각 세트에는 라인이 두 개씩 존재하게 됩니다. 따라서 13비트 세트 번호는 세트들 중 하나를 선택해줍니다. 주소의 태그 필드는 9비트 이므로 , 각 세트를 공유할 수 있는 블록의 수는 2^9개가 되며 그들 중의 두개가 동시에 그 세트내에 적재 되어 있을 수 있습니다.
교체 알고리즘
1. 최소 최근 사용(Least Recently Used, LRU)
사용되지 않은 채로 가장 오랫동안 적재되어 있던 블록을 교체하는 알고리즘 입니다.
2-way 세트 연관 방식에서는 각 라인이 USE 비트를 가지고 있도록 함으로써 이 알고리즘을 구현할 수 있습니다.
어떤 라인이 액세스되면, 그 라인의 USE 비트는 1로 세트됩니다. 그리고 그 세트내의 다른 라인의 USE 비트는 0으로 리셋 됩니다. 만약 새로운 블록이 그 세트로 적재된다면, USE 비트가 0으로 리셋됩니다. 더 최근에 사용되었던 데이터들이 앞으로도 다시 사용될 가능성이 높다는 가정이 맞는 경우가 실제로 많기 때문에 LRU 알고리즘은 높은 적중률을 보여줍니다.
2. FIFO(Fist-In-First-Out, FIFO)
캐시에 적재된지 가장 오래된 블록을 교체하는 것입니다.
3. 최소 사용 빈도 (Least Frequently Used, LFU)
캐시에 적재된 이후 참조되었던 횟수가 가장 적은 블록을 교체하는 것입니다. LFU 알고리즘을 구현하려면 각 라인에 '카운터(counter)를 설치해야 하기 때문에 하드웨어가 복잡해집니다.
4. 임의(Random)
후보 라인들 중 한 라인을 랜덤으로 선택하는 방법
아래 문제를 풀어봅시다.
H = 3/11
'CS > 컴퓨터구조' 카테고리의 다른 글
| 패리티 비트 & 해밍 코드 (0) | 2023.04.04 |
|---|---|
| CPU의 구조와 기능 (0) | 2023.04.04 |
| 컴퓨터 시스템의 개요 (0) | 2023.04.03 |
| 캐시 메모리의 쓰기 정책 / 버퍼와 캐시의 차이 (0) | 2023.04.02 |
| 부동소수점에 대한 이해 (0) | 2023.03.31 |