[ACA] Memory Hierarchy and Caches (3)

이전 포스팅에서는 메인 메모리와 캐시 메모리간의 매핑하는 방법을 배웠다. Direct-mapped Cache는 쉽고 간단하지만 Hit rate이 낮은 단점이 있었고, 이를 보완하기 위한 Fully Associative Cache는 아무런 규칙없이, 인덱스없이 아무데나 저장하는 방식이어서 원하는 데이터를 찾으려면 캐시 메모리 전체를 탐색해야 하기 때문에, 탐색 시간이 긴 단점이 있다. 그래서 이 둘의 단점을 보완할 수 있는, 둘의 장점을 절충한 방법인 Set Associative Cache는 어레이의 특정 행을 지정해서 그 행이 비어있으면, 행의 아무 열에 데이터를 저장하는 방식이다. 이는 Direct-mapped 방식보다 검색은 느리지만, 저장은 빠르며 Fully Associative 방식보다 저장은 느리지만, 검색이 빠르다는 장점이 있다.

 

두 방법의 장점을 적절히 결합한 Set Associative지만 몇가지 문제점이 있다. Miss가 났을 때, 그 블록을 어떻게 처리할 것인가다. 이는 캐시 메모리에서 블록의 우선순위(priority)를 어떻게 정해줄 것이냐는 문제로 직결된다. 이 이슈를 해결할 때 고려할 사항으로는 Insertion, Promotion, Eviction 세가지가 있다.

 

Insertion

삽입된 캐시 블록의 우선순위를 어떻게 결정할 것인가?

 

Promotion

Cache hit이 발생한 이후에 블록의 우선순위를 어떻게 결정할 것인가?

 

Eviction (Replacement)

Cache miss가 발생한 이후에 블록의 우선순위를 어떻게 결정할 것인가?

Cache miss가 발생한 이후에는 블록을 교체해주는데, 교체되는 블록을 Victim이라고 한다.

 

이번 포스팅에서는 위의 세가지 사항 중, Eviction Policy에 대해 자세히 알아볼 것이다. 우리가 어떤 블록을 교체할 것인가에 대해서는 여러가지 정책들이 있다. 나이브하게는 랜덤하게 블록을 선택할 수도 있을 것이다. 혹은 캐시에서 가장 오랫동안 있었던 블록을 선택할 수도 있을 것이고, 최근에 가장 적게 사용된 블록을 교체할 수도 있을 것이다. 우리가 정책을 만들 때 가장 중요하게 생각할 것은 Locality를 어떻게 하면 최대한 활용할 수 있을 것이냐, 그리고 간단하게 구현할 수 있을 것인가다. 대표적인 정책들은 다음과 같다.

 

Eviction (Replacement) Policy

- Random (randomly select a block)

- FIFO (block that has been in cache the longest)

- Least recently used (LRU)

- Not most recently used (NMRU)

- Leat frequently used (LFU)

 

이중에서 LRU Policy에 대해 자세히 알아보도록 하겠다.

 

LRU Policy는 가장 최근에 사용된 적이 적은, 접근한 적이 적은 블록을 교체하는 정책이다. 이 정책의 기본적인 가정은 가장 오랫동안 사용되지 않은 블록이라면 앞으로도 사용될 확률이 낮다는 것이다. 이걸 구현하려면, 우선순위를 위해 Set에 있들 블록들에 카운터를 달아줘야 하는데, 카운터 값이 크면, 우선순위가 높은 것으로 해석한다. 이때 카운터의 사이즈는 몇 Way짜리 set-associative냐에 따라 달라지는데, N-way set-associative인 경우 log_2 (N)가 된다.

 

예. 4-way를 표현하려면 2bit가 필요하다. (10, 01, 00, 11)

 

그림으로 확인하면 다음과 같다. 이제 LRU가 실행되었을 때, 어떻게 되는지 살펴보자.

1. 캐시가 비어있는 상태다.

2. Way3의 카운터값이 가장 낮기 때문에, Way3에 A가 저장되었고, 카운터 값이 제일 커졌다. 다른 Way의 카운터 값이 갱신되었다.

3. Way2의 카운터값이 가장 낮기 때문에, Way2에 B가 저장되었고, 카운터 값이 제일 커졌다. 다른 Way의 카운터 값이 갱신되었다.

4. Way1의 카운터값이 가장 낮기 때문에, Way1에 C가 저장되었고, 카운터 값이 제일 커졌다. 다른 Way의 카운터 값이 갱신되었다.

5. Way0의 카운터값이 가장 낮기 때문에, Way0에 D가 저장되었고, 카운터 값이 제일 커졌다. 다른 Way의 카운터 값이 갱신되었다.

6. 정책에 따라, Way3의 카운터 값이 가장 작기 때문에 Way3의 데이터가 E로 교체되었다.

7. Way2에 B가 있기 때문에 카운터 값이 제일 커졌다.

8. Way0에 D가 있기 때문에 카운터 값이 제일 커졌다.

9. Way2에 B가 있기 때문에 카운터 값이 제일 커졌다.