03 캐시 기억 장치
기억 장치의 액세스 시간이 길면, CPU의 처리 속도가 빨라도 시스템 성능이 낮아짐
캐시
; CPU의 처리 속도와 기억 장치의 액세스 시간의 격차를 줄이기 위해 등장한 것
캐시는 CPU와 인접한 장소에 위치 or CPU 내부에 포함됨
SRAM을 사용하여 DRAM을 사용하는 주기억 장치의 액세스 시간보다 짧다.
SRAM이 훨씬 고가이기 때문에 캐시의 저장 용량은 주기억 장치의 저장 용량에 비해 적다.
캐시의 동작
(1) 캐시기억장치가 없는 컴퓨터 시스템의 기억장치 접근
- CPU가 명령어와 데이터를 인출하기 위해서 주기억장치에 접근
- 주기억장치에서 명령어나 필요한 정보를 획득하여 CPU 내의 명령어 레지스터 등에 저장
(2) 캐시기억장치를 포함하고 있는 컴퓨터 시스템
- CPU가 명령어 또는 데이터를 인출하기 위해 주기억장치보다 캐시기억장치를 먼저 조사
- CPU가 명령어를 인출하기 위해 캐시기억장치에 접근하여 그 명령어를 찾았을 때 적중(hit)이라고 하고, 명령어가 존재하지 않아 찾지 못하였을 경우를 실패(miss)라고 한다.
if) 캐시에 명령어가 없을 경우
- 주기억장치에서 필요한 정보를 획득하여 캐시기억장치에 전송
- 캐시기억장치는 얻어진 정보를 다시 중앙처리장치로 전송
else)
- 캐시기억장치가 1002번지의 워드를 저장하고 있는지 검사하고, 1002번지 워드가 캐시기억장치 내에 존재하면 적중(hit)이 된다.
- 캐시 기억장치에서 얻어진 정보를 중앙처리장치로 직접 전송한다. 주기억장치를 거치는 것보다 훨씬 빠른 속도로 원하는 정보를 획득하게 된다.
- 캐시기억장치의 동작은 기억장치 참조의 지역성에 의해 가능
중앙처리장치의 주기억장치 참조는 제한된 영역에서만 이루어짐
짧은 시간 동안 중앙처리장치가 접근하는 범위는 지역적으로 제한됨
동작 흐름도
(1) CPU가 기억 장치에서 어떤 정보(명령어 또는 데이터)를 읽으려는 경우 해당 정보가 캐시가 있는지 먼저 검사
(2) 있다면 해당 정보를 즉시 읽어 들이고, 없다면 해당 정보를 주기억 장치에서 캐시로 적재한 후 읽어들임
위의 과정이 반복되면, 어느 시점부터는 주기억 장치의 내용 중 많은 부분들이 캐시에 복사되어 있는 상태가 됨
히트와 미스
히트 : CPU에 필요한 정보가 캐시에 기억되어 있는 것
미스 : CPU에 필요한 정보가 캐시에 없는 것
히트율(H) : 기억 장치 액세스 중에서 캐시에 히트되는 비율
미스율(1-H) : CPU에 필요한 정보가 캐시에 없을 확률
평균 액세스 시간(Ta)
Tc는 캐시 액세스 시간, Tm은 주기억 장치 액세스 시간이다.
Tc+Tm의 경우 Tc의 시간이 지극히 적게 소요되기 때문에 Tm과 유사하다고 본다.
예제 6-5
평균 액세스 시간
60%를 예로 들면, 평균 액세스 시간은
0.6*5ns + 0.4*50ns = 23ns가 된다.
캐시의 히트율이 높아질수록 평균 액세스 시간은 캐시의 액세스 시간에 근접하게 된다.
그래프
참조지역성
- 공간적 지역성; 기억 장치 내에 서로 인접하여 저장되어 있는 데이터들이 연속적으로 액세스 될 확률이 높아지는 특성
- ex) 표나 배열의 데이터들이 저장되어 있는 기억 장치 영역은 관련 연산이 수행되는 동안 자주 액세스됨
- 시간적 지역성; 최근 액세스된 명령어나 데이터가 가까운 미래에 다시 액세스 될 확률이 높아지는 특성
- ex) 서브루틴이나 루프 프로그램들은 반복적으로 호출되며, 공통 변수들도 자주 액세스됨
캐시 메모리 설계의 공통적인 목표
- 캐시 히트율 극대화
- 캐시 히트인 경우 캐시에서 정보를 읽어 오는 시간을 최소화
- 캐시 미스인 경우 주기억 장치에서 캐시로 정보를 가져오는데 걸리는 시간을 최소화
- 캐시의 내용이 변경되었을 경우 주기억 장치에 해당 내용을 갱신하는 데 소요되는 시간을 최소화
위의 목표를 만족하기 위해서는 아래의 설계 요소들을 만족해야 한다.
[1] 캐시 용량
캐시 크기는 비트당 평균 비용이 주기억 장치의 평균 비용과 비슷해질 만큼 작아야 하며, 전체 평균 액세스 시간도 캐시의 액세스 시간에 근접할 만큼 커야 함
- 용량이 증가할수록 히트율이 높아짐 ⇒ 비용 또한 증가
- 캐시 용량이 증가할수록 주소 해독 및 정보 인출을 위한 주변 회로가 복잡해짐 ⇒ 액세스 시간이 길어짐+) CPU 칩 또는 메인보드의 공간도 제한을 받음
[2] 사상 방식
블록
; 주기억 장치와 캐시 사이에 이동되는 정보 단위
한 블록 == 연속된 워드, 보통 2의 거듭제곱 수의 워드로 구성된다.
블록은 K개의 워드로, 주기억 장치는 워드 2^n개로 구성되고 각 워드는 n비트의 주소로 지정됨
따라서, 주기억 장치에저 전체 블록의 개수는 2^n/K개가 된다.
라인
; m개로 구성되며, 각 라인에는 워드 K개가 저장됨
라인 크기 == 주기억 장치의 블록 크기
캐시의 용량이 주기억장치보다 작기 때문에 캐시 라인의 수는 주기억 장치의 블록 수보다 작다
태그
; 각 캐시 라인에 어떤 블록이 적재되어 있는지 구분해주는 정보
사상방식
; 주기억 장치의 블록이 어느 캐시 라인에 들어갈 것인지 결정하는 방법
(1) 직접 사상 : 주기억 장치의 블록은 정해진 하나의 캐시 라인에만 들어갈 수 있다.
(2) 완전-연관 사상 : 주기억 장치의 블록은 어떤 캐시 라인에도 들어갈 수 있다.
(3) 세트-연관 사상 : 직접 사상과 완전-연관 사상을 절충한 방법으로 캐시 라인들을 세트 몇 개로 나누어서 주기억 장치의 블록은 세트 하나에만 들어갈 수 있다.
각 사상 방식을 설명할 예
- 주기억 장치의 용량은 128바이트다. 따라서 주소 지정에 7비트가 필요하다. 바이트 단위로 주소가 지정되며 워드 길이는 1바이트다.
- 캐시의 용량은 32바이트다. 따라서 캐시의 주소 지정에 5비트가 필요하다.
- 블록 크기는 4바이트(4워드)이므로 주기억 장치에는 128/4 = 32개의 블록이 있다.
- 블록 크기가 4바이트이므로 캐시 라인의 크기도 4바이트가 되며, 결과적으로 캐시 라인의 수는 8(=32/4)개다.
주기억 장치 블록 32개를 캐시 라인 8개에 배치해야 하므로 위와 같이 블록 번호 5비트를 캐시 라인 3비트로 매핑해야 한다.
직접 사상
; 주기억 장치 블록들이 지정된 어느 한 캐시 라인으로만 매핑될 수 있는 방식
직접 사상에서 주기억 장치 주소는 태그, 라인, 워드 3개 필드로 구성된다.
워드가 4개가 들어가므로 w=2, 캐시 라인의 수가 8개니까 s=3,
태그 필드는 나머지 비트인 2가 된다.
태그 : 캐시 라인을 공유하는 주기억 장치 블록들을 서로 구분하는데 사용됨
주기억장치 주소에서 상위 5비트(t+s)들은 주기억 장치의 블록 32개 중에서 하나를 지정하는 데 사용한다.
이 방식에서 주기억 장치의 블록 j가 적재될 수 있는 캐시 라인 번호 i는 모듈러 연산으로 결정된다. (i = j mod m)
ex) 캐시 라인 수가 8, 주기억 장치의 10번째 블록은 10일 때 i는 2다.
이때 캐시 라인에 해당하는 블록은 총 4개가 되고, 주기억 장치 블록 번호에 적힌 값은 주기억 장치 주소의 상위 5비트에 해당함
예를 통해서 보자.
주기억 장치의 제일 처음에 있는 00 000 xx를 보자.
라인이 000에 해당되므로 캐시의 000라인에 찾아간다. 이때 태그가 00이 아닌 01이기 때문에 00 000에 해당 되는 값을 입력한다.
그럼 00 000 00의 경우 q가 되고, 00 000 01의 경우에는 u, 이런 식으로 값이 들어가게 된다.
00 태그에 총 8개가 해당이 되고, 각 라인에는 총 4개의 태그가 해당된다.
직접 사상 방식을 사용한 캐시 동작
(1) 캐시로 주기억 장치 주소 11 101 01이 보내진다. 태그 필드는 11이고, 라인 필드는 101, 워드 필드는 01이다.
(2) 라인 필드 101이므로 5번 캐시 라인이 선택된다.
(3) 선택된 5번 라인의 태그 비트 11을 읽혀서
(4) 주기억 장치 주소의 태그 필드인 11과 비교한다.
(5) 두 태그 비트가 일치하므로 캐시가 히트된 것이다.
(6) 주소의 워드 필드가 01이므로 poet 중에서 o(1110 1111)가 인출되어 CPU로 전송된다.
(7) 태그 비트가 일치하지 않으면 캐시가 미스된 것이므로 주소 전체가 주기억 장치로 보내져서 해당 블록을 인출해 온다. 인출된 블록은 지정된 캐시 라인에 저장된다. 그런데 그 라인을 공유하는 다른 블록이 이미 저장되어 있는 상태라면 원래 블록은 지워지고 새로 인출된 블록이 저장된다.
장점 : 단순해서 구현 비용이 적다
단점 : 주기억 장치의 블록이 적재될 수 있는 캐시 라인이 하나뿐이기 때문에 블록 2개가 같은 라인에 사상되는 경우가 빈번하면 블록들이 반복적으로 미스되어 교체되므로 히트율이 떨어진다.
완전 - 연관 사상
; 직접 사상 방식의 단점을 보완한 방식으로 주기억 장치의 블록들이 캐시의 어떤 라인으로도 적재될 수 있는 방식
- 주기억 장치의 주소가 태그와 워드 필드 2개로 구성된다.
- 태그 필드 비트가 주기억 장치의 블록 번호와 같아진다.
완전-연관 사상 방식을 적용한 주기억 장치와 캐시의 구성
* 캐시 라인 번호와 태그 필드는 관련이 없음
각 캐시 라인의 태그에는 워드 필드를 제외한 상위 5비트가 저장되어 주기억 장치의 어느 블록이 저장되었는지를 나타냄
예를 통해서 보자
(1) 0000000을 찾는다고 해보자.
캐시에는 00000에 해당되는 태그가 없기 때문에 미스가 발생하고, 5(101)번째 라인에 00000을 추가한다. 그런 다음 00에 해당되는 값인 q를 가지고 온다.
(2) 또 다른 예인 0001010를 찾는 경우를 생각해보자.
이때 캐시에 00010이 존재하기 때문에 hit가 발생하고 10에 해당하는 r을 가지고 오게 된다.
완전 연관 사상에서 캐시 내부 구성 및 읽기 동작
(1) 캐시로 주기억 장치 주소 11001 11이 보내진다. 태그 필드는 11001이고, 워드 필드는 11이다.
(2) 캐시의 모든 라인의 태그들과 주기억 장치 주소의 태그 필드 내용을 비교한다.
(3) 2번 캐시 라인의 11001과 주소의 태그 필드 11001이 일치하므로 캐시가 히트된 것이다.
(4) 다음에는 주소의 워드 필드가 11이므로 navy 중에서 y(0111 1001)가 인출되어 CPU로 전송된다.
(5) 태그 비트가 일치하지 않으면 캐시가 미스된 것이므로 주소 전체가 주기억 장치로 보내져서 해당 블록을 인출, 인출된 블록은 5번 캐시 라인에 저장된다.
장점 : 데이터의 참조 지역성이 높다면 히트율이 매우 높아짐
단점 : 모든 태그를 순차적으로 비교하려면 많은 시간이 소요됨 + 복잡하고 비용이 높음
세트-연관 사상
; 직접 사상의 장점인 단순성과 완전-연관 사상의 장점인 높은 캐시 히트율에 의한 효율성을 모두 취하는 방식
전체 캐시 라인(m)을 v개의 세트로 나누고, 각 세트를 k개의 라인으로 구성
ex) 캐시 라인 수 m=8, 세트당 캐시 라인의 수가 k=2, 세트 수 v=4
세트당 캐시 라인의 수가 2면 2-way-세트-연관 사상 → 한 줄에 넣을 수 있는 양이 2개라는 것
세트당 캐시 라인의 수가 4면 4-way-세트-연관 사상 → 한 줄에 넣을 수 있는 양이 4개
세트가 4개고 세트당 캐시 라인이 2개니까 세트당 8개씩 할당된다.
예를 통해서 보자!
세트가 차 있을 경우 첫 번째 라인을 삭제한다고 가정하자.
(1) 000 00 00을 찾는 경우
0번째 세트가 가득 차 있는데 000에 해당되는 태그의 값은 없다.
값이 없기 때문에 미스가 발생한다.
001 태그에 해당되는 값을 지우고 000에 해당되는 값을 넣는다.
그렇게 하면 001 q u i z 100 b o w l 이런 식으로 들어가게 될 것이다.
그런 후 00에 해당되는 q 값을 가져온다.
(2) 000 10 11을 찾는 경우
2번째 세트에 000 태그의 값이 존재한다.
그러므로 hit가 발생하고 11의 값인 d를 가져오게 된다.
세트 연관 사상에서 캐시 내부 구성 및 읽기 동작
(1) 주기억 장치 주소 001 00 10이 캐시로 보내진다. (태그 필드=001, 세트 필드=00, 워드 필드=10)
(2) 00 세트 번호를 이용해 캐시의 0번 세트를 선택한다.
(3) 0번 세트 라인의 태그에 주기억 장치 주소의 태그 비트 001과 일치하는 것이 있는지 검사한다.
(4) 0번 세트 내 첫 번째 라인의 태그 비트가 001이므로 히트되었다.
(5) 다음에는 주소의 워드 필드가 10이므로 gift 중에서 f(1110 0110)가 인출되어 CPU로 전송된다.
(6) 태그 비트가 일치하지 않으면 캐시가 미스된 것이므로 주소 전체가 주기억 장치로 보내져서 해당블록을 인출, 적절한 교체 알고리즘에 의하여 2개 중 하나를 선택하여 그 라인에 새로운 블록을 적재해야 한다.
사상 방식의 비교
[3] 교체 알고리즘
; 캐시가 다 채워진 상태에서 새로운 블록을 채울 때는 저장된 블록 중 하나를 교체해야 함
- LRU : 가장 오래 사용되지 않은 캐시를 교체
- FIFO : 가장 오래 적재되어 있는 캐시를 교체
- LFU : 액세스 횟수가 가장 적은 블록을 교체
- Random : 임의로 선택하여 교체
[4] 쓰기 정책
; 캐시에 적재되어 있는 데이터가 수정되었을 때 그 내용을 주기억 장치에 갱신하는 시기와 방법을 결정하는 것
write-through
; 모든 쓰기 동작들이 캐시뿐만 아니라 주기억 장치로도 동시에 수행됨
주기억 장치의 내용들이 항상 유효함
단점은 쓰기 동작에 걸리는 시간이 길어지는 것
write-back
; 캐시에서 데이터가 변경되어도 주기억 장치에는 갱신하지 않음
데이터가 수정되면 블록의 UPDATE 비트가 세트되어 나중에 그 블록이 교체될 때 블록 전체가 주기억 장치에 갱신된 후 교체됨
쓰기 동작이 캐시에서만 이루어져 쓰기 시간이 짧아지고, 주기억 장칭 쓰는 동작 횟수가 최소화됨
미스가 발생하여 블록을 교체할 경우, 블록의 데이터가 수정된 상태면 주기억 장치 갱신을 위한 추가 시간이 소요됨
Uploaded by Notion2Tistory v1.1.0