이전 공부 요약
한 워드 블록의 직접 사상 캐시를 사용해 설명. 이 캐시에서는 모든 워드가 분리된 태그를 가지고 있고 각 워드는 단지 한 위치로만 사상되기에 적중과 실패가 매우 단순. 캐시와 메모리를 일치시키기 위해서 즉시 쓰기가 사용됨. 이 방식에서는 캐시에 쓰기가 발생할때마다 메인메모리에도 똑같이 씀. 이에 대한 대안으로는 나중 쓰기
- 공간 지역성을 이용하기 위해서, 캐시가 한 워드보다 더 큰 크기의 블록을 써야. 더 큰 블록의 사용은 실패율을 감소. 캐시의 데이터 저장량에 비해 상대적으로 태그 저장량을 감소시킴으로써 캐시의 효율을 향상.
- 더 큰 블록의 크기가 실패율을 감소 but 심패 손실을 증가. 실패 손실이 블록의 크기에따라 선형적으로 증가한다면 큰 블록은 성능 감소로 이어짐
- 성능 저하를 피하기 위해 메인 메모리의 대역폭을 증가 - 캐시 블록을 더 효과적으로 전송. DRAM의 외부 대역폭 증가시키기 위해 일반적 방법은 메모리 폭을 넓히는 것처럼 인터리빙(interleaving)시키는 것. DRAM 개발자는 더 큰 캐시 블록 크기의 비용 감소를 위해 프로세서와 메모리 사이 인터페이스를 꾸준히 향상 버스트 전송 모드의 대역폭을 증가시켜옴.
캐시 성능 측정 및 향상
CPU 시간은 CPU가 프로그램을 수행하는데 쓰이는 클럭 사이클과 메모리 시스템을 기다리는데 사용하는 클럭 사이클로 나뉜다. 일반적으로 적중된 캐시 접근 시간은 정상적인 CPU 수행 사이클의 일부로 간주한다.
CPU시간 = (CPU 클럭 사이클 + 메모리지연사이클) * 클럭 사이클 시간
메모리 지연 클럭 사이클은 주로 캐시 실패로 생긴다. 메모리 지연 클럭 사이클은 읽기와 쓰기 시에 발생되는 지연 사이클의 합으로 정의할 수 있다.
메로리 지연 클럭 사이클 = 읽기 지연 사이클 + 쓰기 지연 사이클
읽기 지연 사이클은 프로그램당 읽기 접근 수, 읽기 시의 실패 손실 클럭 사이클의 수, 읽기 실패율에 의해 정의 된다.
읽기 지연 사이클 = 읽기 접근횟수 / 프로그램 x 읽기 실패율 x 읽기 실패 손실
쓰기의 경우 더 복잡하다. 즉시 쓰기 방식에서는 지연이 두가지 요소로 구성. 쓰기를 수행하기 전에 블록을 인출해야 하는 쓰기 실패와 쓰기를 수행할 때 쓰기 버퍼가 다 채워져서 발생하는 쓰기 버퍼 지연으로 구성. 그래서 쓰기 시에 지연되는 사이클은 이 두가지의 합과 같다.
쓰기 지연 사이클 = (쓰기 접근 횟수 / 프로그램 x 쓰기 실패율 x 쓰기 실패손실) + 쓰기 버퍼 지연
대부분의 즉시 쓰기 캐시 구현 방식에서 읽기 실패 손실과 쓰기 실패 손실은 같다(메모리에서 블록을 가져오는데 걸리는 시간). 쓰기 버퍼 지연이 무시할 수 있을 정도로 작다고 가정하면, 하나의 실패율과 실패 손실을 써서 읽기와 쓰기를 합칠 수 있다.
메모리 지연 클럭 사이클 = 메모리 접근 횟수 / 프로그램 x 실패율 x 실패 손실
또한 다음과 같이 쓸 수도 있다
메모리 지연 클럭 사이클 = 명령어/프로그램 x 실패/명령어 x 실패 손실
프로세서의 성능에 캐시의 성능이 어떤 영향을 주는지 예를 살펴보자.
캐시 성능의 계산
<예제> : 프로그램 명령어 캐시 실패율이 2%이고, 데이터 캐시 실패율이 4%라고 가정. 메모리 지연이 없을 때 CPI가 2이고 매 실패마다 실패 손실이 100 사이클이라면, 결코 실패가 발생되지 않는 완벽한 캐시에서는 시스템이 얼마나 빨라지는지 계산하라. 읽기와 쓰기 빈도는 36%로 가정.
명령어개수(I)를 사용하여 명령어에 대한 메모리 실패 사이클 수를 계산하면
명령어 실패 사이클 = I * 2% * 100 = 2.00 * I모든 읽기와 쓰기의 빈도는 36%이다. 따라서 데이터 참조에 대한 메모리 실패 사이클 수는 다음과 같다.
데이터 실패 사이클 = I * 36% * 4% *100 = 1.44 * I즉 전체 메모리 지연 사이클 수는 2.00 I + 1.44 I = 3.44 I 이다. 이것은 평균적으로 명령어당 3 사이클 이상의 메모리 지연을 요구한다는 것을 뜻함. 따라서 메모리 지연을 고려할 경우 CPI는 2+3.44=5.44가 된다. 명령어 개수와 클럭 속도에는 변화가 없기 때문에 프로세서 수행 시간의 비율은 다음과 같다.
지연이 있는 경우의 CPU 시간/ 완벽한 캐시의 CPU 시간 = I*CPI(stall)*클럭 사이클 / I*CPI(perfect)*클럭사이클 = CPI(stall) / CPI(perfect) =5.44 / 2즉 완벽한 캐시가 있으면 성능은 5.44/2 = 2.72배 더 좋아진다.
만약 프로세서가 더 빠르게 동작하고 메모리 시스템은 전과 같다면 어떤 일이 발생할까? 이 경우에 메모리 지연에 쓰이는 전체 수행 시간 중 더 큰 부분을 차지하게 된다. 1장에서 살펴본 Amdahl의 법칙이 이를 상기시켜준다. 앞의 예제에서 클럭 속도는 변화 x CPI를 2에서 1로 줄여 시스템의 성능을 증가시켰다고 가정. 이는 파이프라인의 개선을 통해 가능. 캐시 실패가 있는 시스템의 CPI는 1+3.44 = 4.44. 완벽한 캐시를 갖는 시스템이 4.44배 빠르게된다.
메모리 지연에 쓰이는 수행 시간의 양은
3.44 / 5.44 = 63% 에서 3.44 / 4.44 = 77% 로 증가한다. 마찬가지로 메모리 시스템의 변화 없이 클럭 속도를 증가시키는 것도 또한 캐시 실패로 인한 손실을 증가시키게 된다.
앞의 예제와 식들은 적중 시간이 캐시의 성능을 결정하는 요인이 아니라고 가정. 하지만 적중시간이 증가한다면 메모리 시스템으로부터 워드를 가져오는 전체 시간이 증가 따라서 프로세서 사이클 또한 증가. 적중 시간을 증가시키는 것 중 하나의 예가 캐시의 크기를 증가. 적중과 실패 시의 데이터 접근 시간이 모두 성능에 영향. 이를 확인하기 위해 설계자는 서로 다른 캐시 구조를 평가하는 방법으로 평균 메모리 접근 시간(AMAT: average memory access time)을 사용한다. 이는 아래의 수식으로 표현된다.
평균 메모리 접근 시간 = 캐시 적중 시간 + 실패율 * 실패손실 평균 메모리 접근 시간의 계산
예제: 클럭 사이클이 1ns 이고 , 실패 손실은 20클럭, 명령어당 0.05의 실패율을 가지며, 캐시 적중을 포함한 캐시 접근 시간이 1클럭이라고 할 때 평균 메모리 접근 시간을 구하라. 읽기와 쓰기의 실패 손실은 같고 다른 쓰기지연은 무시.
명령어당 평균 메모리 접근 시간은
평균 메모리 접근 시간 = 캐시 적중 시간 + 실패율 * 실패 손실 = 1 + 0.05 * 20 = 2 클럭 사이클또는 2ns이다.
더 유연한 블록 배치를 통한 캐시실패 줄이기
지금까지는 메모리 블록을 캐시에 넣을 때 각 블록이 캐시의 딱 한 곳만 들어갈 수 있는 단순한 배치 방법을 사용. 이 방법은 메모리 블록 주소를 상위 계층의 한 곳에 바로 사상시키므로 직접 사상(direct mapped)이라 부른다. 하지만 실제로는 블록을 배치하는 다양한 방식이 존재, 그 중 극단적 방법이 블록을 한 곳에만 넣을 수 있는 직접 사상 방식.
다른 극단에는 블록이 캐시 내에 어디든 위치할 수 있는 방식이 존재. 이를 완전 연관(fully asscociate)라함. 완전 연관 캐시에서 주어진 블록을 찾으려면 모든 엔트리를 검색해야 함. 효율적으로 검색하기 위해 병렬적으로 비교기를 써서 검색. 이러한 비교기는 하드웨어 비용을 크게 증가시킴 그래서 완전 연관 방식은 블록이 작은 캐시에서만 유용.
직접 사상과 완전 연관 사상의 중간 == 집합연관(set associate)방식. 집합 연관 사상 캐시에는 한 블록이 들어갈 수 있는 자리의 수가 고정. 각 블록당 n개의 배치 가능한 위치를 갖는 집합 연관 캐시를 n-way 집합 연관 캐시라 부름. n-way 집합 연관 캐시는 각각 n 개의 블록으로 이뤄진 다수의 집합으로 구성. 메모리의 각 블록은 인덱스 필드에 의해 캐시 내의 한 집합으로 사상. 선택된 집합 내에서는 어디든 들어갈 수 있다. 하나의 블록은 한 집합에 직접 사상, 일치하는 것을 찾기 위해 집합 내의 모든 블록들을 검색해야 한다.
위 그림은 세 가지 블록 배치 방법에 대해 전체 8개의 블록으로 구성된 캐시에 블록 12가 어디에 위치하게 되는지 보여준다. 직접 사상 캐시 내의 메모리 블록의 위치는 다음과 같이 구할 수 있다.
(블록 번호) modulo (캐시 내 블록의 수)
집합 연관 캐시에서 어떤 메모리 블록을 갖고 있는 집합은 다음과 같이 구현할 수 있다.
(블록 번호) modulo (캐시 내 집합 수) 블록이 집합 내 어디나 배치 될 수 있기에 집합 내 모든 태그를 다 검색해야 함. 완전 연관 캐시에서는 블록이 어느 곳에나 위치할 수 있으므로 캐시 내 모든 블록을 다 검색해야 함.
모든 블록 배치 방식을 집합 연관 방식의 변형으로 생각하는 것도 가능.
위그림은 8개 블록을 갖는 캐시에서 가능한 연관정도(associativity)에 따라 다양한 구조를 보여줌. 직접 사상 캐시는 1-way 집합 연관 캐시. 각 캐시 엔트리는 한 블록을 원소로 갖는 집합으로 구성됨. m개의 엔트리로 구성된 완전 연관 캐시는 간단히 m-way 집합 연관 캐시라고 볼 수 있다. m 개의 블록으로 구성된 한 개의 집합만을 갖고 엔트리는 그 집합 내 어느 블록에도 위치 가능.
연관 정도를 늘리면 실패율이 줄어드는 장점이 있지만 단점으로 적중 시간이 증가한다.
실패와 캐시의 연관정도
1 워드 크기를 갖는 블록 4개로 구성된 작은 세 종류의 캐시가 있다. 하나는 완전 연관, 다른 하나는 2-way 집합 연관 방식, 나머지는 직접 사상 방식. 각 캐시 구현에 대해 블록주소 0,8,0,6,8 순으로 블록을 참조할 때 발생하는 실패는 각각 몇 번?
직접 사상 캐시의 경우가 가장 쉽다. 먼저 각각의 블록 주소가 어느 캐시블록으로 사상되는지 결정하자.
| Block address | Cache block |
|---|---|
| 0 | (0 modulo 4) =0 |
| 6 | (6 modulo 4) =2 |
| 8 | (8 modulo 4) =0 |
이제 참조 후 캐시의 내용을 채울 수 있다. 빈칸은 블록이 유효하지않음을 파란색은 캐시에 추가된 새로운 엔트리. 검은색은 전부터 캐시에 있던 엔트리.
| Address of memory block accessed | Hit or Miss | 0 | 1 | 2 | 3 |
|---|---|---|---|---|---|
| 0 | miss | Memory[0]* | |||
| 8 | miss | Memory[8]* | |||
| 0 | miss | Memory[0]* | |||
| 6 | miss | Memory[0] | Memory[6]* | ||
| 8 | miss | Memory[8]* | Memory[6]* |
직접 사상 캐시에서는 5번 접근 시도에 5번 실패가 발생.
집합 연관 캐시는 집합당 2개의 원소를 갖는 2개의 집합(0과 1로 인덱스)으로 구성. 각 블록 주소가 어느 집합으로 사상되는지 알아보자.
| Block address | Cache Set |
|---|---|
| 0 | (0 modulo 2) =0 |
| 6 | (6 modulo 2) =0 |
| 8 | (8 modulo 2) =0 |
실패 시 집합 내에서 교체할 엔트리의 선정을 위해서는 교체 방식을 선정해야 LRU 방식을 사용. 가장 오래전에 사용한 블록이 교체된다.
| Address of memory block accessed | Hit or Miss | set0 | set0 | set1 | set1 |
|---|---|---|---|---|---|
| 0 | miss | Memory[0]* | |||
| 8 | miss | Memory[0] | Memory[8]* | ||
| 0 | hit | Memory[0] | Memory[8] | ||
| 6 | miss | Memory[0] | Memory[6]* | ||
| 8 | miss | Memory[8]* | Memory[6] |
블록 6이 참조될 때 블록 8이 교체된다. 블록 8이 블록 0보다 더 오랫동안 참조되지 않았기에. 2way 집합 연관 캐시는 전부 4번의 실패.
완전 연곤 캐시는 4개의 캐시 블록으로 구성된 1개의 집합을 갖는다. 어떠한 메모리 블록도 캐시 내 어느 블록에나 적재될 수 있다. 이 완전 연관 방식 캐시가 단지 3개의 실패만 발생시키며 최고의 성능.
| Address of memory block accessed | Hit or Miss | Block0 | Block0 | Block1 | Block1 |
|---|---|---|---|---|---|
| 0 | miss | Memory[0]* | |||
| 8 | miss | Memory[0] | Memory[8]* | ||
| 0 | hit | Memory[0] | Memory[8] | ||
| 6 | miss | Memory[0] | Memory[8] | Memory[6]* | |
| 8 | miss | Memory[0] | Memory[8] | Memory[6] |
이런 순서를 갖는 참조에서는 세 가지 블록 주소를 사용하기 때문에 3개의 실패가 우리가 가질 수 있는 최상의 것. 만약 8개의 블록이 있다면, 2-way 집합 연관 캐시의 경우 교체는 발생하지 않는다. 따라서 완전 연관 캐시와 실패횟수가 동일하게 된다. 마찬가지로 16개의 블록이 있다면 이 3개의 캐시는 모두 같은 개수의 실패를 갖는다.
실패율이 연관 정도에 의해서 얼마나 줄어드는가? 그럼 5.16은 16워드의 블록으로 구성된 64KiB 데이터 캐시가 얼마나 개선되는지 보여준다.
| Associativity | Data miss rate |
|---|---|
| 1 | 10.3% |
| 2 | 8.6% |
| 4 | 8.3% |
| 8 | 8.1% |
캐시에서 블록 찾기
집합연관 방식인 캐시에서 블록을 찾는 방법을 살펴보자. 직접 사상 캐시에와 같이 집합 연관 캐시 내의 블록은 블록 주소를 나타내는 주소 태그를 가지고 있다. 선택된 집합 내 모든 블록의 태그는 프로세서로부터 나온 태그와 일치하는지를 검사하게 된다.
Tag Index Block offset 집합 연관이나 직접 사상 캐시에서의 주소 세부분. 인덱스는 집합을 고르는데 사용되고 태그는 고른 집합 내부에서 비교에 의해 블록을 선택할 때 사용된다. 블록 변위는 원한느 데이터 블록 내 주소이다.
위는 주소가 어떻게 나뉘는지 보여준다. 인덱스 값을 이용하여 필요한 주소를 가지고 있는 집합을 선정하고, 선정된 집합 내 모든 블록의 태그를 비교한다. 빠른 속도가 매우 중요하기에 집합 내 모든 태그는 병렬로 검색된다. 병렬이 아닌 순차적인 탐색은 완전 연관 캐시에서와 같이 집합연관캐시의 적중시간을 너무 느리게 만든다.
전체크기가 같다면, 연관 정도를 늘리는 것은 집합당 블록의 수를 증가시킨다. 집합당 블록의 수는 병렬로 검색되어 동시에 비교되어야 하는 횟수와 같다. 연관 정도를 2배 늘리는 것은 인덱스의 크기를 1비트 줄게, 태그의 크기는 1비트 늘게 한다. 완전 캐시의 경우, 실제로 한 개의 집합만이 존재하고 모든 블록들은 병렬로 검사되어야 한다. 다라서 인덱스가 필요 없고 블록 변위를 제외한 전체 주소는 모든 블록 태그와 비교된다. 다시 말해서 인덱스를 사용하지 않고 전체 캐시를 검사해야 한다.
직접사상 캐시는 엔트리가 한 블록에만 존재할 수 있으므로, 단지 하나의 비교기만 필요하고 인ㄷ넥스만으로 캐시에 접그날 수 있다. 아래 그림의 4-way 집합 연관 캐시에서는 선정된 집합 4개의 원소 중 하나를 선택하는데 4:1 멀티플렉서와 4개의 비교기가 필요하다. 캐시 접근은 집합을 찾는 것과 집합내 채그를 비교하는 것으로 구성. 집합 연관 캐시를 사용하려면 많은 비교기가 필요하고 집합의 원소들을 비교하고 선택하는 데 걸리는 시간 지연을 감수해야 한다.
4-way 집합 연관 캐시의 구현에는 4개의 비교기와 4:1 멀티플렉서가 필요하다
비교기는 선정된 집합의 어느 원소가 태그와 일치하는지를 결정한다. 비교기의 출력은 멀티플렉서에 인가되어 인덱스된 집합 내 4개의 데이터 중 하나를 선정하는데 사용된다. 어떤 구현에서는 캐시의 출력을 RAM 외부로 내부내는 출력 구동 신호를 이용하여 집합에서 원하는 엔트리를 선택한다. 출력구동 신호는 비교기로부터 나오고 일치하는 엔트리가 캐시의 출력이 되도록 해준다. 이 방식을 사용하면 멀티플렉서가 필요없다.
교체시킬 블록 선택
직접 사상캐시에서 실패가 발생되면 요구된 블록은 딱 한 곳으로만 갈 수 있으므로 그 자리를 차지하던 블록은 교체되어야 한다. 연관 방식의 캐시에서는 요구된 블록을 어디에 위치시킬지 선택을 하여야 하며, 이는 교체시켜야할 블록을 선택하는 것과 동일하다. 완전 연관 캐시는 모든 블록이 교체 후보가 되며 집합 연관 캐시의 경우에는 선정된 집합 내 블록 중 하나를 골라야 한다.
가장 일반적으로 사용된느 방식은 LRU(least recently used) 방식. 교체되는 블록은 가장 오랫동안 사용되지 않은 것. LRU 방식은 집합의 어떤 원소가 집합 내의 다른 원소에 비해 상대적으로 언제 사용되었는지를 추적함으로써 구현 가능하다. 2-WAY 집합 연관 방식의 캐시에서는 두 원소가 언제 사용되었느지 추적하는 것은 각 집합마다 한 비트를 두고 원소가 참조될 때마다 원소를 표시하는 값으로 비트를 결정함으로써 구현될 수 있다. 연관 정도가 커지면 LRU를 구현하는 것이 더욱 힘들어짐.
태그 크기 대 집합의 연관 정도
연관 정도를 늘리는 것은 캐시 블록당 더 많은 태그 비트를 요구할 뿐만 아니라 더 많은 비교기를 필요한다. 4096개의 블록을 갖고 하나의 블록은 4개의 워드를 가지며 32비트 주소를 갖는 캐시에 대해 직접사상, 2-way 집합연관, 4-way 집합 연관과 완전연관 방식을 적용했을 때 각각에 대해 전체 집합의 수와 전체 태그비트의 수를 구해랑
풀이 : 블록당 16바이트가 존재하므로 32비트 주소 중 인덱스와 태그용으로 32-4 = 28 비트를 필요로 한다. 직접 사상 캐시에서는 블록의 개수와 집합의 개수가 같으므로 인덱스로 12비트[log2 (4096)]=12를 갖는다. 따라서 태그 비트의 총 수는
28 - 12 * 4096 = 16 * 4096 = 66K태그 비트연관의 정도를 높일 때마다 집합의 수는 절반식 줄어들고 따라서 캐시를 인덱스 하는 데 필요한 비트의 수도 하나씩 감속하게 된다. 또한 태그에 필요한 비트는 하나씩 증가하게 된다. 따라서 2-way 집합 연관 캐시는 2048 개의 집합을 갖게 되고 전체 태그 비트 수는
(28-11)*2*2048 = 70K 태그 비트가 된다. 4-way 집합 연관 캐시는 전체 집합의 수가 1024이고 전체 태그 비트 수는
(28-10) * 4 * 1024 = 72 * 1024 = 74K 비트가 된다.완전 연관 캐시의 경우 4096 블록 크기의 집합 하나만 존재하므로 태그는 28비트이며
28 * 4096 *1 = 115K 태그 비트가 된다.다단계 캐시를 이용한 실패 손실 줄이기
현대 컴퓨터는 캐시를 사용. 프로세서의 빠른 클릭 속도와 상재적으로 느려지는 DRAM 접근 시간 사이의 차이를 줄이기 위해, 고성능 마이크로프로세서들은 캐시를 한 계층 더 사용한다. 이 2차 캐시(secondary cache)는 주로 마이크로 프로세서에 내장되어 있으며, 1차 캐시(primary cache)에서 실패가 발생할 때 접근 된다. 2차 캐시가 원하는 데이터를 가지고 있으면 실패 손실은 2차 캐시의 접근 시간이 되며 이 값은 메인 메모리의 접근시간보다 훨씬 작다. 1차 캐시와 2차 캐시 둘 다 데이터를 갖고 있지 않은 경우에는 메인 메모리 접근이 필요하게 되고 더 큰 실패 손실이 발생하게 된다.
