Cache miss 주요 원인들(3C's model)과 해결법

Cache miss의 원인은 크게 세 가지로 나눌 수 있다. 이유의 각 앞글자를 따서 3C's model이라고 한다. 각 모델을 설명하고 이를 해결하기 위한 방법을 간단히 논한다.

1. 3C's models

a. Compulsory miss

한국말로 직역하면 "강제 미스" 이다. 데이터에 처음 접근시 캐시에 데이터를 올리기 위해 발생하는 캐시 미스이다. 다른말로 cold start miss라 부르기도 한다.

b. Capacity miss

캐시의 용량이 부족하여 발생하는 미스이다. 즉, 프로그램 수행 시 접근하는 데이터의 양이 캐시의 사이즈를 넘어갈 경우 발생한다. 예를들어 32k direct mapped cache를 달고 있는 컴퓨터에서 128k array data를 접근하는 경우 캐시는 array data를 모두 저장할 수 없으므로 용량 부족에 의한 캐시 미스가 발생한다. 이러한 미스를 capacity miss라 한다.

c. Conflict miss

Cache에서 set¹의 way가 부족하여 발생하는 miss이다.

²

위 그림에서 다른 주소더라도 index 8bit(초록색)이 같게 되면 같은 세트에 위치한다. 이 때문에 우연히 이 세트에 여러번 접근되면 특정 set에 way가 부족하여 miss를 일으키는데 이를 conflict miss라 한다.

d. Coherence miss(if 4C's model)

멀티코어가 대두되면서 각 코어마다 캐시를 장착하게 되었다. 이러한 시스템에서는 코어 캐시 간 일관성이 중요하다. 이 때문에 한 코어에서 캐시라인이 업데이트 시, 일관성을 위해 다른 코어의 캐시라인이 invalidate 된다. Invalidate된 데이터를 재 접근시 발생하는 캐시 미스이다. 

False sharing(거짓공유)

서로 다른 두 변수가 locality에 의해 같은 캐시라인을 쓰는 경우 발생한다. 원리는 아래와 같다.

시스템은 8바이트 캐시라인을 사용한다고 가정한다.

상황

• 각 코어는 8바이트 캐시라인을 가지고 있다.
• int A,B 변수는 서로 근접하고 있다.
• 코어 0번 캐시에는 한 캐시라인에 A,B가 같이 올라가 있다.
• 코어 1번 캐시에는 한 캐시라인에 A,B가 같이 올라가 있다.
• 코어 0번 프로그램은 A에 쓰기를 매번 시도한다.
• 코어 1번 프로그램은 B에 읽기를 매번 시도한다.

위 상황의 경우, 코어 0번은 A만 접근하고 코어 1번은 B만 접근하므로 두 코어는 변수를 공유하지 않는다. 하지만 A,B 변수가 캐시라인을 공유한다.

코어 0번 캐시의 A 데이터를 write하면 A 데이터의 캐시 일관성을 위해 A 데이터를 가진 코어 1번 캐시라인의 캐시라인이 invalidate된다. 코어 1번 프로그램은 B만 읽지만 코어 0번 때문에 캐시라인이 invalidate 되어 B 데이터에 접근할 때, cache miss가 발생하는 일을 겪는다.

이와같이 실제로 변수를 공유하지 않지만 캐시라인을 공유하는 상황때문에 cache miss가 발생하는것을 false sharing이라 한다.

2. Solutions for 3C's cache misses

아래 방법들은 cache의 전체적인 performance와는 관계 없다. 단순히 miss의 횟수를 줄이는 방향이다. 예를 들어, high associativity cache는 실제 tag matching 시간이 오래 걸리므로 miss가 감소하는 대신 hit time이 증가하게 된다.

a. Large cache size

캐시 사이즈를 늘리면 capacity miss를 줄일 수 있다.

b. High associativity cache

Way가 높아질수록 conflict miss를 줄일 수 있다.

c. Victim cache

Conflict miss를 줄일 수 있다. 구조는 다음과 같다.

³

위 구조의 경우 primary cache(Directed Mapped Cache) 밑에 victim cache가 존재한다. Victim cache는 fully associative cache 형태로 존재한다. Hit/miss에 따라 세가지 경우의수가 존재한다.⁴

• Primary cache hit: 정상동작
• Primary cache miss, Victim cache hit: Hit 된 victim cache의 cache line과 primary cache의 miss난 cache line을 swap
• Primary cache miss, Victim cache miss: Primary cache에 miss난 데이터를 올리고, 원래 있던 primary cache의 cache line은 victim cache로 대피. 만약 대피된 cache line을 저장하려고 할 때, victim cache의 capacity가 부족하면 오래된 victim cache line을 버림

이 경우 위 두개는 hit으로 간주하고 아래 한개는 miss로 간주한다. 이러한 접근은 conflict miss를 줄여준다. 이유는 기존 set의 부족한 way를 늘려주는 효과를 갖기 때문이다. 

d. Pseudo-associative cache

Conflict miss를 줄일 수 있다. 단, capacity miss는 증가할 수 있다. Pseudo-associative cache는 기본적으로 2-way associative cache와 비슷하다.

키 아이디어: 하나의 index를 두 번 비교한다.

• 기본구조
  • Cache 내부는 H1과 H2로 나누어져 있다. (논리적인 분할, 실제 분할이 아님)
• 동작원리
  • 임의의 index에 대하여 H1를 체크한 뒤, miss가 나면 H2를 체크한다.
  • H1을 체크할 땐 regular index를 이용하여 체크하고 H2를 체크할 때는 hashing한 index를 가지고 체크한다.
  • H2에 속해있는 set를 표시하기 위해 hashing bit가 필요하다.
• Hit or Miss 처리
  • H1 miss/ H2 hit시, 서로의 cache line을 swap
  • H1 miss/ H2 miss시, memory data를 가져와서 H1의 cache line으로 올린다.

이렇듯, 하나의 index를 두 번 비교하며 H1과 H2를 sequential하게 체크하므로 hit time이 약간 늘어난다. 하지만 conflict cache miss가 줄어든다.

e. Two skewed-associative cache

키 아이디어: 2-way associative cache에서 하나의 way(way1)는 regular index로 비교하고 다른 하나의 way(way0)는 index와 tag를 이용한 hash값을 비교한다.

일반적인 2-way associative cache는 다른 주소가 같은 index를 가지게 되면 conflict miss가 일어나게 된다. 이를 방지하기 위해 한 way(way0)에서는 같은 index더라도 tag가 다르면 결과적으로 다른 제2의 index를 활용하도록 hash function⁵을 이용한다. 구조는 아래와 같다.

6

이 경우, conflict miss는 줄어들게 되나 같은 index를 분산하여 저장하므로 way 0의 capacity miss는 늘어나게 된다.

---

1. Set은 하나의 index에 대응하며 n way의 cache line으로 이루어져 있다. ↩

2. https://cs.nyu.edu/~gottlieb/courses/2000s/2001-02-fall/arch/lectures/lecture-22.html ↩

3. http://wiki.expertiza.ncsu.edu/index.php/CSC_456_Fall_2013/1b_ra ↩

4. http://timewizhan.tistory.com/entry/Victim-Cache ↩

5. hash function은 수학적 논리에 의해 분포도를 조절할 수 있다. ↩

6. http://www.ece.cmu.edu/~ece740/f10/lib/exe/fetch.php?media=740-fall10-lecture13-afterlecture-morecaching.pdf ↩