Three Kinds of Cache Mapping

개요

캐시(Cache)는 크게 Direct-mapped 캐시, Set-associatice 캐시, Fully associative 캐시로 구분된다. 이는 각각 Figure 1(a), (b), (c)와 같은 형태이다. Direct-mapped 캐시는 E = 1인 캐시이며, 각 set에 대해 하나의 라인이 할당된다. Set-associatice 캐시는 E>1, S > 1인 캐시이며, 여러 set가 존재할 수 있고 하나의 set에 여러 라인이 할당될 수 있다. Fully associative 캐시는 S = 1인 캐시이며, 하나의 set에 모든 라인이 할당된다.

Analyzing cache hit and cache miss

캐시 히트(hit)와 미스(miss)를 분석하기 위해, Direct-mapped 캐시와 접근할 주소가 주어졌다고 가정하자:
먼저 캐시 내에 해당 주소가 가리키는 데이터가 있는지 확인하기 위해서는 set index bit를 사용해야 한다. Figure 2는 set index = 0b00001이므로, set 1에 접근하여 캐시 블록을 탐색하는 것을 보여준다. 이때 주의해야 할 것은 다수의 메모리 블록이 여러 set 내에 존재할 수 있다는 것이다. 하지만 해당 케이스는 E = 1이고, 하나의 캐시 라인(캐시 블록)에는 하나의 메모리 블록을 저장하므로 해당 예시에는 하나의 set에는 하나의 메모리 블록이 저장된다.

Set index를 통해 탐색해야 할 set가 선택된 이후에는 valid bit = 1인지와, tag bits가 주어진 주소의 tag bits와 일치하는지 체크한다. 만약 두 조건이 모두 만족된다면, 캐시 히트에 해당한다. 캐시 히트라면, 마지막으로 block offset을 사용하여 접근하고자 하는 데이터의 위치를 특정한다. 이는 figure 3에 잘 나타나 있다. 만약 두 조건 중 하나 이상이 맞지 않는다면 이는 캐시 미스에 해당한다. 이 경우 해당 set와 캐시 블록에 주어진 주소가 가리키는 메모리 블록으로 덮어 쓴다. 또한 valid bit = 1로 설정하고, tag bits는 주어진 주소의 tag bits로 설정한다. 이러한 메커니즘은 figure 4에 잘 나타나 있다.

이때 중요한 것은 캐시 히트와 캐시 미스 사이에는 굉장히 큰 퍼포먼스 차이가 존재한다는 것이다. 캐시 미스가 발생하여 메인 메모리에 접근하는 경우는 캐시 히트의 경우보다 약 100배는 느리며, 따라서 캐시 히트의 확률을 높이는 것이 굉장히 중요하다. 이때 어떤 메모리 접근에 대해 캐시 히트가 발생할 확률을 hit rate라고 하고, 캐시 미스가 발생할 확률을 miss rate라고 한다. 이때 hit rate와 miss rate는 다음과 같이 계산된다:

Hit Rate = # of cache hits / # of total accesses
Miss Rate = # of cache misses / # of total accesses
          = 1 - hit rate