유연한 블록배치를 통한 캐쉬실패 줄이기 - Decrease the Cache missrate by arranging block location

블록배치방식 - 캐쉬에 블록을 위치시키는 방법은 다음의 세가지 방식이 존재한다.
  1. Directed Mapped : 블록이 단지 한곳에만 위치할 수 있는 방법
  2. Fully Associative : 블록이 캐쉬내의 어느 곳에나 위치할 수 있는 방식.
  3. Set associative : n-way 집합연관 캐쉬는 각각 n개의 블록으로 이루어진 다수의 집합들로 구성되어 있다. 빠른 검색을 위해 n개의 블록을 병렬로 수행한다.

집합 연관방식 장,단점
  - 장점
  연관 정도를 늘리는 것의 장점은 대개 실패율이 줄어든다는 것이다.
(부가설명=>n-way 집합 연관방식에서는 n개의 블록을 병렬로 검색한다. 따라서 더 많은 수의 블록을 검색하기 위한 논리 게이트가 증가한다, 반면에 캐쉬 내 집합의 개수는 감소하여 찾을 범위가 더 적어진다.)
  - 단점
  가장 큰 단점은 적중 시간의 증가이다.(비용적 문제도 증가)

집합 연관 방식에서 블록 교체 방식
  집합연관 캐쉬는, 대개 집합내에서 가장 오래전에 사용된 블록을 교체시키는 LRU(least recently used)교체 방식을 사용한다.


문제
  4개의 1워드 블록으로 구성된 캐쉬가 있다(캐쉬 크기가 4워드). 직접사상, 2-way 집합연관, 4-way 집합연관, fully 집합연관방식이다. 각 캐쉬 구현에 대해서 다음 순서에 따른 블록 주소의 참조시 발생하는 실패의 수는 각각 얼마인가? 블록주소 : 0, 8, 0, 6, 8

직접사상캐쉬 : 5번
2-way 집합연관 캐쉬 : 4번
4-way 집합연관 캐쉬(완전 집합연관방식) : 3번

4-way 집합연관 캐쉬

  위 그림은 4-way 집합연관 캐쉬이다. 하나의 블럭은 1워드이다. 집합의 개수는 256개(0~255)이다. 따라서 캐쉬의 사이즈는 4byte * 집합의 개수 * n-way(블럭개수) 로 계산이 가능하므로, 4byte * 256 * 4 = 4096 byte, 즉 4K이다.
  그림에서 보는거와 같이 색인값은 필요한 주소를 가지고 집합을 선정하는데 이용되고, 선정된 집합 내부의 모든 블록의 태그는 비교되어야 한다. 선정된 모든 태그는 빠른 속도를 위하여 병렬로 검색한다.
  완전연관 캐쉬의 경우, 실제 한 개의 집합만이 존재하며 모든 블록들은 병렬로 검사되어야 한다. 따라서 색인이 필요 없고, 블록 변위를 제외한 전체주소는 모든 블록의 태그와 비교된다. 즉 색인을 사용하지 않고 전체 캐쉬를 검색해야 한다.

문제
연관정도를 늘리는 것은 캐쉬 블록 당 더 많은 태그 비트를 요구할 뿐만 아니라, 더 많은 비교기를 필요로 한다. 4K개의 블록을 갖고 하나의 블록은 4개의 워드를 가지며 32 비트 주소를 갖는 캐쉬에 대해 직접 사상, 2-way 집합연관, 4-way 집합연관과 완전연관 방식을 적용하였을때 각각에 대해 전체 집합의 수와 전체 태그 비트 수는 ?
  정답 : 직접사상, 2-way, 4-way, 완전연관 => 64Kbits, 68 Kbits, 72 Kbits, 112Kbits

출처 : 컴퓨터 구조 및 설계 - 하드웨어/소프트웨어 인터페이스 -