컴퓨터 구조 5_Cache Performace

 

Fully associativity와 set associativity에 해당하는 내용이다.
Fully 에 해당하는 경우 메모리의 데이터가 Cache의 빈자리에 들어가면 되는데
빈자리가 없는 경우 기존의 다른 데이터가 나와야 한다. 하지만 이 경우에는
아무곳이나 들어갈 수 있으므로 어떤 데이터를 나오게 해야하는 것인가? 하는
문제가 있다. 
Which block should be replaced on a cache miss?
1. 랜덤하게 나간다. 이것도 방법이긴 하지만 공학을 하는 입장에서
그렇게 좋은 방법 같아 보이지는 않는다.
2. FIFO(First In First Out), 데이터 구조 Queue에서 봤던 동작 원리이다.
여러 개의 block이 있다면 Cache에 가장 오랬동안 있었던 block이 나가게 한다.
예를 들어 도서관에 공부하러 왔는데 자리가 없어서 기다리고 있는 상황이라고 해보자
기존에 있던 학생 중 한 명이 무조건 나가야 하고 어떤 학생이 나가는 것이
fair 한 것일까? 가장 오랫동안 사용한 학생을 내보내는 것이 그나마 공정해보인다.
Time stamp가 필요하다. 왜냐하면 누가 가장 오래 사용했는지 탐지할 수 있는 것이
있어야 하기 때문이다. 꽤 공정해보이기는 하지만 자주 사용되는 block이 제거될 수 있는
위험성이 존재한다.

 

3. LRU(Least Recently Used)
가장 최근에 사용하지 않은 것.
Cache에 오래 있었지만 reference 되지 않은 것을 탐지하여 내보내는 것.
도서관에 언제 온지에 상관없이 공부를 가장 하지 않은 학생을 내보내는 것.
이 경우도 Time stamp가 존재해야 한다.(필요함)
하지만 Time stamp를 계속적으로 찍어야 해서 overhead가 커질 확률이 많다.
4. LFU(Least Frequently Used)
Reference한 횟수를 count하여 가장 사용이 안됀 것을 내보내는 것
Counter가 필요하다. 하지만 1번 밖에 reference되지 않았지만 방금 전에
들어온 Block이 나가게 되는 경우가 생긴다는 것이다.
예를 들어 방금 전에 도서관에 들어온 학생이 제일 적게 공부했으므로 나가라는
fair한 경우가 발생할 수 있다는 것이다.

 

 

가장 좋은 방법은 미래에 가장 사용하지 않을 Block을 내보내는 것이 좋다.
하지만 미래는 알 수 없으므로 과연 이 Optimal한 것에 가까운 것이 무엇인가??
이 중에는 LRU가 가장 성능이 좋은 것으로 알려져있다.
(OS 수업 시간에 자세히 다룰 것임)

 

Assuming we use the LRU strategy
: directed mapped, 2-way set associative, fully associative

 

 

Cache를 Multi Level로 두는 방법이 있다.
Cache level1 과 level2 이렇게 나누는 것이다. 
2 level이 있다고 가정하면 1번째 level은 CPU 안에 있는 것이고 
2번째 level은 SRAM 안에 있는 것이다.
Example에서 숫자는 중요하지 않으니까 굳이 하지 않아도 된다.

 

 

Block size를 조절하는 것
Direct, Set, Fully 중 Fully는 가장 복잡하지만 가장 좋은 성능을 낸다고 알려져있다.
LRU가 Optimal에 가장 가까운 성능을 보인다.
요즘은 Cache를 Multi level로 나눠서 사용하기도 한다.

 

Cache: Summary
locality 특성으로 hierachy 를 만들어 구현할 수 있다.
block size에 따라서 miss ratio와 miss penalty가 왔다갔다 하기 때문에 적당한
크기를 찾아야 한다는 것. block size가 커짐에 따라 performance가 낮아질 수 있는데
이를 방지하기 위해 Wide Bus를 한다는 등 interleaving이 방법이 될 수 있다.

 

 

Cache Structure
: direct, fully, set
fully는 miss rate를 줄이지만 복잡하고 값이 비싸다.
CPU time이라는 것은 요즘 Cache의 miss되는 시간까지 고려해서 계산하고 있다.