Lecture 19: Memory Hierarchy - 3

경희대학교 김정욱 교수님의 컴퓨터 구조 수업을 기반으로 정리한 글입니다.

Common Framework for Memory Hierarchy

▶ cache / main memory

 

TLB는 address를 mapping하는 정보밖에 없기 때문에, data를 포함한 캐시보다 작다.
용량이 클수록 miss rate가 낮다. 때문에 miss rate은 L1 > L2 > main memory

 

※ 용량 - L1: layer 1 cache < L2: secondary cache

Block Placement of Memory Hierarchy

Q1. Block이 어디에 위치할 수 있는가?

▶ Direct mapped / Set associative / Fully associative 

▶ Miss rate 확률

 

cache size가 증가할수록 miss rate 감소한다.
Associativity가 증가할수록 temporal locality에 의해 miss rate가 감소한다.

그러나, associative가너무 커지면 saturation (포화) 확률이 높아진다.

Fining Blocks of Memory Hierarchy

Q2. 어떤 Block을 찾아야(교체를 위해) 하는가?

▶ Direct mapped / Set associative / Fully associative 

• Direct mapped: index에 match되는 set 당 block 개수가 1개이므로, 하나만 비교
• Set associative: index에 match되는 set 당 block 개수가 degree of associativity(자유도) 만큼 있으므로, 자유도에 맞는    개수만큼 비교
• Full: 그 자체로 하나의 set이기 때문에 모든 cache size만큼의 block과 비교, 미리 계산된 lookup table이 있다면 비교할     필요 X

Block Replacement of Memory Hierarchy

Q3. Cache miss가 일어났을 때 어떤 Block이 교체되어야 하는가?

• Direct-mapped: set에 존재하는 하나의 block만 교체됨
• Set associative: set에 존재하는 associativity만큼의 block이 교체 후보
• Fully associative: 모든 block이 교체 후보

Two primary strategies for replacement
1. Random: 후보 blocks 중 무작위로 선택됨 
2. Least recently used  (LRU): 가장 오래 사용되지 않은 block이 교체된다. (reference bit = 0)

 

용량이 너무 큰 경우에는, 각각의 공간에 reference bit를 주면서 bit를 교체하는 게 물리적으로 어렵다.

또한, 용량이 커지면 커질수록 최근에 쓴 것을 선택할 확률이 매우 작아지기에,

용량이 커지면 커질수록 Random 방식을 많이 사용한다.

 

혹은, associativity가 큰 경우 LRU를 근사하여 사용한다.

Virtual memory의 경우, miss 발생시 disk에 접근하는 것은 손해가 매우 크기에, 근사된 LRU를 사용한다.

Write Policy of Memory Hierarchy

Q4. Write할 때 무슨 일이 일어나는가?

 

1. Write-through
값이 업데이트될 때마다 cache에서 main memory로 바로 write하는 기법이다.
write-back보다 상대적으로 구현이 쉽고 값이 꼬이지 않기에 consistent가 유지된다는 장점이 있다.

대신, cache를 둔 목적을 상실한다는 단점이 있어, 이를 해결하기 위한 방식이 Write buffer를 두는 방식도 있다.

 

Write buffer를 두면, cache  입장에선 매번 main memory로 가는 것이 아니라,

Write buffer에다 저장을 해놓고 main mory로 한 번에 간다.

하지만, 이 방식은 Write buffer가 가득차면 stall이 된다는 단점이 있다.

 

2. Write-back

값 업데이트시 dirty bit를 1로 바꿔주고,

나중에 그 값들이 더이상 쓰이지 않아 교체되어야 할 때 dirty bit를 보고 저장을 해준다.

 

즉, cache에만 정보가 저장되고, 수정된 block이 교체될 때만 main memory의 저장소에 반영한다.

 

하지만, 이 방식은 cache와 main memory 사이에 consistent가 맞지 않아,

multi process를 할 때 문제가 된다는 단점이 있다.

Virtual memory
write-back 방식만 사용한다.
그 이유는, lower level인 disk에 wirte하는 것은 시간이 오래 걸리기 때문이다.

Source of Misses

miss의 종류는 총 3가지가 있다.

 

1. Compulsory misses (= cold-start misses)
RAM은 휘발성이기에 컴퓨터를 키면 cach엔 아무것도 들어 있지 않는다.

때문에, 이런 경우 무조건 발생하는 miss이다. (solution 존재 X)

 

2. Capacity misses
cache의 용량 자체는 크지 않은데, 이때 cache가 가득 차 발생하는 miss이다. (cache 안에서 일어나는 miss)

즉, 모든 block이 가득 찼을 때 발생하는 miss이다. (block 교체 필요)

 

-> solution: cache size를 키우면 된다.

 

3. Conflict misses (= collision misses)
associativity 때문에 발생하는 miss로, 값을 교체해야 할 때 발생하는 miss이다. (cache의 set 안에서 일어나는 miss)

즉, 하나의 set이 포함할 수 있는 block 개수에 제한이 있기 때문에 발생한다.

 

이때, 캐시에 공간이 남아 돌아도 set이 포함하는 block 개수(associativity)가 작으면 발생한다.

때문에, direcet cache, set-associative cache의 경우, full associative cache에 비해 conflict miss가 자주 일어난다.

 

-> solution: associativity (자유도)를 증가시키면 된다.

▶ Miss rate per three types of misses

• Capacity miss: cache 용량이 커질수록 miss rate 감소 (miss의 가장 많은 부분 차지)
• Conflict misses: associativity가 많아질수록 miss rate 감소

temporal locality 때문에, One-way에서 Two-way 갈 때 miss rate이 가장 많이 줄어든다.

Challenges of Memory Hierarchy Design

Cache size: Miss rate vs. Access time

• cache size가 증가하면 miss rate는 감소하지만 access time은 증가할 수 밖에 없다.

Associativity: Miss rate vs. Access time

• associativity가 증가하면 miss rate는 감소하지만 access time은 증가할 수 밖에 없다.

Block size: Miss rate vs. Miss penalty

• block size가 증가하면 miss rate는 감소하지만 miss penalty은 증가할 수 밖에 없다. (spatial locality)

※ block size 증가시, miss penalty가 증가하는 이유는 size가 클수록 뭉탱이로 더 많이 확 가져와야 하기 때문이다. 예를 들면, 원래는 하나만 가져올 것을, 주변까지 다 끌어서 가져와야 한다.

▶ cache size / associativity / block size

Concluding Remarks

Principle of Locality

• Spatial locality
• Temporal locality

Memory hierarchy

• Cache
  
  • Directed-mapped
  • Set associative
  • Fully associative
• Main memory
• Virtual memory (물리적인 memory X)
• Disk

Multilevel caches for cache optimization