6.4-Cache_Memories

초기에는 3가지 레벨의 계층구조, Register, Main Memory, Disk 로 존재해왔다.
그러나, CPU 와 Main Memory 간의 성능 차이가 점점 커지면서,
CPU 와 Main Memory 사이에 하나의 계층을 추가해야한다는 목소리가 커졌다.
이에 작은 SRAM Cache Memory 가 추가되었고, 이는 라고 불렸다.
보통 4 Cycle 정도의 빠르기로 Register 와 비슷하다.

CPU와 Register 간의 성능 차이가 점점 늘어가면서, 더 큰 Cache 에 대한 필요성이 대두되었다.
이에 L2 Cache 가 L1 Cache 와 Main Memory 사이에 추가되었다.
L2 Cache 는 10 Cycle 정도의 속도를 가진다.

현대 시스템은 여기서 더 큰 L3 Cache 를 L2 와 Main Memory 사이에 두기도 한다.
이는 50 Cycle 정도의 속도를 가진다.

여기서는 논의를 간단하게 하기 위해, L1 Cache 만 가정하고 이야기한다.
하지만, 역시 그 기본적인 내용은 L2, L3 등등에 대해 똑같이 적용된다.

6.4.1 Generic Cache Memory Organization

Cache 는 Set, Line, Data Block 으로 이루어진다.
Cache 는 개의 의 배열로 이루어져있다.
각각의 Set 은 개의 으로 이루어져있다.
각각의 Line 은

개의 Byte 로 이루어진 과
Cache 가 정보를 저장하는지 알려주는 과
Cache Line 에서 Block 을 식별해주는 로 구성된 로
구성되어있다.

Cache 의 구조는 으로 표현할 수 있다.
이 때 Cache 의 사이즈 는 가능한 모든 Block 의 총합이기 때문에,
tab bit 와 valid bit 는 제외된다. 따라서, 로 표현된다.

CPU가 Main Memory 의 A 주소의 값을 원할 때, CPU는 A 주소를 Cache 로 보낸다.
Cache 가 만약 A를 가지고 있다면 바로 전달해주는데,
Cache 는 어떻게 가지고 있다는 것을 알고 있을까?

Cache 는 주소를 간단하게 검사하는 것으로 원하는 Word 가 존재하는지 찾을 수 있게 정렬되어있다. 이는 마치, Hash Table 에서 매우 간단한 Hash 함수를 쓰는 것과 유사하다.

, 가 길이의 주소를 3부분으로 나눈다.
articles/chapter6/imgs/organization_of_cache.png
는 S set 배열에서 어느 set 에 존재하는지 알려준다.
set 을 알고나서는 t tag bit 는 어느 Line 에 존재하는지 알려준다.
이 때, valid bit 가 설정되어있어야만, 해당 정보를 가지고 있다고 판단한다.
마지막으로 b Block Offset Bit 는 원하는 Word 가 존재하는 Block 까지의 거리를 알려준다.

아래는 지금까지 나온 매개변수를 정리한 것이다.
articles/chapter6/imgs/summary_of_cache_parameters.png

6.4.2 Direct - Mapped Caches

Cache 는 하나의 Set 당 몇개의 Line 을 가지는지, 즉 에 따라 서로 다른 종류로 분류할 수 있다.
정확히 1개의 Line 을 가지는 Cache 를 라고한다.
articles/chapter6/imgs/direct_mapped_cache.png

이 Direct - Mapped Cache 를 통해, 앞으로 이야기를 진행한다.
우리에게 CPU, Register, L1 Cache, Main Memory 가 있다고 가정해보자.

CPU 가 Memory 에서 Word w 를 읽고자한다고 했을 때,
L1 Cache 에 요청하게 되고, 존재한다면(Cache Hit) 빠르게 w 를 반환해준다.
없다면(Cache Miss), L1 Cache 가 Main Memory 에 요청할 때까지 기다린다.
요청에 의해 도착하면 L1 Cache 는 해당 내용이 담긴 Block 을 Caching 하고,
w 를 추출해 전달한다.

Cache 가 요청에 대해 Hit 인지 Miss 인지 판단하고, Word 를 추출하는 과정은 아래의 3단계로 나뉜다.

Set Selection
Line Matching
Word Extraction

Set Selection in Direct - Mapped Caches

Cache 는 w 를 위한 주소에서 s Set Index 를 추출한다.
이를 Unsigned Integer 즉, Set Index 로 해석한다.
우리는 Cache 가 Set 에 대한 1차원 배열로 이루어져있다고 생각해볼 수 있다.
articles/chapter6/imgs/set_selection.png

Line Matching in Direct - Mapped Caches

전 단계에서 어느 Set 을 살펴봐야하나 결정했다.
다음 단계로는 Line 을 결정하는 일이지만, Direct - Mapped Cache 는
Line 이 하나이므로 간단하다.
w 를 가지고 있는지의 여부는 Valid Bit 와 tag 가 올바른지 확인하면 알 수 있다.

articles/chapter6/imgs/line_matching.png
위 그림에서 Vaild Bit, Tag Bit 를 확인하는 것을 알 수 있다.
2개 모두 올바르면 Cache Hit 이고, 아니라면 Cache Miss 임을 알 수 있다.

Word Selection in Direct - Mapped Caches

만약 Cache Hit 임을 전 단계에서 확인했다면, 우리는 w 가 어느 Block 에 존재함을 알 수 있다.
정확한 위치는 Block Offset 을 통해 구할 수 있으며, 이를 통해 Word 크기만큼 복사하면 된다.
위의 그림에서는 Word 가 4Byte 임을 가정하고, 4개의 Block 을 복사한다.

Line Replacement on Misses in Direct - Mapped Caches

Cass Miss 임을 확인하게 된다면, 다음 레벨의 Block 에게 요청하고,
그 정보를 Cache Line 에 저장해야한다.
일반적으로 해당 Set에서 이미 가능한 Line 이 가득차면, 어느 Line 이 제거되어야한다.
Direct - Mapped Cache 는 Line 이 1개이므로 제거되어야할 Line 은 자명하다.

Putting It Together: A Direct - Mapped Cache in Action

Cache 가 Set 과 Line 을 결정하는 과정은 매우 단순하다.
왜냐하면, 하드웨어가 이를 ns 안에 해결해야하기 때문이다.

그러나, 그 과정이 사람에게는 혼란을 줄 수 있기 때문에 예제를 통해 설명한다.

라고 가정한다. 즉,

4개의 Set
Set 당 1개의 Line
2 Byte 로 구성된 Block
4 Bit 로 구성된 주소
이다.
또한, Word 는 1 Byte 로 구성된다고 가정한다.

tag와 index bit 을 통해, block 을 일대일로 맵핑할 수 있다.
예를 들어, tag, index 가 0 이라면, 0번 Block 이다.

8개의 Memory Block 이 존재한다.
하지만 4개의 Cache Set 이 존재하므로, 여러개의 Block 이 같은 Cache Set 을 이용할 수 있다.
예를 들어, 0, 4 Block 은 Set 0 으로 포함된다.

같은 Set 에 포함되는 Block 은 Tag Bit 을 통해 구분된다.
0과 4 Block 은 Tag Bit 가 각각 0, 1 인것으로 구분된다.
articles/chapter6/imgs/4_bit_address_ex.png

이러한 조건 속에서 Cache 의 행동을 시뮬레이션 해본다.
Word 크기는 1 Byte 임을 기억하고 진행한다.

초기의 Cache 는 비어있다. 즉 Valid Bit 은 모두 0이다.
articles/chapter6/imgs/cache_0.png
각 줄은 하나의 Cache Line 을 의미한다.

Read Word at Address 0.
모든 Valid Bit 이 0이므로 Cache Miss 이며,
다음 레벨의 장치에서 데이터를 가져오고, Caching 을 진행한다.
그 후, m[0] 을 반환하고 저장한다. (m[0] 은 Memory 주소 0에서의 데이터를 의미한다.)
Read Word at Address 1
이것은 Cache Hit 으로 바로 m[1] 을 반환하게 된다.
Read Word at Address 13
Set 2 가 Invalid 하기 때문에, Cache Miss 이다.
Block 6을 가져와서 저장하고 반환한다.
Read word At Address 8
Set 0 은 Valid 하지만, Tag 가 맞지 않으므로 Cache Miss 이다.
Block 4 를 가져와서 저장하고, 반환한다.
이 과정에서 기존의 Block 0 은 제거된다.
Read Word at Address 0
바로 직전에 Block 0 이 제거되었기 때문에 Cache Miss 이다.
Cache 는 충분하지만, 다른 Block 이 참조되고 있기 때문에 발생한 Miss 이므로,
Conflict Miss 이다.

Conflict Misses in Direct - Mapped Caches

Direct - Mapped Cache 에서 2의 거듭제골꼴의 길이를 가진 배열에 접근할 때,
Conflict Miss 가 발생하곤한다. 다음의 예제를 살펴보자.

	float dotprod(float x[8], float y[8]) {
		float sum = 0.0;
		for(int i = 0; i < 8; i++) 
			sum += x[i] * y[i];
		return sum;
	}

위의 함수는 좋은 Locality 를 가졌으므로, Cache Hit 이 잘 일어날거라고 기대되지만,
그렇지 않을 수 있다.

다음을 가정해보자.
x 는 각 원소가 0부터 4Byte 단위로 이어진다. 즉, 0, 4, 8, ... 28 의 주소를 갖는다.
y 는 32부터 60까지의 주소를 갖는다.

Cache 는 Block 이 16Byte 의 크기이며, 2개의 Set 을 가진다고 가정한다.
즉, 총 크기는 32 Byte 이다. 이때, 주소에 해당하는 Set Index는 다음과 같다.
articles/chapter6/imgs/conflict_miss_ex.png

x[0] 에 대해서, x[0] 부터 x[3] 까지가 Caching 된다.
다음으로 y[0] 에 대해서, y[0] 부터 y[3] 까지 Caching이 되는데,
이 때, x[0] 와 y[0] 가 같은 공간을 차지하게 된다.
이 때문에 모든 x[] 와 y[] 에 대한 참조는 Cache Miss 특히, Conflict Miss 가 발생한다.

이런 식으로 Cache 가 같은 데이터에 대해 계속해서 저장되고, 지워지는 과정을
이라고 한다.

자연스러운 형태로 앞의 Bits 을 Index로 잡으면, Cache 저장에 비효율적이다.
특히, Locality 가 높아 그 주변에 대해 참조하는 경우에는, Cache 에 많은 정보가 저장될 수 없다.

articles/chapter6/imgs/why_cache_has_middle_index.png
위의 그림에서 배열을 순차적으로 순회한다고 가정해보자.
첫번째 경우에 대해서는 처음 4개의 Block 을 같은 Set 에 저장하게 된다.
이것이 반복되어서, 결국 매 순간에 한 Set 만 사용하게 되는 비효율이 발생한다.
이것을 Middle-Order Index 과 비교하면, 더 효율적임을 알 수 있다.

결론적으로 좋은 Locality 에도 불구하고, 같은 Cache Set 을 사용하게 되어,
Conflict Miss 가 발생한다.
이는 간단한 예시로 살펴보았지만, 충분히 현실에서도 발생할 수 있다.

다행히 원인을 안다면, 해결방법은 상대적으로 쉽다.
한가지 쉬운 해결책은 Byte 의 padding 원소를 각 배열에 추가한다.
예를 들어, x[8] 이 x[12] 이 되도록 늘려준다.
이는 Set Index를 아래와 같이 바꾼다.
articles/chapter6/imgs/padding_ex.png
이를 통해, Thrashing 을 제거할 수 있다.

6.4.3 Set Associative Caches

이전에 Conflict Miss 가 발생한 이유는 근본적으로 Set 이 오직 하나의 Line 만을 가졌기 때문이다.
은 여러개의 Line() 를 가지고 있다.
특히 개의 Line 을 가짐을 강조하여, 라고 한다.
우리는 정확히 인 경우는 나중에 살펴볼 것이다.

Set Selcection in Associatve Caches

Set 을 고르는 과정은 direct - mapped Cache 와 동일하다.
articles/chapter6/imgs/asso_cache.png

Line Matching and Word Selection in Set Associative Caches

여러개의 Line 이 존재하기 때문에 Direct - Mapped Cache 와는 달리,
Tag Bit 를 검사한다.
전통적인 Memory 는 주소를 입력으로서 받으면, 그 값을 돌려준다.
반면에 Associative Memory 는 (Key, Value) 의 배열로 되어있다.
즉, Key 를 입력받아 (Key, Value) 를 반환해준다.

따라서 우리는 Associative Cache 에 존재하는 Set 을 작은 Associative Memory로 생각해,
Tag 와 Valid Bit 을 합친 것을 Key 로, Block 의 내용을 Value 로 생각할 수 있다.

Line 이 가질 수 있는 Memory Block 에는 제한이 없기 때문에,
모든 Line 에 대해 검사해야만 한다.
만약 찾게 되면, Block Offset 을 통해 그 결과를 반환해준다.
articles/chapter6/imgs/line_match_in_asso_cache.png

Line Replacement on Misses in Associative Caches

Cache Miss 가 발생할 때, 어느 Line 을 제거해야할까?
만약 빈 Line 이 존재한다면, 그 Line 은 좋은 후보지만, 모두 차있을 경우에는 어떻게 할까?
그렇다면 고른 Line 이 더이상 참조되지 않기를 기대해야한다.

프로그래머가 해당 Replacement Policy 를 코드에 적용시키는 것은
어렵기 때문에 자세히 설명하지 않는다.
가장 간단한 방법은 랜덤으로 지정하는 것이다.
좀 더 정교하게는 Princicple of Locality 에 기대어, 이후에 참조될 가능성이 가장 적은 Line 을 고른다.
예를 들어 LFU(Least Frequently Used) Policy 는 가장 적게 참조된 Line 을 제거한다.
또는 LRU(Least Recently Used) Policy 는 가장 마지막으로 접근된 Line을 제거한다.
이는 하드웨어적으로 더 시간이 걸리지만, CPU에서 먼 장치로 가는 것보다는 빠르다.

6.4.4 Fully Associative Caches

Fully Associative Cache 는 단 하나의 Set 으로 구성되어 있다.
articles/chapter6/imgs/full_asso_cache.png

Set Selection in Fully Associative Caches

Set 선택은 단순하다. 왜냐하면 Set 이 1개밖에 없기 때문이다.
또한, Index bit 이 없기 때문에, 주소는 tag 와 Block Offset 으로만 나뉘어진다.

Line Matching and Word Selection in Fully Associative Caches

이는 Associative Cache 와 동일하게 작동한다.
그러나, 일치하는 Tag 를 병렬적으로 찾아야하기 때문에, 용량이 크면서 빠르게는 만들기 어렵다. 그래서 작은 Cache 나 TLB(Transition Lookside Buffer) 정도에서 사용된다.

6.4.5 Issues with Writes

Cache 의 Read 는 직관적이다.
Cache Hit 의 경우, 바로 반환하며, Miss 의 경우 저장한 다음 반환한다.

반면에 Cache Write 의 경우는 좀 더 복잡하다.
Write Hit, Cache 에 저장된 데이터에 대해 Write 가 일어나면 어떻게 하는가?

가장 간단한 방법은 write 마다 다음 단계의 장치도 write 하는 이지만,
이는 Write 로 인한 Bus Traffic 을 증가시킨다.

다른 방법은 이라는 방법이다.
이는 해당 데이터가 Cache 에서 없어질 때, 다음장치에 write 를 시도하는 것이다.
이는 Locality 가 좋을수록 그 효율이 증가한다.
하지만, 추가적인 복잡도, Cache Block 이 변했는지 확인하는 Dirty Bit 가 필요한 등
단점이 존재한다.

또 다른 문제는 Write Miss 에서 발생한다.
한가지 접근은 라고 알려진 방법이다.
다음 레벨 장치에서 해당하는 Block 의 데이터를 Cache 로 가져와서 Cache 에서 Update 한다.
이는 Locality 에 기대하는 동작이지만, 매 Miss 마다 다음 레벨 장치의 Block 이동이 있다는 단점이 있다.

다른 방법으로 가 있다.
이는 Cache 를 건너띄고, 바로 다음 레벨 장치에 Write 하는 것이다.

보통 Write-through Cache 는 no-write-allocate 를,
Write-back Cache 는 write-allocate 를 사용한다.

Write 를 최적화하는 작업은 미묘하고 어려운 작업으로,
여기서는 간단하게 살펴보았다.

프로그래머로서 Cache-friendly 한 코드를 작성하고 싶다면,
Write-back, Write-allocate Cache 방식이라고 가정하고 작성하는 것을 추천한다.
낮은 계층의 메모리는 전송 시간이 길기 때문에 write-back 을 많이 사용하기 때문이다.
또한, Write-back, Write-allocate 는 Read 를 다루는 방법과 유사하기 때문에 통일된 시각으로 볼 수 있다.

6.4.6 Anatomy of a Real Cache Hierarchy

여태까지는 데이터만 저장하는 것으로 이야기했지만, 명령어도 Cache 에 저장할 수 있다.
명령어(Instruction) 만 저장한 Cache 를 라고 한다.
반면에 데이터만 저장한다면 라고 한다.
만약 둘다 존재한다면 라고 한다.

현대의 프로세서는 분리된 i-cache 와 d-cache 를 가진다.
이에 대한 이유로,
분리되어있기 때문에 동시에 2개의 Cache 를 읽을 수 있다.
또한, 보통 I-Cache 는 Read-Only 이기 때문에 간단하다.
2개의 Cache 는 접근 방식에 대해 다른 최적화를, 다른 Block 크기 등등을 가질 수 있다.
또한 분리됨으로서 서로 간의 Conflict Miss 가 발생하지 않게 해준다.

다음은 i7 CPU에 대한 전체적인 이미지이다.
articles/chapter6/imgs/i7_ex.png

6.4.7 Performance Impact of Cache Parameters

Cache 의 성능은 보통 아래의 지표를 통해 평가된다.

Miss Late
프로그램이 동작하는 동안, Miss 한 비율을 나타낸다.
로 나타낸다.
Hit Rate
Hit 한 비율을 나타낸다. 로 표현할 수 있다.
Hit Time
Cache 에서 CPU로 Word 를 전달하는데 걸리는 시간을 의미한다.
이는 Set Selection, Line Identification, Word Selection 을 포함한다.
이는 L1 Cache 의 Cycle 에 비례한다.
Miss Penalty
Miss 로 인해 필요한 추가시간이다.
L1 에 대해 L2 는 10, L3 는 50, Main Memory 에 대해서는 200 Cycle 에 비례한다.

비용과 성능에 대한 trade-off 를 최적화하는 것은
수많은 시뮬레이션과 실제 벤치마크가 필요한, 우리의 범위를 넘어선다.
하지만, 일부 trade-off 관계를 살펴볼 수 있다.

Impact of Cache Size

큰 Cache 사이즈는 Hit Rate 의 비율을 높여준다.
하지만, 그 속도는 느려질 것이다. 즉 Hit Time 이 커지게 된다.
이것은 L1 이 L2 보다, L2가 L3 보다 용량이 작은 이유를 설명해준다.

Impact of Block Size

큰 Block 사이즈는 복합적이다.
Spatial Locality 에 기대어 Hit Rate 를 늘려주지만,
큰 Block 사이즈는 적은 수의 Line 을 암시하기 때문에 Temporal Locality 를 낮춰
Hit Rate 를 낮출 수도 있다.
또한, 전송시간을 늘리기 때문에 Miss Penalty 에도 악영향을 끼친다.

Impact of Associativity

매개변수 , 즉 Set 당 Line 의 개수가 끼치는 영향이다.
가 클수록, Conflict Miss 로 인한 Thrashing 이 줄어든다.
하지만, 가 큰 Cache 는 만들기 비싸며, 빠르게 만들기 어렵다.
더 많은 Tag bit, 추가적인 LRU(Least Recently Used) 상태 Bit, 추가적인 통제 로직을 필요로하기 때문이다.
또한, 증가된 복잡성 때문에 Hit Time 을 증가시킬 수 있다.
Miss Penalty 측면에서도 제거할 Line 을 찾기 위한 로직의 복잡성 증가로 증가할 수 있다.

Impact of Write Strategy

Write-Through 방식은 더 구현하기 쉽고,
Cache 를 업데이트하는데 무관하며 따로 동작하는 Write Buffer 를 사용할 수 있다.
그리고, Read Miss 는 추가적인 Write 가 발생하진 않기 때문에 비교적 싸다.

반면에 Write-back 방식은 더 적은 이동으로, DMA 를 사용하는 I/O 장치에게 넓은 대역폭을 제공할 수 있다. 또한 이동의 횟수를 줄이는 것은 이동의 비용이 많이 드는 낮은 레벨의 장치에서 중요하다. 일반적으로 낮은 레벨일수록 Write-back 을 사용하는 경향이 있다.