Set Associative Cache (집합결합성 캐시)

직접매핑 캐시의 충돌 미스 문제는 각 집합이 정확히 하나의 라인만을 갖는다는 제한에서 오는 것이다(즉 E = 1). 집합 결여성 캐시는 이 제한을 완화해서 각 집합이 하나 이상의 캐시 라인을 갖는다. 1 < E < C / B인 캐시는 E-way 집합결합성 캐시라고 부른다. 

그림 1. 집합결여성 캐시의 예시

 집합결합성 캐시에서 집합의 선택

캐시 집합을 선택하는 과정은 직접매핑 캐시와 동일하며, 집합 인덱스 비트 s는 집합을 나타내게 된다.

그림 2. 집합결합성 캐시에서 집합의 선택

집합 결합성 캐시에서 라인 매칭과 워드 선택

라인 매칭은 직접매핑 캐시보다 집합 결합성 캐시에서 더 복잡한데, 그 이유는 요청한 워드가 집합에 있는지 결정하기 위해서 여러 개의 라인들의 태그와 유효비트를 조사해야 하기 때문이다. 보통의 메모리는 값들의 배열로, 주소를 입력으로 받아서 해당 주소에 저장된 값을 리턴해준다. 결합성 메모리는 반대로 (key, value) 쌍의 배열로, 키를 입력으로 받아서 (key, value) 쌍들 중에서 입력 키와 매칭되는 쌍에 있는 값을 리턴한다. 그래서 집합결합성 캐시의 각 집합을 "키가 태그와 유효비트가 결합된 형태이고, 블록의 내용을 값으로 가지는 하나의 작은 결합성 메모리"로 간주할 수 있다. (key = Valid bit + Tag bits, Value = block의 content)

그림 3. 집합결합성 캐시에서 라인 매칭과 워드 선택

위의 그림은 집합결합성 캐시에서 라인 매칭하는 기본 개념을 보여준다. 여기서 중요한 개념 한 가지는 집합의 모든 라인은 해당 집합에 매핑하는 어떤 메모리 블록도 다 포함할 수 있다는 것이다. 그래서 캐시 내의 태그와 주소의 내의 태그가 일치하는 유효한 라인을 찾기 위해 해당 집합의 각 라인을 탐색해야 한다. 만일 캐시가 이러한 라인을 찾아내면, 적중이 된 것이며 블록 오프셋은 이전처럼 블록 내 워드를 선택한다.

집합결합성 캐시에서 미스 발생 시 라인의 교체

만일 CPU가 요청한 워드가 해당 집합의 라인 어디에도 저장되어 있지 않다면, 미스가 발생한 것으로 캐시는 해당 워드를 포함하는 블록을 메모리에서 선입해야 한다. 그러나 일단 캐시가 그 블록을 가져오면, 어떤 라인을 교체해야할지를 결정해야 한다. 물론, 만일 비어있는 라인이 있다면 이 라인이 적절한 후보가 될 수 있겠으나 집합에 비어있는 라인이 없다면 비어 있지 않은 라인 중에서 하나를 선택해야 하며, CPU가 가까운 시간 내에 교체되어 사라져버린 라인을 참조하지 않기를 기대해야 한다.

프로그래머들이 자신의 코드에서 캐시 교체 정책에 대한 지식을 활용하는 것은 매우 어렵기 때문에, 해당 글에서는 자세한 내용을 다루지는 않을 것이다. 가장 간단한 교체 정책은 랜덤으로 교체할 라인을 선택하는 것이다. 좀더 복잡한 다른 방법들은 교체된 라인이 가까운 미래에 참조될 확률을 최소화하고자 시도하는 일환으로 지역성의 원리를 사용한다. 예를 들어 최소 빈도 사용 _{least-frequently-used LFU} 정책은 과거의 일정 시간 구간 동안에 가장 적은 횟수로 참조된 라인을 교체한다. 최소 최근 사용 least-recently-used LRU 정책은 과거 마지막 사용 시점이 가장 오래된 라인을 교체한다. 이 정책은 모두 추가적인 시간과 하드웨어 모두를 필요한다. 그러나 우리가 메모리 계층구조를 CPU와 멀어지는 방향으로 좀더 아래로 내려가면 미스의 비용이 더욱 비싸지고, 때문에 상위 계층의 저장 장치에서 좋은 교체 전략을 통해 미스를 최소화하는 것이 중요해진다.