[컴퓨터 구조] 메모리[4] - Associative Cache

 

 

 

 

 

🧐 Associative Cache

Associatvie Cache는 유연한 블록 배치(placement)를 통해 캐시 실패율(Miss rate)을 줄이는 방법입니다.

이전 글 까지에서는 메모리 블록을 캐시에 넣을 때 각 블록이 캐시의 딱 한 장소에만 들어갈 수 있도록 하는 단순한 배치 방법인 directed mapped를 사용하였습니다.

 

directed mapped는 블록을 배치하는 다양한 방식들 중, 극단적으로 블록을 한 곳에만 넣을 수 있도록 하는 방법입니다.

 

반대쪽 극단에는 블록이 캐시의 어느 곳에나 들어갈 수 있도록 하는 방식이 있습니다.

 

 

👉 fully associative

블록이 캐시의 어느 곳에나 들어갈 수 있도록 하는 캐시 구조를 의미합니다.

메모리 블록을 캐시 내의 어떤 엔트리와도 연관(매핑, 사상)시킬 수 있기 때문에, 이를 fully associative 방식이라 합니다.

 

fully associative 캐시에서는 블록이 어느 곳에나 있을 수 있기 때문에 원하는 블록을 찾기 위해서는 캐시 내의 모든 엔트리를 검색해야 합니다.

 

검색이 실용성이 있으려면, 각 캐시 엔트리와 연결된 비교기(Comparator)를 이용하여서 병렬로 검색해야 합니다.

그러나 해당 비교기로 인해 하드웨어의 비용이 크게 증가될 수 있기 때문에 fully associative 방식은 블록이 몇개 되지 않은 작은 캐시에서만 쓸 수 있습니다.

 

 

 

 

👉 set associative 

두 양 극단의 사상 방법(directed mapped와 fully associative)의 중간에는 set associative 방식이 있습니다.

set associative 캐시에서는 한 블록이 들어갈 수 있는 자리의 개수가 고정되어 있습니다.

각 블록당 n개의 배치 가능한 위치를 갖는 set associative 캐시를 n-way set associative 캐시라고 부릅니다.

 

n-way 집합 연관 캐시는 다수의 집합들로 구성되어 있는데 각 집합에는 n개의 블록이 있습니다.

(집합의 개수가 아닌 한 집합 내의 블록의 개수가 n개입니다.)

메모리의 각 블록은 cache 인덱스 필드에 의해서 캐시 내의 한 집합으로 사상되고, 해당 집합 내에서는 아무 장소에나 들어갈 수 있습니다.

 

 

 

검색 시에는 블록이 존재하는 집합으로 사상한 후, 집합 내의 모든 블록을 검색하여 일치하는 것을 찾습니다.

 

예를 들어 아래 그림에서는 총 8개의 블록으로 구성된 캐시에서의 3가지 블록 배치 방법을 적용했을 때, 블록 주소가 12인 블록이 어디에 사상되는지를 보여줍니다.

directed mapped 캐시에서는 12 mod 8 = 4이므로, index가 4인 블록에만 사상될 수 있습니다.

 

위의 set associative 캐시는 2-way set associative 캐시이므로 집합의 수는 (전체 블록 수 / 집합당 블록 수)인 4개이며,

블록 주소가 12이므로 12 mod 4 = 0번 집합에 있어야 합니다.

0번 집합 내에서는 아무 위치에나 들어갈 수 있습니다.

 

fully associative 캐시에서는 아무 위치에나 들어갈 수 있습니다.

 

 

캐시 내의 블록의 인덱스(위치)는 다음과 같이 구할 수 있음을 상기하고 넘어가겠습니다.

directed mapped 캐시
캐시 인덱스 = (블록 주소) modulo (캐시 내의 블록 수)

set assosiavtive 캐시
캐시 인덱스(집합 번호) = (블록 주소) modulo (캐시 내의 집합 수)

 

 

set associative 캐시에서는 블록이 집합 내에서 어느 곳에나 존재할 수 있기 때문에, 집합 내의 모든 블록의 태그를 전부 검사해야 합니다.

fully associative 캐시에서는 블록이 어느 곳에나 위치할 수 있으므로, 캐시 내 모든 블록의 태그를 다 검색해야 합니다.

 

모든 블록 배치 방식을 set associative 방식의 변형이라고 생각할 수도 있습니다.

 

예를 들러 블록의 개수가 8개인 캐시에서 가능한 associativity(연관 정도) 구조는 다음과 같습니다.

 

associativity를 늘리는 것의 장점은 대게 실패율(miss rate)이 줄어든다는 것이고,

단점으로는 적중시간(hit time)이 증가한다는 것입니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Associativity와 Miss rate의 관계

1워드 크기의 블록 4개로 구성된 세가지 종류의 캐시에 대해 생각해 보도록 하겠습니다.

 

하나는 fully associative, 하나는 2-way set associative, 하나는 directed mapped 입니다.

 

블록 주소는 0, 8, 0, 6, 8 순으로 참조되며, 이러한 경우 각 캐시 구성에서 실패는 몇 번씩 발생하는지 확인해 보도록 하겠습니다.

 

 

 

👉 directed mapped의 경우

우선 각 블록의 주소가 가지는 캐시 인덱스를 구해보도록 하겠습니다.

Block Address	Cache Index
0	0 mod 4 = 0
6	6 mod 4 = 2
8	8 mod 4 = 0

 

다음과 같이 총 5번의 Miss가 발생합니다.

 

 

 

 

 

 

 

👉 2-way set associative의 경우

캐시의 블록 수가 4개이므로, 2-way의 경우에는 집합의 수가 4 / 2 = 2개(인덱스 0과 1)입니다.

각 집합에는 2개의 원소(block)가 존재할 수 있습니다.

 

각 블록의 주소가 가지는 캐시 인덱스를 구해보도록 하겠습니다.

Block Address	Cache Index
0	0 mod 2 = 0
6	6 mod 2 = 0
8	8 mod 2 = 0

 

 

다음과 같이 총 4번의 Miss가 발생합니다.

6이 들어오는 경우 교체가 발생하였습니다.

 

 

 

 

 

 

 

👉 fully associative의 경우

fully associative 캐시의 경우 4개의 캐시 블록으로 구성된 1개의 집합을 갖습니다.

 

다음과 같이 총 3번의 Miss가 발생합니다.

 

 

 

이를 통해 다음을 알 수 있습니다.

Associativity가 커진다면 Miss rate가 줄어드는 것을 알 수 있습니다.

 

 

 

 

 

 

 

 

 

 

🧐 캐시에서 블록 찾기

set associative 캐시에서 블록을 찾는 방법을 살펴보겠습니다.

 

directed mapped 캐시에서와 같이 set associative 캐시 내의 블록들은 블록 주소를 나타내는 주소 태그를 가지고 있습니다.

 

선택된 집합 내 모든 블록의 태그는 프로세서가 보낸 주소의 태그와 일치하는지 검사하게 됩니다.

 

메모리 주소는 다음과 같이 세 부분으로 나누어집니다.

인덱스 값을 이용하여 원하는 주소가 속한 집합을 선정합니다.

 

이후 선정된 집합 내의 모든 블록의 태그를 검색합니다.

 

속도가 매우 중요하기 때문에 선정된 집합 내의 모든 태그를 병렬로 검색합니다.

 

 

캐시의 전체 크기가 같다면, Associativity를 늘리는 것은 하나의 집합 내 블록의 수를 증가시킵니다.

집합 내 블록의 수는 병렬 검색을 위해 필요한 동시 비교 횟수와 같습니다.

 

Associativity를 2배 증가시키면, 집합당 블록의 수가 2배가 되고, 집합의 수는 $\frac{1}{2}$ 배가 됩니다.

따라서 Associativity를 2배 늘릴 따마다, 태그의 크기는 1비트 늘어나고, 인덱스의 크기는 1비트 줄어듭니다.

 

Fully Associative 캐시의 경우 집합이 단 1개밖에 없는 것과 마찬가지이므로,

따라서 인덱스는 없으며, Block offset을 제외한 주소 전체가 태그가 되어 모든 블록의 태그와 비교되어야 합니다.

 

 

 

직접 사상 캐시에서는 엔트리가 들어갈 수 있는 블록이 하나밖에 없기 때문에 인덱스만 사용하여 캐시에 접근하므로 비교기가 하나만 있으면 됩니다.

 

아래 그림과 같이 4-way set associative 캐시에서는 선정된 집합의 4개 원소 중 하나를 선택하는데 4:1 멀티플렉서와 4개의 비교기가 필요합니다.

색칠된 4개의 부분은 하나의 집합에 속합니다.

 

 

 

 

 

 

 

🧐 교체 정책

directed mapped 캐시에서 실패가 발생되면 요구된 블록은 딱 한 곳으로만 갈 수 있으므로 그 자리에 위치한 블록을 교체하면 됩니다.

 

하지만 set-associative 캐시에서는 요구된 블록을 집합 내 어느 위치에 넣어야 할 지 선택하여야 하며, 이는 교체할 블록을 선택하는것과 동일합니다.

 

fully associative 캐시에서는 모든 블록이 교체의 후보가 됩니다.

 

 

가장 널리 사용되는 방식은 LRU(least recently used) 방식입니다.

LRU 방식에서 교체되는 블록은 가장 오랫동안 사용되지 않은 것입니다.

 

LRU 방식을 사용하기 위해서는 가장 오랫동안 사용되지 않은 블록을 추적할 수 있어야 합니다.

 

2-way set associative 캐시에서는 각 집합마다 한 비트를 추가로 두고, 원소가 참조될 때마다 해당 값을 변화시킴으로써 상대적 사용 시기를 추적할 수 있습니다.

 

그러나 associativity가 더 커지면 LRU를 구현하기 힘들어집니다.

 

LRU 방식 이외에도 무작위로 블록을 골라 교체하는 Random 방식도 있습니다.

Random 방식은 구현하기 간단할 뿐더러 LRU와 비슷한 성능을 냅니다.