캐시 메모리 교체 정책 Overview

- 캐시 메모리 시리즈 모아보기 - 
https://microelectronics.tistory.com/102

캐시 용량 및 교체 정책

캐시 메모리는 제한된 공간을 가지고 있기 때문에, 이 공간이 다 찼을 때 어떤 데이터를 제거할지 결정하는 교체 정책이 필요하다. 교체 정책의 목표는 성능을 최적화하기 위해 곧 사용되지 않을 데이터를 현명하게 제거하는 것이다.

1. 교체 정책

캐시에는 다양한 교체 정책이 있으며, 각각의 정책은 장단점이 있다.

• Direct-Mapped Cache는 선택의 여지가 없기 때문에, 특정 주소는 오직 한 위치에만 저장될 수 있다. 그 위치가 이미 차 있다면 기존 데이터를 제거하고 새로운 데이터를 그 자리에 넣어야 한다.
• Fully-Associated 또는 Set-Associative Cache는 조금 더 유연하다. 같은 데이터가 여러 위치에 저장될 수 있기 때문에 어떤 데이터를 제거할지를 선택할 수 있는 여지가 생긴다.

대표적인 교체 정책에는 다음 두 가지가 있다:

• 랜덤 교체(Random Replacement): 캐시에서 제거할 블록을 임의로 선택한다.
• 최소 최근 사용(Least Recently Used, LRU): 가장 오랫동안 사용되지 않은 블록을 제거하는 방식이다.

1.1 Random Replacement Policy

랜덤 교체 정책은 말 그대로 캐시 내의 블록 중 하나를 무작위로 선택해 제거한다.

예를 들어, 검은색 루프와 파란색 루프 두 개로 구성된 프로그램을 실행할 때, 각 루프의 명령어가 차례로 캐시에 로드된다. 검은색 루프에서 파란색 루프로 전환할 때, 랜덤 교체 정책은 임의로 블록을 제거하기 때문에 때로는 재사용될 파란색 루프의 명령어가 제거될 수 있다.

이는 캐시 히트율을 떨어뜨리고 성능 저하로 이어질 수 있다.

 

1.2 Least Recently Used Policy

LRU 정책은 가장 오랫동안 사용되지 않은 데이터를 제거하는 방식을 취한다. 같은 예시에서, 검은색 루프를 다 실행한 후 파란색 루프를 시작하면, LRU 정책은 가장 이전에 사용된 검은색 루프의 명령어부터 제거해 새로운 명령어를 넣는다.

이 방식은 최근에 사용된 데이터를 최대한 유지하기 때문에, 시간지역성을 유지할 수 있어 성능 면에서 유리하다.

2. 시간 지역성과 정책 비교

반응형

시간지역성이란 프로그램 실행 중 방금 사용된 데이터가 다시 사용될 가능성이 높은 성질을 의미한다. 예를 들어, 반복문 내의 명령어들은 반복될 때마다 다시 사용되기 때문에, 시간지역성을 잘 활용하는 정책은 이 데이터들을 캐시에 유지하려 한다.

• 랜덤 교체 정책은 시간지역성을 무시하는 경향이 있다. 데이터가 새롭든 오래되었든 동일한 확률로 제거될 수 있기 때문이다.
• LRU 정책은 시간지역성을 중시하여, 가장 오래된 데이터를 우선적으로 제거하고 새로운 데이터를 유지한다. 일반적으로 이 정책은 성능 향상에 도움이 된다.

3. LRU 구현의 어려움

하지만 LRU 정책에는 단점도 있다. 캐시 내의 모든 항목의 접근 순서를 정확히 추적하는 것은 어려울 수 있다. 특히, 캐시가 더 많은 연관성을 가질수록 복잡성이 증가한다.

• 2-way 캐시의 경우, 오래된 항목을 추적하는 데 1비트만 필요하기 때문에 구현이 비교적 간단하다.
• 높은 연관성의 캐시에서는 더 많은 비트가 필요하고, 구현이 복잡해진다.

이러한 복잡성 때문에, 실제 LRU의 구현은 복잡하고 많은 비트와 자원을 필요로 한다.

이를 해결하기 위해 LRU를 근사하는 Pseudo-LRU가 개발되었으며, 이 정책은 적은 하드웨어 리소스와 간단한 알고리즘으로 LRU와 유사한 성능을 제공한다.

 

결론

캐시의 공간이 제한적이기 때문에, 어떤 데이터를 유지하고 어떤 데이터를 제거할지를 결정하는 정책은 시스템의 효율성과 처리 속도에 큰 영향을 미친다.

랜덤 교체 정책은 간단하고 구현이 쉬운 장점이 있지만, 시간지역성을 무시하기 때문에 성능 저하를 일으킬 수 있다.

반면, 최소 최근 사용(LRU) 정책은 시간지역성을 적극적으로 활용하여 일반적으로 더 나은 성능을 제공한다. 그러나 LRU는 높은 연관성의 캐시에서는 구현이 복잡해지고 많은 하드웨어 자원을 필요로 한다는 단점이 있다.

 

이러한 LRU의 구현상의 문제를 해결하기 위해 Pseudo-LRU와 같은 근사 알고리즘이 개발되었다. Pseudo-LRU는 LRU에 비해 적은 자원으로도 유사한 성능을 제공할 수 있어, 하드웨어 복잡성과 성능 간의 균형을 유지하는 데 효과적이다.

 

Reference

• https://www.youtube.com/watch?v=p-UsUuQelUY&list=PL9YOoYsOKCKA-r0uYHnG53jgU0xyScAdh&index=9