[CA] Lecture #26 (1)

Block Replacement Policy

▶ LRU (Least-Recently Used)

• Direct mapped cache: Set 하나 당 엔트리가 1개이다. 따라서 선택지는 하나뿐이다.
• 2-way associative cache: Set 하나 당 엔트리가 2개이다. 따라서 가장 덜 최근에 사용된 것을 지우고, 그 자리에 필요한 데이터를 쓴다. --> timestamp를 위한 bit: 1-bit (2^1 = 2)
• Fully associative cache(= 4-way associative cache): Set 하나 당 엔트리가 4개이다. 따라서 가장 덜 최근에 사용된 것을 지우고, 그 자리에 필요한 데이터를 쓴다. --> timestamp를 위한 bit: 2-bit (2^2 = 4)

- 장점: Temporal locality - 최근에 사용한 데이터는 다시 사용할 확률이 높다. 따라서 최근에 사용한 데이터를 남기는 것은 현명한 선택이다.

- 단점: timestamp를 위한 비트를 더 필요로한다. 따라서 이러한 오버헤드를 줄이기 위해, ramdom replacement policy를 사용하는 경우도 많다.

 

LRU Block Replacement - Example

2-way associative cache

 

---

Multi-level Caches

▶ Miss penalty vs. Miss rate

• Multi-level cache: miss penalty를 줄인다. 즉, L1 cache에서 miss가 발생해도, 아직 L2 cache가 있기 때문에, 메모리로의 접근을 막을 수 있다. 따라서 cache miss가 발생해도, clock cycle이 크게 증가하지 않는다. 
• 2-way associative cache, fully associative cache: miss rate를 줄인다. 즉, 하나의 set 당 sub-room이 여러 개이기 때문에, 캐시에서 지워야하는 횟수가 줄어들고, 따라서 cache hit이 발생할 확률이 높아진다.

▷ L1 cache: L1 cache의 목적은 CPU로 최대한 빠르게 접근하는 것이다. 따라서 작고, 빠르다. --> Direct mapped cache

▷ L2 cache

▷ L3 cache: L3 cache의 목적은 메모리로의 접근을 최대한 막는 것이다. 따라서 miss rate을 줄이는 것이 가장 중요하다. --> Fully associative cache

 

Multi-level Cache - Example

L2 캐시를 도입하면 CPI(Clock cycle Per Instruction)이 어떻게 바뀔까?

Multi-level Cache - Example

: L2 캐시를 도입하면, L1 캐시에서 miss가 발생해도 L2 캐시가 backup으로 남아있다. 따라서 miss가 발생해도 바로 메모리로 접근할 필요가 없다. --> Reduce miss penalty!

• L1 캐시 접근으로 인한 penalty: 1 clock cycle
• L2 캐시 접근으로 인한 penalty: 20 clock cycles
• 메모리 접근으로 인한 penalty: 400 clock cycles

▷ L1 cache만 있을 때: 1 + 0.02*400

• 1: L1 캐시에 일단 접근해야 한다.
• 0.02: L1 캐시 miss가 발생할 확률
• 400: L1 캐시 miss가 발생하면, 메모리로 접근한다.

▷ L2 cache를 도입할 때: 1 + 0.02*20 + 0.005*400

• 1: L1 캐시에 일단 접근해야 한다.
• 0.02: L1 캐시 miss가 발생할 확률
• 20: L1 캐시 miss가 발생하면, L2 캐시로 접근한다.
• 0.005: L2 캐시 miss가 발생할 확률
• 400: L2 캐시 miss가 발생하면, 메모리로 접근한다.

--> 만약 L2 캐시 miss까지 발생한다면... L2 캐시를 도입함으로써 오히려 CPI를 늘리게 된다. (쓸데없이 캐시 접근에 clock cycle을 소비함)

 

---

Virtual Memory

• Problem: Main memory에 모든 데이터를 저장할 수가 없다. Disk에도 저장해야 한다.
• Solution: Virtual memory에 main memory와 disk의 address를 저장한다!

Address Translation

 

Page Table

: Virtual memory의 page와 Main memory의 page를 매핑해준다.

Page Table

- 4K = (2^2 * 2^10) bytes

• Page offset: Virtual memory의 page를 구분하기 위한 bit --> 4K의 page 크기에서는 12-bit가 필요하다.
• Physical page number = (32 - Page offset) bits

 

TLB (Translation Lookaside Buffer)

• Problem: Page table은 main memory에 저장되어 있다. Page table register가 main memory의 page table 주소를 가리킨다. 따라서 원하는 데이터를 찾기 위해 virtual memory의 page에 접근하고 나서, 그 page가 main memory의 어떤 page와 매핑되는지 확인하기 위해서는 main memory에 접근해야 한다.
• Solution: TLB

: TLB는 page table에 대한 캐시 메모리 역할을 한다. Page table entry의 일부를 TLB에 저장해둔다. 그렇게 하면, page table을 확인하기 위해 main memory에 접근할 필요가 없어진다!

 

 

 

 

 

출처: 이화여자대학교 윤명국교수님 컴퓨터구조