캐시 교체 정책

컴퓨팅에서 캐시 알고리즘(흔히 캐시 치환 알고리즘 또는 캐시 치환 정책이라고도 함)은 컴퓨터에 저장된 정보의 캐시를 관리하기 위해 컴퓨터 프로그램 또는 하드웨어로 유지되는 구조가 사용할 수 있는 명령 또는 알고리즘을 최적화하는 것입니다.캐싱은 최근 또는 자주 사용되는 데이터 항목을 일반 메모리 저장소보다 액세스 속도가 빠르거나 계산 비용이 저렴한 메모리 위치에 저장함으로써 성능을 향상시킵니다.캐시가 가득 차면 알고리즘은 새 항목을 위한 공간을 확보하기 위해 폐기할 항목을 선택해야 합니다.

개요

평균 메모리 참조 시간은^[1]

${\displaystyle T=m\times T_{m}+T_{h}+E}$

어디에

${\displaystyle m}${\$displaystyle$ m$}$ =$$ 미스비 = 1 - (히트비)

${\displaystyle T_{}}$m { $displaystyle T_{m}}$ =$$ 누락(또는 멀티 레벨 캐시의 경우 다음 캐시의 경우 평균 메모리 참조 시간)이 발생했을 때 메인 메모리에 액세스할 수 있는 시간

${\displaystyle T_{}}$h(\$displaystyle$ T_${h})$ $=$ 지연 시간: 캐시를 참조하는 시간(히트 및 미스의 경우 동일해야 함)

${\displaystyle E}${\$displaystyle$ E$}$ =$$ 멀티프로세서 시스템의 큐잉 효과 등 다양한 이차 효과

캐시의 메리트에는 레이텐시와 히트율의 2가지 주요 수치가 있습니다.캐시의 ^[1]퍼포먼스에 영향을 주는 부차적인 요인도 많이 있습니다.

캐시의 "적중률"은 검색된 항목이 실제로 캐시에서 발견되는 빈도를 나타냅니다.보다 효율적인 교체 정책은 (특정 캐시 크기에 대해) 히트율을 개선하기 위해 더 많은 사용 정보를 추적합니다.

캐시의 "지연"은 원하는 항목을 요청한 후 캐시가 해당 항목을 반환할 수 있는 시간을 나타냅니다(히트가 있을 때).신속한 교체 전략은 일반적으로 적은 사용률 정보(직접 매핑된 캐시의 경우 정보 없음)를 추적하여 해당 정보 업데이트에 필요한 시간을 단축합니다.

각 교체 전략은 히트율과 레이텐시를 절충한 것입니다.

적중률 측정은 일반적으로 벤치마크 애플리케이션에서 수행됩니다.실제 적중률은 애플리케이션마다 크게 다릅니다.특히 비디오 및 오디오 스트리밍 애플리케이션의 히트율은 0에 가까운 경우가 많습니다.스트림의 각 비트는 처음으로 읽혀지고(필수 미스), 그 후 다시 읽거나 쓰지 않기 때문입니다.더욱이 많은 캐시 알고리즘(특히 LRU)을 통해 이 스트리밍 데이터가 캐시를 가득 채우고 곧 다시 사용될 캐시 정보(캐시 오염)^[2]에서 밀려날 수 있습니다.

기타 고려해야 할 사항:

• 비용이 다른 아이템: 구하는데 시간이 오래 걸리는 아이템 등 비용이 많이 드는 아이템을 보관합니다.
• 캐시를 더 많이 사용하는 항목:항목의 크기가 다른 경우 캐시는 큰 항목을 삭제하여 여러 개의 작은 항목을 저장할 수 있습니다.
• 경과와 함께 만료되는 항목:일부 캐시는 만료되는 정보(예: 뉴스 캐시, DNS 캐시 또는 웹 브라우저 캐시)를 유지합니다.유효기간이 지났기 때문에, 컴퓨터가 아이템을 폐기할 수 있습니다.캐시 크기에 따라 아이템을 폐기하기 위한 캐싱 알고리즘이 더 이상 필요하지 않을 수 있습니다.

캐시 일관성을 유지하기 위한 다양한 알고리즘도 존재합니다.이는 동일한 데이터에 대해 여러 개의 독립 캐시가 사용되는 상황(예를 들어 단일 공유 데이터 파일을 업데이트하는 여러 데이터베이스 서버)에만 적용됩니다.

정책들

벨라디 알고리즘

가장 효율적인 캐싱 알고리즘은 앞으로 가장 오랜 시간 동안 필요하지 않은 정보를 항상 폐기하는 것입니다.이 최적의 결과를 벨라디의 최적 알고리즘/단순히 최적의 대체 정책 또는 투시적 알고리즘이라고 합니다.일반적으로 미래의 정보가 얼마나 필요할지 예측하는 것은 불가능하기 때문에, 이것은 일반적으로 실제로 구현할 수 없습니다.실제 최소값은 실험 후에만 계산할 수 있으며 실제로 선택한 캐시 알고리즘의 효과를 비교할 수 있습니다.

페이지 장해가 발생했을 때에, 몇개의 페이지는 메모리에 보존되어 있습니다.이 예에서 '5', '0', '1'의 시퀀스는 각각 프레임 1, 프레임 2, 프레임 3에 의해 액세스된다.그런 다음 '2'에 액세스할 때 프레임 1에 있는 값 '5'를 대체합니다. 이 값은 조만간 '5'에 액세스할 수 없을 것으로 예측하기 때문입니다.실제 범용 운영체제는 언제 '5'에 접속할지 예측할 수 없기 때문에 벨라디 알고리즘은 구현이 불가능하다.

랜덤 치환(RR)

후보 아이템을 랜덤으로 선택하고 필요에 따라 폐기합니다.이 알고리즘에서는 액세스 이력에 관한 정보를 유지할 필요가 없습니다.단순성을 위해 ARM ^[3]프로세서에 사용되고 있습니다.효율적인 확률적 ^[4]시뮬레이션을 허용합니다.

단순한 큐 기반 정책

선입선출(FIFO)

이 알고리즘을 사용하면 캐시는 FIFO 큐와 동일하게 동작합니다.캐시는 이전에 액세스한 횟수 또는 횟수에 관계없이 추가된 순서대로 블록을 제거합니다.

Last in First Out(LIFO) 또는 First in Last Out(FILO)

이 알고리즘을 사용하면 캐시는 스택과 같은 방식으로 동작하며 FIFO 큐와 반대 방향으로 동작합니다.캐시는 이전에 액세스한 빈도 또는 횟수에 관계없이 가장 최근에 추가된 블록을 먼저 제거합니다.

심플한 레퍼런스 기반

최근 사용(LRU)

가장 최근에 사용한 항목을 먼저 삭제합니다.이 알고리즘에서는 언제 무엇을 사용했는지 추적해야 합니다.알고리즘이 항상 가장 최근에 사용한 항목을 폐기하려면 비용이 많이 듭니다.이 기술을 일반적으로 구현하려면 캐시 라인의 "에이징 비트"를 유지하고 에이징 비트를 기반으로 "가장 최근에 사용한" 캐시 라인을 추적해야 합니다.이러한 구현에서는 캐시 라인이 사용될 때마다 다른 모든 캐시 라인의 사용 기간이 변경됩니다.LRU는 실제로 Todore Johnson과 Dennis Shasha의 ^[5]2Q와 Pat O'Neil, Betty O'Neil 및 Gerhard Weikum의 ^[6]LRU/K를 포함한 캐싱 알고리즘 패밀리입니다.

다음 예시의 액세스시퀀스는 A B C D E D F 입니다.

위의 예에서는 A B C D가 시퀀스 번호(새로운 액세스마다 증분 1)로 블록에 설치되면 E에 액세스 할 때 누락되어 블록 중 하나에 설치해야 합니다.LRU 알고리즘에 따르면 A가 최하위 등급(A(0))이므로 E가 A를 대체합니다.

두 번째에서 마지막 단계까지 D에 접속하여 시퀀스 번호를 갱신한다.

마지막으로 현재 최하위(B(1)인 B를 대신해 F에 접속한다.

가장 최근에 사용한 시간 인식(TLRU)

Time aware Lest Recently Used(TLRU;^[7] 시간 인식 최소 최근 사용)는 캐시에 저장된 컨텐츠의 유효 수명이 있는 상황을 위해 설계된 LRU의 변형입니다.이 알고리즘은 Information-Centric Networking(ICN; 정보중심 네트워킹), Content Delivery Network(CDN; 콘텐츠 전송 네트워크), 분산 네트워크 등의 네트워크 캐시 애플리케이션에 적합합니다.TLRU에는 TTU(Time to Use)라는 새로운 용어가 도입되었습니다.TTU는 콘텐츠/페이지의 타임스탬프로서 콘텐츠의 지역성과 콘텐츠 퍼블리셔 공지사항을 바탕으로 콘텐츠의 사용가능시간을 규정합니다.이 로컬 기반 타임스탬프 때문에 TTU는 로컬 관리자에게 네트워크 스토리지를 규제할 수 있는 더 많은 제어 기능을 제공합니다.TLRU 알고리즘에서는, 컨텐츠가 착신하면, 캐시 노드는 컨텐츠 퍼블리셔에 의해서 할당된 TTU 값에 근거해 로컬 TTU 값을 계산합니다.로컬 TTU 값은 로컬로 정의된 함수를 사용하여 계산됩니다.로컬 TTU 값이 계산되면 캐시 노드에 저장된 전체 콘텐츠의 서브셋에서 콘텐츠 치환이 수행됩니다.TLRU를 사용하면 인기가 적고 수명이 짧은 콘텐츠를 수신 콘텐츠로 대체할 수 있습니다.

최근 사용(MRU)

LRU(Last Recently Used)와 달리 MRU는 가장 최근에 사용한 항목을 먼저 폐기합니다.Chou와 DeWitt은 제11회 VLDB 컨퍼런스에서 발표한 결과에서 "[Looping Sequential] 참조 패턴으로 파일을 반복적으로 스캔할 때는 MRU가 최선의 대체 ^[8]알고리즘입니다."라고 언급했습니다.그 후 제22회 VLDB 컨퍼런스에 참석한 다른 연구자들은 대규모 데이터셋(^[9]일명 주기적 액세스 패턴)에 대한 랜덤 액세스 패턴 및 반복 스캔의 경우 오래된 데이터를 유지하는 경향이 있기 때문에 MRU 캐시 알고리즘이 LRU보다 적중 횟수가 더 많다는 점에 주목했습니다.MRU 알고리즘은 항목이 오래될수록 액세스할 가능성이 높은 상황에서 가장 유용합니다.

다음 예시의 액세스시퀀스는 A B C D E C D B 입니다.

여기서 A B C D는 아직 사용 가능한 공간이 있기 때문에 캐시에 배치됩니다.5번째 액세스 E에서는 D를 유지하던 블록이 최근에 사용되었기 때문에 E로 대체되었음을 알 수 있습니다.C에 대한 다른 액세스와 D에 대한 다음 액세스 시 C는 D 직전에 액세스된 블록이므로 대체됩니다.

세그먼트 LRU(SLRU)

SLRU 캐시는 수습 세그먼트와 보호 세그먼트의 2개의 세그먼트로 나뉩니다.각 세그먼트의 행은 가장 최근에 액세스한 것부터 가장 최근에 액세스한 것 순으로 정렬됩니다.누락된 데이터는 수습 세그먼트의 가장 최근에 액세스한 끝에 캐시에 추가됩니다.히트는 현재 어디에 있든 제거되고 보호된 세그먼트의 가장 최근에 액세스한 끝에 추가됩니다.따라서 보호된 세그먼트의 회선에 적어도2회 이상 액세스 하고 있습니다.보호 세그먼트는 한정되어 있기 때문에, 보호 세그먼트에서 보호 세그먼트로 회선을 이행하면, 보호 세그먼트의 LRU 회선을 보호 세그먼트의 최신 사용(MRU) 엔드로 이행할 필요가 있어, 이 회선에 액세스 하고 나서 교환할 수 있습니다.보호된 세그먼트의 크기 제한은 I/O 워크로드 패턴에 따라 달라지는 SLRU 매개 변수입니다.캐시에서 데이터를 폐기해야 할 경우 항상 행은 수습 ^[10]세그먼트의 LRU 끝에서 가져옵니다.

LRU의 근사치

연관성이 높은 캐시에서는 LRU가 엄청나게 비쌀 수 있습니다.실용적인 하드웨어는 대개 근사치를 사용하여 훨씬 낮은 하드웨어 비용으로 유사한 성능을 달성합니다.

유사LRU(PLRU)

어소시에이티브가 큰 CPU 캐시의 경우(일반적으로 4가지 이상의 방법), LRU의 구현 비용은 막대해집니다.많은 CPU 캐시에서 가장 최근에 사용된 항목 중 하나를 폐기하는 방식이면 충분하기 때문에 많은 CPU 설계자는 캐시 항목당 1비트만 있으면 작동하는 PLRU 알고리즘을 선택합니다.일반적으로 PLRU는 미스비가 약간 낮고 레이텐시가 약간 우수하며 LRU보다 소비전력이 약간 낮으며 오버헤드는 LRU에 비해 낮습니다.

다음으로 비트가 최근에 사용되지 않은 서브트리를 가리키는1비트 포인터의 바이너리 트리로 동작하는 예를 나타냅니다.리프 노드에 대한 포인터 체인에 따라 교체 후보를 식별합니다.액세스 시 액세스 방식의 리프 노드에서 루트 노드로 향하는 체인 내의 모든 포인터는 액세스 방식을 포함하지 않는 하위 트리를 가리키도록 설정됩니다.

액세스 시퀀스는 A B C D E 입니다.

여기서의 원리는 화살표 포인터만 보면 이해하기 쉽습니다.값에 액세스할 수 있지만 캐시에서 값을 찾을 수 없는 경우 메모리에서 해당 값을 로드하고 화살표가 현재 가리키는 블록에 위에서 아래로 이동합니다.블록을 배치한 후 같은 화살표를 뒤집어 반대 방향을 가리킵니다.위의 예에서는 'A'에 이어 'B', 'C', 'D'가 어떻게 배치되었는지 볼 수 있습니다.그 후 캐시가 꽉 차면 'E'가 'A'를 대체했는데, 그 이유는 화살표가 A를 가리키고 있었기 때문입니다. 그리고 'A'로 이어지는 화살표는 반대 방향을 가리키도록 뒤집혀져 있었습니다.화살표는 'B'로 이어지며, 다음 캐시 누락 시 블록이 교체됩니다.

클럭 프로

LRU 알고리즘은 오버헤드가 높기 때문에 운영 체제 등의 컴퓨터 시스템의 핵심 경로에 직접 구현할 수 없습니다.구현에는 CLOCK이라고 하는 LRU의 근사치가 일반적으로 사용됩니다.마찬가지로 CLOCK-Pro는 ^[11]시스템에서의 저비용 구현을 위한 LIRS의 근사치입니다.CLOCK-Pro는 기본 CLOCK 프레임워크 아래 있지만 3가지 주요 장점이 있습니다.첫째, CLOCK-Pro는 "시계 바늘"이 하나만 사용되는 CLOCK의 단순한 구조와는 대조적으로 3개의 "시계 바늘"을 가지고 있습니다.CLOCK-Pro는 3개의 손으로 데이터 액세스의 재사용 거리를 대략적으로 측정할 수 있습니다.둘째, 일회성 액세스 및/또는 저지역 데이터 항목을 신속하게 제거하는 등 LIRS의 모든 장점이 유지됩니다.셋째, CLOCK-Pro의 복잡성은 CLOCK의 복잡성과 동일하기 때문에 저렴한 비용으로 구현이 용이합니다.현재 버전의 Linux에서 버퍼 캐시 교환 구현은 LRU와 CLOCK-Pro를 ^[12][13]조합한 것입니다.

단순한 주파수 기반 정책

최소사용빈도(LFU)

항목이 필요한 빈도를 카운트합니다.가장 자주 사용되지 않는 것이 먼저 폐기됩니다.이 기능은 LRU와 매우 유사하지만 블록의 최근 액세스 횟수 값을 저장하는 대신 블록의 액세스 횟수 값을 저장합니다.따라서 액세스 시퀀스를 실행하는 동안 캐시에서 가장 적게 사용된 블록을 바꿉니다.예를 들어 A가 5회 사용(접속)되고 B가 3회 사용되었으며 기타 C와 D가 각각 10회 사용되었을 경우 B를 교체합니다.

최근 사용 빈도가 가장 낮은(LFRU)

Lefrequency Recently Used(LFRU)^[14] 캐시 교환 방식은 LFU 및 LRU 방식의 이점을 결합합니다.LFRU는 정보중심 네트워킹(ICN), 콘텐츠 전송 네트워크(CDN), 분산 네트워크 등의 '네트워크 내' 캐시 애플리케이션에 적합합니다.LFRU에서는 캐시는 특권 파티션과 비특권 파티션이라는2개의 파티션으로 분할됩니다.특권 파티션은 보호된 파티션으로 정의할 수 있습니다.컨텐츠가 널리 사용되는 경우, 컨텐츠는 특권 파티션에 푸시됩니다.특권 파티션의 치환은 다음과 같이 이루어집니다.LFRU는 특권 파티션에서 콘텐츠를 제거하고 특권 파티션에서 특권 파티션으로 콘텐츠를 푸시한 후 마지막으로 새로운 콘텐츠를 특권 파티션에 삽입합니다.위의 절차에서는 특권 파티션에 LRU를 사용하고 특권 파티션에 근사 LFU(ALFU) 스킴을 사용합니다.따라서 LFRU는 생략형입니다.

ALFU 방식으로 현지에서 인기 있는 콘텐츠를 걸러내고, 인기 콘텐츠를 특권 파티션 중 하나에 푸시하는 것이 기본 구상이다.

동적 에이징을 사용한LFU(LFU)

LFU with Dynamic 에이징(LFU; 동적 에이징)이라고 불리는 배리언트.다이나믹에이징을 사용하여 일반적인 오브젝트 세트의 시프트에 대응합니다.새 개체가 캐시에 추가되거나 기존 개체가 다시 참조될 때 참조 수에 캐시 에이징 팩터가 추가됩니다.LFUDA는 블록을 제거할 때 제거된 개체의 키 값으로 설정하여 캐시 에이징을 증가시킵니다.따라서 캐시 에이징은 항상 ^[15]캐시 내의 최소 키 값보다 작거나 같습니다.과거에 객체에 자주 접근했다가 현재는 비인기 상태가 된 경우 해당 객체가 캐시에 장기간 남아 있기 때문에 새로 사용되거나 사용 빈도가 낮은 객체가 해당 객체를 대체하는 것을 방지할 수 있다고 가정합니다.따라서 이 다이내믹에이징은 이러한 오브젝트의 카운트를 낮추기 위해 도입되어 교환이 가능합니다.LFUDA의 장점은 캐시 크기가 매우 작을 때 LFU로 인한 캐시 오염을 줄일 수 있다는 것입니다.캐시 사이즈가 클 경우 교체 결정이 충분하지 않고 캐시 오염도 문제가 되지 않습니다.

RRIP 스타일의 정책

RRIP 스타일의 정책은 CRC2 챔피언십에서 우승하여 당대 가장 진보된 캐시 교체 정책으로 간주된 Hawkeeye를^[16] 포함한 많은 다른 캐시 교체 정책의 기초를 형성합니다.

Re-Reference Interval Prediction(RRIP; 참조 간격 예측)

RRIP는^[17] 인텔이 제안하는 매우 유연한 정책입니다.이 정책은 뛰어난 스캔 저항성을 제공함과 동시에 재사용되지 않은 오래된 캐시 라인을 삭제할 수 있도록 합니다.모든 캐시 행에는 RRPV(Re-Reference Prediction Value)라고 불리는 예측 값이 있으며, 이 값은 회선의 재사용이 예상되는 시기와 관련이 있어야 합니다.삽입 시 이 RRPV는 보통 높기 때문에 회선이 즉시 재사용되지 않으면 제거됩니다.이는 스캔(1회만 사용되는 대량의 데이터)이 캐시를 가득 채우지 않도록 하기 위해서입니다.캐시 회선이 재사용되면 이 RRPV는 0으로 설정됩니다.이것은 이 회선이 1회 재사용되어 재사용될 가능성이 있음을 나타냅니다.

캐시 미스에서는 가능한 최대 RRPV와 동일한 RRPV를 가진 회선이 제거됩니다(3비트 값에서는 RRPV가 2 =7인³ 회선이 제거됩니다).이 값을 가진 회선이 없는 경우 세트 내의 모든 RRPV는 1에 도달할 때까지1씩 증가합니다.타이 브레이커가 필요하며, 보통은 왼쪽 첫 번째 라인입니다.이 인크리먼트는 오래된 라인이 올바르게 에이징되어 재사용되지 않을 경우 제거되도록 하기 위해 필요합니다.

스태틱 RRIP(SRRIP)

SRIP는 RRPV 값이 maxRIP인 행을 삽입합니다.즉, 삽입된 지 얼마 안 된 라인이 캐시 미스 상에서 삭제될 가능성이 가장 높습니다.

바이모달 RIP(BRRIP)

SRIP는 통상적인 경우에서는 양호한 성능을 발휘하지만 작업 세트가 캐시 크기보다 훨씬 커서 캐시 스레싱이 발생하는 경우 대부분의 경우 RRPV 값이 maxRRPV인 행을 삽입하고 가능성이 낮은 RRPV 값이 maxRRPV - 1인 행을 랜덤으로 삽입함으로써 문제를 해결합니다.이로 인해 일부 행이 캐시에 "고정"되어 스레싱에 도움이 됩니다.

단, BRRIP는 스레싱 이외의 액세스에서는 퍼포먼스를 저하시킵니다.

Dynamic RRIP(DRRIP)

작업 세트가 캐시 크기보다 작을 때 SRIP가 가장 잘 작동하고, 작업 세트가 캐시 크기보다 클 때 BRIP가 가장 잘 작동합니다.

DRIP는^[17], 양쪽 모두의 메리트를 목표로 하고 있습니다.SRIP 또는 BRRIP 중 어느 쪽을 사용할지 선택하기 위해 set^[18] deeling을 사용합니다.SRIP만을 사용하도록 몇 개의 세트(일반적으로 32개)를 할당하고 BRIP만을 사용하도록 할당하며, 이러한 세트 중 어떤 것이 더 나은지 모니터링하는 정책 카운터를 사용하여 캐시의 나머지 부분에서 사용할 정책을 결정합니다.

Bélady 알고리즘에 가까운 캐시 교환 정책

Bélady의 알고리즘은 최적의 캐시 치환 정책이지만 향후 가장 오래 재사용될 회선을 제거하기 위해서는 미래에 대한 지식이 필요합니다.과거의 액세스 패턴으로부터 장래의 재사용 거리를 예측하기 위한 복수의 교환 정책이 제안되고 있습니다.따라서 최적의 대체 정책에 근접할 수 있습니다.가장 성능이 뛰어난 캐시 교체 정책 중 일부는 Bélady의 알고리즘을 모방하려고 시도하는 정책입니다.

호크아이

Hawkeeye는^[16] PC에 의한 과거의 액세스를 사용하여 Bélady의 알고리즘을 에뮬레이트하여 캐시 프렌들리 액세스(나중에 사용되는 액세스) 또는 캐시 애버스의 액세스(나중에 사용되지 않는 액세스) 중 어느 쪽을 생성하는지 예측하려고 합니다.

이를 위해 다수의 캐시 세트를 샘플링하여(정렬되지 않음), 길이${\displaystyle }8{\displaystyle \mathrm{}}$ × ${\displaystyle \text{캐시}}$ 크기$(\$ 8$\text {cache$ size$})$의 이력을 사용하고 이러한 액세스에서 벨라디의 알고리즘을 에뮬레이트합니다.이를 통해 정책은 캐시해야 할 회선과 캐시해서는 안 될 회선을 파악할 수 있습니다.

이 데이터를 통해 명령이 캐시 친화적인지 캐시 거부적인지 예측할 수 있습니다.이 데이터는 다음으로 RIP에 공급되며 캐시 프렌들리 명령으로부터의 접근은 낮은 RRPV 값(나중에 제거될 가능성이 있음)을 가지며 캐시 애버스의 명령으로부터의 접근은 높은 RRPV 값(빠른 시일 내에 제거될 가능성이 있음)을 갖습니다.

RRIP 백엔드는 실제 삭제 결정을 하는 부분입니다.샘플링된 캐시와 OPT 제너레이터는 삽입된 캐시 라인의 초기 RRPV 값 설정에만 사용됩니다.

Hawkeeye는 2017년 ^[19]CRC2 캐시 챔피언십에서 당시 다른 캐시 교체 정책을 모두 제치고 우승을 차지했습니다.

하모니는 프리페치 성능을 향상시킨 호크아이 확장판이다^[20].

모킹제이

모킹제이는^[21] 호크아이를 여러 가지 방법으로 개선하려고 한다.첫째, 바이너리 예측을 폐기하여 제거할 캐시 라인을 보다 세밀하게 결정할 수 있습니다.둘째, 추가 정보를 이용할 수 있게 된 후 나중에 제거할 캐시 라인을 결정합니다.

이를 실현하기 위해서는 고유 액세스와 이를 생성한 PC 및 타임스탬프의 샘플링된 캐시를 유지합니다.샘플링된 캐시 내의 회선에 다시 액세스하면 시간차가 Reuse Distance Predictor로 전송됩니다.이 경우 시간차이 ^[22]프레딕터는 새로운 RDP vale가 이상치를 보완하기 위해 작은 수치만큼 증가 또는 감소시킵니다.숫자는 w ${\displaystyle =}$ ${\displaystyle m}$ ${\displaystyle a}$x ( ${\displaystyle \frac{\text{1}}{}}$,${\displaystyle \frac{\text{timestamp}}{}}$ ${\displaystyle \frac{\mathrm{difference}}{}}$ 16$$ {$displaystyle$ w$=max(1,{\frac {text{$text{$text{difference}}{16$로 계산되며, 값이 초기화되지 않은 경우를 제외하고 관측된 재사용 거리가 직접 삽입됩니다.샘플링된 캐시가 가득 차서 회선을 폐기해야 할 경우 마지막으로 액세스한 PC가 스트리밍 액세스를 생성하는 RDP를 훈련합니다.

액세스 또는 삽입 시 이 회선의 예상 재사용 시간(ETR)이 갱신되어 예측 재사용 거리가 반영됩니다.세트에 몇 번 액세스할 때마다 세트의 모든 ETR 카운터가 감소합니다(재사용 예상 시간을 초과하여 액세스하지 않을 경우 음수가 될 수 있음).

캐시 누락 시 절대 ETR 값이 가장 높은 행이 제거됩니다(앞으로 가장 오래 재사용될 것으로 예상되거나 과거에 가장 오래 재사용된 것으로 추정되고 재사용되지 않은 행).

Mockingjay는 최적의 Bélady 알고리즘에 매우 가까운 결과를 얻습니다.일반적으로 퍼포먼스 차이는 불과 몇 %입니다.

머신 러닝을 사용한 대체 정책 캐시

여러 캐시 대체 정책이 퍼셉트론, 마르코프 체인 또는 다른 유형의 기계 학습을 사용하여 ^[23][24]제거되는 라인을 예측하려고 시도했습니다.캐시 교체 문제에 대한 학습 증강 알고리즘도 있습니다.^[25][26]

기타 캐시 교체 정책

Low Inter-Reference Recency Set(LIRS; Low Inter-Reference Recency Set)

LIRS는 페이지 치환 알고리즘으로 LRU 및 기타 많은 새로운 치환 알고리즘보다 성능이 향상되었습니다.이것은, 재이용 거리를, 액세스 된 페이지의 순위를 동적으로 매겨 치환을 ^[27]결정하는 지표로서 사용합니다.LIRS는 기준치를 사용하여 대체 결정을 내리기 위한 Inter-Reference Recency(IRR)를 평가함으로써 LRU의 한계에 효과적으로 대처합니다.

위 그림에서 "x"는 블록이 시간 t에 액세스됨을 나타냅니다.블록 A1이 시간 1에 액세스되면 첫 번째 액세스 블록이므로 Recency가 0이 되고 IRR이 시간 3에 다시 액세스될 것으로 예측되므로 1이 된다고 가정합니다.A4에 액세스한 이후 시간 2에서는 A4가 가장 최근에 액세스한 개체이고 IRR이 4가 되어 계속되기 때문에 A4는 0, A1은 1이 됩니다.시간 10에 LIRS 알고리즘에는 두 개의 LIR 집합 = {A1, A2}과(와) HIR 집합 = {A3, A4, A5}이(가) 포함됩니다.10시에 A4에 액세스 할 수 있으면, 미스가 발생합니다.LIRS 알고리즘은 가장 큰 빈도로 인해 A2가 아닌 A5를 제거합니다.

적응형 교환 캐시(ARC)

LRU와 LFU의 균형을 지속적으로 유지하여 조합 ^[28]결과를 개선합니다.ARC는 최근 제거된 캐시 항목에 대한 정보를 사용하여 사용 가능한 캐시 공간을 최대한 활용하기 위해 보호된 세그먼트 및 임시 세그먼트의 크기를 동적으로 조정함으로써 SLRU를 개선합니다.이 ^[29]예에서는 적응형 치환 알고리즘에 대해 설명합니다.

AdaptiveClimb(AC)

최근 히트/실수를 사용하여 점프 위치를 조정하고, 상승 시 한 슬롯을 위로 전환하고, LRU에서 히트 위치를 위로 전환합니다.따라서,^[30] 프로그램이 고정 범위 내에 있을 때 상승의 최적성과 LRU와 같이 새로운 범위에 대한 신속한 적응의 혜택을 누린다.^[31] 또한 캐시 상부에 대한 참조가 있을 때 추가로 릴리스하여 코어 간의 캐시 공유를 지원합니다.

어댑티브 치환(CAR)이 있는 시계

Adaptive Replacement Cache(ARC)와 CLOCK의 장점을 결합합니다.CAR는 ARC에 필적하는 성능을 갖추고 있으며 LRU와 CLOCK를 모두 크게 능가합니다.ARC와 마찬가지로 CAR도 셀프 튜닝이므로 사용자 지정 매직파라미터가 필요 없습니다.2개의 클럭 T1과 T2 및 2개의 단순 LRU 리스트 B1과 B2의 4개의 이중 링크리스트를 사용합니다.T1 클럭은 "주파수" 또는 "장기 유틸리티"를 기준으로 페이지를 저장하는 반면, T2는 "주파수" 또는 "장기 유틸리티"를 사용하여 페이지를 저장합니다.T1 및 T2에는 캐시 내의 페이지가 포함되어 있으며, B1 및 B2에는 각각 T1 및 T2에서 최근에 삭제된 페이지가 포함되어 있습니다.알고리즘은 이들 리스트 B1'T2 및 B2'T1의 크기를 유지하려고 합니다.새로운 페이지는 T1 또는 T2에 삽입됩니다.B1에 히트하면 T1의 사이즈가 커지고 B2에 히트하면 T1의 사이즈가 작아진다.사용되는 적응 규칙은 ARC와 같은 원리로 페이지가 더 추가될 때 더 많은 히트를 제공하는 목록에 더 많이 투자합니다.

멀티큐(MQ)

다중 큐 알고리즘 또는 MQ는 서버 버퍼 캐시와 같은 두 번째 레벨 버퍼 캐시의 성능을 개선하기 위해 개발되었습니다.그것은 Zhou, Philbin, ^[32]Li의 논문에 소개되어 있다.MQ 캐시에는 다수의 LRU₁ 큐(Q_m-1, Q, ..., Q)가₀ 포함되어 있습니다.여기서 m 값은 특정 큐 내의 모든 블록의 라이프 타임을 기반으로 한 계층을 나타냅니다.예를 들어 j>i의 경우 Q의_j 블록은 Q의_i 블록보다 라이프타임이 길어집니다.이들 외에 모든_out 블록 식별자 목록과 액세스 빈도를 유지하는 큐인 이력 버퍼Q도 있습니다.Q가 가득 차면_out 가장 오래된 식별자가 제거됩니다.블록은 소정의 라이프 타임 동안 LRU 큐에 머무릅니다.MQ 알고리즘에 의해 동적으로 정의되는 것은 같은 파일에 대한2개의 액세스 사이의 최대 시간 거리 또는 캐시 블록의 수 중 큰 것입니다.블록이 라이프 타임 내에 참조되지 않은 경우 블록은 Q에서Q로_ii−1 강등되거나 Q에 있는₀ 경우 캐시에서 삭제됩니다.각 큐에는 최대 액세스카운트도 있습니다.큐_i Q 내의 블록에 2회ⁱ 이상 접근하면 2회 이상ⁱ⁺¹ 접근하거나 라이프타임이 만료될 때까지 이 블록은 Q로_i+1 승격됩니다.특정 큐 내에서 ^[33]블록은 LRU에 따라 액세스의 빈도에 따라 순위가 매겨집니다.

그림에서 알 수 있다.MRU 큐가 캐시에 배치되는 방법.그림도 참조.Q가_out 블록 식별자와 대응하는 액세스 빈도를 저장하는 방법.최근 1회밖에 접속하지 않았기 때문에a는 Q에₀ 배치되지 않았습니다.또, 액세스 빈도는 2와 4이므로, Q에서 b와_out c가 각각 Q와₂ Q에 어떻게₁ 배치되었는지 확인할 수 있습니다.블록이 배치되는 큐는 log(f)로서₂ 액세스 빈도(f)에 의존합니다.캐시가 가득 차면 가장 먼저 제거되는 블록은 이 경우 a의 Q의 선두가₀ 됩니다.a에 한 번 더 접속하면 b 아래의 Q로 이동합니다₁.

패니어:복합 객체의 컨테이너 기반 캐싱 알고리즘

Pannier는^[34] 다양한 액세스 패턴을 가진 블록이 있는 서로 다른(이종) 컨테이너를 식별하는 컨테이너 기반 플래시 캐싱 메커니즘입니다.Pannier는 priority-queue 기반 생존 대기열 구조를 사용하여 컨테이너의 생존 시간을 기준으로 컨테이너의 순위를 매깁니다. 이는 컨테이너의 실시간 데이터에 비례합니다.Pannier는 핫 데이터와 콜드 데이터를 분리하는 세그먼트 LRU(Segmented LRU)를 기반으로 구축되었습니다.또한 Pannier는 다단계 피드백 컨트롤러를 사용하여 플래시 쓰기를 조정하여 플래시 수명을 보장합니다.

「 」를 참조해 주세요.

• 캐시 오비어스 알고리즘
• 참조 위치
• 분산 캐시

레퍼런스

외부 링크

• 다양한 캐시 알고리즘의 정의
• 플래시/SSD 캐싱 알고리즘