의사 LRU

Pseudo-LRU

유사 LRU 또는 PLRU는 캐시 내의 모든 값의 정확한 경과시간을 유지하는 것이 아니라 대략적인 경과시간을 사용하여 값을 치환함으로써 Lerest Recently Used(LRU) 알고리즘의 성능을 향상시키는 캐시 알고리즘 패밀리입니다.

PLRU는 보통 트리 PLRU와 비트 PLRU의 2가지 캐시 치환 알고리즘을 나타냅니다.

트리 PLRU

Tree-PLRU는 일련의 항목과 항목에 대한 일련의 액세스이벤트를 고려하여 최근에 접근하지 않았을 가능성이 가장 높은 항목을 선택하는 효율적인 알고리즘입니다.

이 기술은 Intel 486의 CPU 캐시 및 Freescale의 Power와 같은 PowerPC 패밀리의 많은 프로세서에서 사용됩니다.Apple Computer에서 사용하는 PC G4.

알고리즘은 다음과 같이 동작합니다.해당 항목의 바이너리 검색 트리를 검토합니다.트리의 각 노드에는 "의사 LRU 요소를 찾기 위해 왼쪽으로 이동" 또는 "의사 LRU 요소를 찾기 위해 오른쪽으로 이동"을 나타내는 1비트 플래그가 있습니다.유사 LRU 요소를 찾으려면 플래그 값에 따라 트리를 이동합니다.항목 N에 대한 액세스로 트리를 업데이트하려면 트리를 탐색하여 N을 찾은 후 트래버설 중에 노드 플래그를 선택한 방향과 반대 방향으로 설정합니다.

Pseudo LRU working

이 알고리즘은 근사치이기 때문에 차선일 수 있습니다.예를 들어 위의 A, C, B, D 캐시 라인이 있는 그림에서 접근패턴이 C, B, D, A일 경우 C 대신 B를 선택합니다.이는 A와 C가 모두 같은 절반에 있고 A에 액세스하면 캐시 라인 C를 포함하지 않는 나머지 절반으로 알고리즘이 유도되기 때문입니다.

비트 PLRU

비트 PLRU는 캐시 행마다 1개의 상태 비트를 저장합니다.이러한 비트를 MRU 비트라고 부릅니다.회선에 액세스 할 때마다 MRU 비트가 1로 설정되어 회선이 최근에 사용되었음을 나타냅니다.세트의 상태 비트의 마지막 0비트가 1로 설정될 때마다 다른 모든 비트는 0으로 재설정됩니다.캐시가 누락되면 MRU 비트가 0인 맨 왼쪽 행이 [1]교체됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 마이크로아키텍처 모델 자동 생성


Stub icon

이 컴퓨터 과학 기사는 촌스럽다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.