Three Kinds of Cache Mapping 문서 원본 보기

==개요==
<gallery caption="Figure 1. Cache category" widths="350px" heights="250px">
Direct-Mapped Cache.png|Figure 1.(a) Direct-Mapped Cache
Set-Associative Cache.png|Figure 1 (b). Set-Associative Cache
Fully Associative Cache.png|Figure 1 (c). Fully Associative Cache
</gallery>
캐시(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==
[[파일:First step of cache mecahnism.png|섬네일|Figure 2. First step of cache mecahnism]]
[[파일:Figure 3. Second step of cache mecahnism.png|섬네일|Figure 3. Second step of cache mecahnism]]
캐시 히트(hit)와 미스(miss)를 분석하기 위해, Direct-mapped 캐시와 접근할 주소가 주어졌다고 가정하자:<br>
먼저 캐시 내에 해당 주소가 가리키는 데이터가 있는지 확인하기 위해서는 set index bit를 사용해야 한다. Figure 2는 set index = 0b00001이므로, set 1에 접근하여 캐시 블록을 탐색하는 것을 보여준다. 이때 주의해야 할 것은 다수의 메모리 블록이 여러 set 내에 존재할 수 있다는 것이다. 하지만 해당 케이스는 E = 1이고, 하나의 캐시 라인(캐시 블록)에는 하나의 메모리 블록을 저장하므로 해당 예시에는 하나의 set에는 하나의 메모리 블록이 저장된다.
[[파일:Figure 3. When cache miss is occured.png|섬네일|Figure 4. When cache miss is occured]]
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

===Analyzing Cache Hit/Miss Exercise===
[[파일:Exercise -1.png|가운데|섬네일|500x500픽셀|Figure 5. Exercise #1]]
Figure 5와 같은 상황이 주어졌을 때, 다음 네가지 질문에 답해보자.
# What are S, t, s and b?
# What is the cache hit rate of this code?
# If m is changed to 64, does cache hit rate change?
# If the size of array element is changed to 8, does cache hit rate change?
1. <code>C = B x E x S = 2<sup>12</sup> = 2<sup>4</sup> x 1 x E</code>이므로, <code>S = 2<sup>8</sup> = 256</code>이다. 이에 따라, <code>b = log<sub>2</sub>B = 4, s = log<sub>2</sub>S = 8</code>이다. 또한 <code>m = t + s + b</code>이므로 <code>t = 20</code>이다.<br>
2. <code>B = 16bytes</code>이므로, set 1에는 <code>a[0~3]</code>이, set 2에는 <code>a[4~7]</code>이, ..., set 256에는 <code>a[1020~1023]</code>이 저장된다. 이 경우 <code>a[0], a[4],...,a[1020]</code>일 때에는 캐시 미스가 발생한다. 하지만 <code>a[1~3], a[5~7],..., a[1021~1023]</code>의 경우는 이미 캐시 미스로 인해 캐시에 데이터가 로드된 후 접근하므로 캐시 히트가 발생한다. 따라서 <code>hit rate = 75%</code>이다.<br>
3. <code>m = 64</code>가 바뀌어도 바뀌는 것은 tag bits의 개수만 42로 바뀐다. 이때 t는 hit rate에 직접적인 연관이 있는 변수는 아니므로 hit rate를 바꿀 수 없다.<br>
4. <code>B = 16bytes</code>이므로, set 1에는 <code>a[0~1]</code>이, set 2에는 <code>a[2~3]</code>이, ..., set 256에는 <code>a[510~511]</code>이 저장된다. 이에 따라 hit rate를 계산하면 50%이다.

===Thrashing===

==각주==
[[분류:컴퓨터 시스템]]