[컴퓨터 구조] Lecture 19: Memory Hierarchy - Part3

경희대학교 김정욱 교수님의 컴퓨터 구조 강의 내용을 기반으로 한 정리글

 

Common Framework for Memory Hierarchy

• TLB는 address를 mapping하는 정보밖에 없기 때문에, data를 포함한 L1 캐시보다 작다.
• 많은 용량을 가질수록 miss rate가 낮다 -> TLB는 사용한 값을 또 부를 확률이 높기 때문에 낮은 miss rate

 

1. Block이 어디에 위치할 수 있는가?
2. 어떤 Block이 발견될 것인가?
3. Cache miss가 일어났을 때 어떤 Block이 교체되어야 하는가?
4. Write bit이 on이면 무슨 일이 일어나는가?

 

Block Placement of Memory Hierarchy

Q1. Where Can a Block Be Placed?

• direct mapped, fully associative는 set-associative의 variations의 일종으로 생각할 수 있다.
• 자유도가 증가하면 -> miss rate가 감소한다.

Scheme name	Number of sets	Blocks per set
Direct mapped	캐시의 총 blocks 개수	1
Set associative	캐시의 총 blocks 개수 / 자유도	자유도 (typically 2 - 16)
Fully associative	1	캐시의 총 blocks 개수

 

• cache size 증가 -> Miss rate 감소
• Associativity 증가 -> 전에 쓰인 block이 교체될 확률 감소 -> miss rate 감소
• 그러나 자유도 너무 커지면 saturation 확률이 높아짐
• cache size 커질수록 associativity로부터의 영향이 감소

 

Q2. How is a Block Found?

Associativity	Location method	Comparisons required
Direct mapped	Index	1
Set associative	Index로 알맞은 set을 찾고, 해당 set의 elements 중에서 탐색	associativity 만큼
Full	모든 cache entires를 탐색	cache size 만큼
	separate lookup table	0

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

 

Q3. Which Block Should Be Replaced on a Cache Miss?

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

Two primary strategies for replacement

• Random: 후보 blocks 중 무작위로 선택됨
• Least recently used(LRU): 가장 오래 사용되지 않은 block이 교체된다.
• associativity가 큰 경우 -> LRU가 근사되어 사용되거나, Random replacement가 사용된다.

Virtual memory

• 근사된 LRU 사용 -> miss rate가 작더라도, miss가 발생했을 때(disk에 접근해야 함)의 손해가 큼

 

Q4. What Happens on a Write

Write-through

• cache에 저장될 때마다, lower level의 block(memory)에도 바로 write하는 기법
• write-back보다 상대적으로 구현이 쉬움

Write-back

• cache에만 정보가 저장되고, 수정된 block이 교체될 때만 lower level의 저장소에 반영

Virtual memory

• write-back만 쓰임
• lower level(disk)에 wirte -> Long latency

 

Source of Misses

Compulsory misses (=cold-start misses)

• first access -> 해당 block이 cache에 접근된 적이 아예 없을 때 발생

Capacity misses

• cache가 모든 block을 포함할 수 없을 때 -> program에서 cache에서 out된 block을 요구할 때 발생
• solution: cache size를 키우면 된다.

Conflict misses (=collision misses)

• set-associative/direct-mapped cache에서 발생
• 하나의 set이 포함할 수 있는 block 개수에 제한이 있기 때문에 발생 -> 캐시에 공간이 남아 돌아도 set이 포함하는 block 개수(associativity)가 적으면 발생
• solution: associativity를 증가시키면 된다.

 

Miss rate per three types of misses

 

• Capacity miss -> 용량이 커질수록 miss rate 감소
• Conflict misses -> associativity가 많아질수록 miss rate 감소

 

Challenges of Memory Hierarchy Design

• Cache size: Miss rate vs. Access time
• Associativity: Miss rate vs. Access time
• Block size: Miss rate vs. Miss penalty

 

Increases cache size

• capacity misses 감소
• access time to cache 증가

Increases associativity

• conflict misses 감소
• access time to cache 증가

Increases block size

• spatial locality에 의해서 -> miss rate 감소
• large size block(원래는 하나만 가져올 것을, 주변까지 다 끌어서 가져와야 함) -> miss penalty 증가