직접 매핑 된 명령어 캐시 VS LRU 대체를 사용하는 완전 연관 명령어 캐시

Question

크기가 작은 캐시의 경우 직접 매핑 된 명령어 캐시가 LRU 대체를 사용하여 전체 연관 명령어 캐시보다 성능이 더 좋을 수 있습니다.

누구나 이것이 예제 액세스 패턴으로 어떻게 가능할 지 설명 할 수 있습니까?

Answer 1

작은 크기의 캐시에서 발생할 수 있습니다. 크기 2의 캐시를 비교해 봅시다.

예를 들어, 직접 매핑 된 "DM"캐시는 홀수 주소의 경우 행 A를, 짝수 주소의 경우 행 B를 사용합니다.

LRU 캐시는 가장 최근에 사용되지 않은 행을 사용하여 누락 된 값을 저장합니다.

내가 제안하는 액세스 패턴은 13243142 (원하는만큼 반복)입니다.

여기에 서투른 캐싱 알고리즘이 동작하는 방법의 고장이다 :

8 LRU에 대한 미스 직접 매핑 6을 제공

H - hits 
M - misses 

----- time ------>>>>> 

Accessed: 1 | 3 | 2 | 4 | 3 | 1 | 4 | 2 
      \ \ \ \ \ \ \ \ 
LRU A ? | ? | 3 | 3 | 4 | 4 | 1 | 1 | 2 | 
    B ? | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 
      M M M M M M M M 

DM A ? | 1 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 
    B ? | ? | ? | 2 | 4 | 4 | 4 | 4 | 2 | 
      M M M M H M H M 

. 이 패턴은 영원히 반복됩니다 경우의가 어떻게되는지 보자

----- time ------>>>>> 

Accessed: 1 | 3 | 2 | 4 | 3 | 1 | 4 | 2 
      \ \ \ \ \ \ \ \ 
LRU A  | 2 | 3 | 3 | 4 | 4 | 1 | 1 | 2 | 
    B  | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 
      M M M M M M M M 

DM A  | 1 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 
    B  | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 2 | 
      H M H M H M H M 

그래서 직접 매핑 캐시 LRU의 0 % 안타를 능가하는 성능 히트의 50 %를해야합니다. LRU 캐시가 항상 그리워 있도록

• 이 패턴을 반복 모든 주소 이전이 액세스 (그리고이 두 가지가 다르다)에 대한 액세스되지 않은 : 때문에

  이이 방식으로 작동합니다.

• DM 캐시는 해당 패턴이 마지막으로 사용 된 시간을 사용하도록 패턴이 설계되어 있기 때문에 때때로 누락됩니다.

따라서 한 번 더 큰 캐시 크기 비슷한 패턴을 만들 수 있지만, 더 큰 캐시 크기는 더 이상 이러한 패턴은 할 필요가있다. 이것은 더 큰 캐시의 경우 이러한 방식으로 악용하는 것이 더 힘들 것이라는 직관에 해당합니다.