본문으로 이동

캐시 교체 정책

위키백과, 우리 모두의 백과사전.
페이징에 특화된 상세 알고리즘에 대해서는 페이지 교체 알고리즘 문서를 참고하십시오.

캐시 교체 정책(Cache replacement policies), 캐시 교체 알고리즘 또는 캐시 알고리즘은 컴퓨팅에서 컴퓨터 프로그램 또는 하드웨어 유지 구조가 정보 캐시를 관리하는 데 활용할 수 있는 명령 또는 알고리즘을 최적화하는 것이다. 캐싱은 일반 메모리 저장소보다 액세스 속도가 더 빠르거나 계산 비용이 저렴한 메모리 위치에 최근 또는 자주 사용되는 데이터 항목을 보관하여 성능을 향상시킨다. 캐시가 가득 차면 알고리즘은 새 데이터를 위한 공간을 확보하기 위해 삭제할 항목을 선택해야 한다.

개요

[편집]

평균 메모리 참조 시간은 다음과 같다.[1]

여기서

= 미스율 (miss ratio) = 1 - (히트율)
= 미스가 발생했을 때 메인 메모리에 액세스하는 데 걸리는 시간 (또는 다단계 캐시의 경우, 다음 단계의 하위 캐시에 대한 평균 메모리 참조 시간)
= 레이턴시: 캐시를 참조하는 데 걸리는 시간 (히트와 미스 시 동일해야 함)
= 다중 프로세서 시스템의 큐잉 효과와 같은 2차 효과

캐시에는 레이턴시와 히트율이라는 두 가지 주요 성능 지표가 있다. 여러 2차적 요인 또한 캐시 성능에 영향을 미친다.[1]

캐시의 히트율은 검색된 항목이 얼마나 자주 발견되는지를 나타낸다. 더 효율적인 교체 전략은 더 많은 사용 정보를 추적하여 주어진 캐시 크기에서 히트율을 높인다. 캐시의 레이턴시는 원하는 항목을 요청한 후 히트가 발생했을 때 캐시가 해당 항목을 반환할 수 있을 때까지 걸리는 시간을 설명한다. 빠른 교체 전략은 일반적으로 정보를 업데이트하는 데 필요한 시간을 줄이기 위해 사용 정보를 덜 추적하거나, 직접 매핑 캐시의 경우 정보를 전혀 추적하지 않는다. 각 교체 전략은 히트율과 레이턴시 사이의 절충안이다.

히트율 측정은 일반적으로 벤치마크 애플리케이션에서 수행되며, 히트율은 애플리케이션에 따라 달라진다. 비디오 및 오디오 스트리밍 애플리케이션은 스트림의 각 데이터 비트가 한 번 읽히고(강제 미스), 사용된 후 다시 읽거나 쓰지 않기 때문에 히트율이 0에 가까운 경우가 많다. 많은 캐시 알고리즘(특히 LRU)은 스트리밍 데이터가 캐시를 채우도록 허용하여 곧 다시 사용될 정보를 밀어낸다(캐시 오염).[2] 다른 요인으로는 크기, 획득 시간, 만료 등이 있을 수 있다. 캐시 크기에 따라 항목을 폐기하기 위한 추가적인 캐싱 알고리즘이 필요하지 않을 수도 있다. 알고리즘은 또한 여러 데이터베이스 서버가 공유 데이터 파일을 업데이트하는 경우와 같이 동일한 데이터에 대해 여러 캐시가 사용될 때 캐시 일관성을 유지한다.

정책

[편집]

벨레이디의 알고리즘

[편집]

가장 효율적인 캐싱 알고리즘은 가장 오랜 시간 동안 필요하지 않을 정보를 폐기하는 것이다. 이는 벨레이디의 최적 알고리즘, 최적 교체 정책 또는 선견지명 알고리즘으로 알려져 있다. 미래에 정보가 얼마나 멀리 필요할지 예측하는 것은 일반적으로 불가능하므로 이는 실무에서 실행 불가능하다. 실질적인 최소값은 실험 후에 계산할 수 있으며, 선택된 캐시 알고리즘의 효과를 비교하는 데 사용할 수 있다.

벨레이디 알고리즘의 차트

페이지 부재가 발생하면 페이지 세트가 메모리에 있게 된다. 예시에서 5, 0, 1의 시퀀스는 각각 프레임 1, 프레임 2, 프레임 3에 의해 액세스된다. 2가 액세스될 때, 값 5가 가까운 미래에 액세스되지 않을 것으로 예측하여 값 5(프레임 1에 있음)를 교체한다. 범용 운영체제는 5가 언제 액세스될지 예측할 수 없으므로, 벨레이디의 알고리즘은 거기서 구현될 수 없다.

무작위 교체 (RR)

[편집]

무작위 교체는 항목을 선택하여 필요할 때 공간을 만들기 위해 폐기한다. 이 알고리즘은 액세스 기록을 보관할 필요가 없다. 단순함 덕분에 ARM 프로세서에서 사용되었으며,[3] 효율적인 추계학적 시뮬레이션을 가능하게 한다.[4]

단순 큐 기반 정책

[편집]

선입 선출 (FIFO)

[편집]

이 알고리즘을 사용하면 캐시는 FIFO 큐처럼 동작한다. 이전에 얼마나 자주 또는 몇 번 액세스되었는지에 관계없이 추가된 순서대로 블록을 축출한다.

후입 선출 (LIFO) 또는 선입 후출 (FILO)

[편집]

캐시는 FIFO 큐와 달리 스택처럼 동작한다. 이전에 얼마나 자주 또는 몇 번 액세스되었는지에 관계없이 가장 최근에 추가된 블록을 먼저 축출한다.

SIEVE

[편집]

SIEVE는 키-값 캐시 및 콘텐츠 전송 네트워크와 같은 웹 캐시를 위해 특별히 설계된 단순 축출 알고리즘이다. 이는 지연 승급(lazy promotion)과 빠른 강등(quick demotion)의 아이디어를 사용한다.[5] 따라서 SIEVE는 캐시 히트 시 전역 자료 구조를 업데이트하지 않고 축출 시점까지 업데이트를 지연시킨다. 한편, 캐시 워크로드는 높은 단일 히트 비율(one-hit-wonder ratios)을 보이는 경향이 있고 대부분의 새로운 객체는 캐시에 보관할 가치가 없기 때문에 새로 삽입된 객체를 빠르게 축출한다. SIEVE는 단일 FIFO 큐를 사용하며 이동하는 핸들(hand)을 사용하여 축출할 객체를 선택한다. 캐시의 객체에는 객체가 캐시에 수용된 후 요청되었는지 여부를 나타내는 1비트의 메타데이터가 있다. 축출 핸들은 처음에 큐의 꼬리를 가리키고 시간이 지남에 따라 머리 쪽으로 이동한다. CLOCK 축출 알고리즘과 비교하여 SIEVE에서 유지된 객체는 원래 위치에 머문다. 따라서 새로운 객체는 항상 머리에 있고, 오래된 객체는 항상 꼬리에 있다. 핸들이 머리 쪽으로 이동함에 따라 새로운 객체는 빠르게 축출된다(빠른 강등).[6]

단순 최신성 기반 정책

[편집]

최근 최소 사용 (LRU)

[편집]

가장 최근에 사용되지 않은 항목을 먼저 폐기한다. 이 알고리즘은 무엇이 언제 사용되었는지 추적해야 하므로 번거롭다. 캐시 라인에 대한 "나이 비트(age bits)"가 필요하며, 이 나이 비트를 기반으로 가장 최근에 사용되지 않은 캐시 라인을 추적한다. 캐시 라인이 사용되면 다른 캐시 라인의 나이가 변경된다. LRU는 캐싱 알고리즘의 한 제품군으로, 시어도어 존슨과 데니스 샤샤의 2Q[7]와 팻 오닐, 베티 오닐, 게르하르트 위쿰의 LRU/K를 포함한다.[8] 예시의 액세스 시퀀스는 A B C D E D F이다.

LRU 알고리즘의 그래픽 예시

A B C D가 시퀀스 번호(새 액세스마다 1씩 증가)가 있는 블록에 설치되어 있고 E가 액세스되면, 이는 미스이며 블록에 설치되어야 한다. LRU 알고리즘을 사용하면 A가 가장 낮은 순위(A(0))를 가지므로 E가 A를 대체한다. 마지막에서 두 번째 단계에서 D가 액세스되고 시퀀스 번호가 업데이트된다. 그런 다음 F가 액세스되어 가장 낮은 순위를 가졌던 B – 를 대체한다(B(1)).

시간 인식 LRU (TLRU)

[편집]

시간 인식 LRU(TLRU)[9]는 캐시의 내용에 유효 수명이 있는 경우를 위해 설계된 LRU의 변형이다. 이 알고리즘은 정보 중심 네트워킹(ICN), 콘텐츠 전송 네트워크(CDN) 및 일반적인 분산 네트워크와 같은 네트워크 캐시 애플리케이션에 적합하다. TLRU는 TTU(Time To Use)라는 용어를 도입하는데, 이는 해당 지역성 및 콘텐츠 게시자를 기반으로 콘텐츠의 사용 가능 시간을 규정하는 콘텐츠(또는 페이지)의 타임스탬프이다. TTU는 네트워크 스토리지를 규제하는 데 있어 로컬 관리자에게 더 많은 제어 권한을 제공한다.

TLRU 대상 콘텐츠가 도착하면 캐시 노드는 콘텐츠 게시자가 할당한 TTU를 기반으로 로컬 TTU를 계산한다. 로컬 TTU 값은 로컬에 정의된 함수로 계산된다. 로컬 TTU 값이 계산되면 캐시 노드 전체 콘텐츠의 하위 집합에 대해 콘텐츠 교체가 수행된다. TLRU는 인기가 없고 수명이 짧은 콘텐츠가 새로 들어오는 콘텐츠로 교체되도록 보장한다.

최근 최다 사용 (MRU)

[편집]

LRU와 달리 MRU는 가장 최근에 사용된 항목을 먼저 폐기한다. 제11회 VLDB 컨퍼런스에서 초우(Chou)와 드윗(DeWitt)은 다음과 같이 말했다. "파일이 [루프 순차] 참조 패턴으로 반복적으로 스캔될 때, MRU가 최고의 교체 알고리즘이다."[10] 제22회 VLDB 컨퍼런스에서 발표한 연구자들은 임의 접근 패턴과 대규모 자료 집합(순환 액세스 패턴으로도 알려짐)에 대한 반복적인 스캔의 경우, MRU 캐시 알고리즘이 오래된 데이터를 보유하려는 경향 덕분에 LRU보다 더 많은 히트를 기록한다고 언급했다.[11] MRU 알고리즘은 항목이 오래될수록 액세스될 가능성이 더 높은 상황에서 가장 유용하다. 예시의 액세스 시퀀스는 A B C D E C D B이다.

MRU 알고리즘의 다이어그램

공간이 있으므로 A B C D가 캐시에 배치된다. 다섯 번째 액세스(E)에서 D를 가졌던 블록은 이 블록이 가장 최근에 사용되었기 때문에 E로 교체된다. 다음 액세스(D)에서는 C가 D 직전에 액세스된 블록이었으므로 C가 교체된다.

세그먼트 LRU (SLRU)

[편집]

SLRU 캐시는 수습(probationary)과 보호(protected)라는 두 세그먼트로 나뉜다. 각 세그먼트의 라인은 가장 최근에 액세스된 것부터 가장 오래전에 액세스된 것 순으로 정렬된다. 미스된 데이터는 수습 세그먼트의 가장 최근 액세스 끝부분에 캐시에 추가된다. 히트는 상주하는 위치에서 제거되어 보호 세그먼트의 가장 최근 액세스 끝부분에 추가된다. 보호 세그먼트의 라인은 적어도 두 번 액세스된 것이다. 보호 세그먼트는 유한하며, 수습 세그먼트에서 보호 세그먼트로 라인이 이동하면 보호 세그먼트의 LRU 라인이 수습 세그먼트의 가장 최근 사용 끝부분으로 이동하게 되어, 이 라인이 교체되기 전에 다시 액세스될 기회를 한 번 더 제공한다. 보호 세그먼트의 크기 제한은 I/O 워크로드 패턴에 따라 달라지는 SLRU 파라미터이다. 캐시에서 데이터를 폐기해야 할 때는 수습 세그먼트의 LRU 끝부분에서 라인을 가져온다.[12]

LRU 근사 알고리즘

[편집]

LRU는 높은 연관도를 가진 캐시에서 비용이 많이 들 수 있다. 실제 하드웨어는 대개 낮은 하드웨어 비용으로 유사한 성능을 얻기 위해 근사 알고리즘을 사용한다.

의사 LRU (PLRU)
[편집]

높은 연관도(일반적으로 4-웨이 초과)를 가진 CPU 캐시의 경우, LRU의 구현 비용이 과도해진다. 많은 CPU 캐시에서 최근에 가장 적게 사용된 항목 중 하나를 거의 항상 폐기하는 알고리즘이면 충분하다. 많은 CPU 설계자는 작동하는 데 캐시 항목당 1비트만 필요한 PLRU 알고리즘을 선택한다. PLRU는 일반적으로 LRU보다 미스율은 약간 나쁘고, 레이턴시는 약간 좋으며, 전력을 약간 덜 사용하고 LRU보다 낮은 오버헤드를 갖는다.

비트는 최근에 덜 사용된 하위 트리를 가리키는 1비트 포인터의 이진 트리로 작동한다. 리프 노드까지 포인터 체인을 따라가면 교체 후보를 식별한다. 액세스가 발생하면 액세스된 웨이의 리프 노드에서 루트 노드까지의 체인에 있는 모든 포인터는 액세스된 경로를 포함하지 않는 하위 트리를 가리키도록 설정된다. 예시의 액세스 시퀀스는 A B C D E이다.

의사 LRU의 그래픽 예시

값(A와 같은)에 대한 액세스가 있고 캐시에 없는 경우, 메모리에서 로드되어 예시에서 화살표가 가리키는 블록에 배치된다. 해당 블록이 배치된 후 화살표는 반대 방향을 가리키도록 뒤집힌다. A, B, C, D가 배치되고, 캐시가 채워짐에 따라 E가 A를 대체하는데, 그곳이 화살표가 가리키던 곳이었기 때문이다. 그리고 A로 향하던 화살표들은 반대 방향(다음 캐시 미스 시 교체될 블록인 B)을 가리키도록 뒤집힌다.

Clock-Pro
[편집]

LRU 알고리즘은 높은 오버헤드 때문에 운영체제와 같은 컴퓨터 시스템의 임계 경로에서 구현될 수 없다. 대신 LRU의 근사인 Clock이 일반적으로 사용된다. Clock-Pro는 시스템에서 저비용 구현을 위한 LIRS의 근사치이다.[13] Clock-Pro는 기본적인 Clock 프레임워크를 유지하면서 세 가지 장점을 가진다. Clock의 단일 "핸들"과 달리 세 개의 "클록 핸들"을 가지며 데이터 액세스의 재사용 거리를 대략적으로 측정할 수 있다. LIRS와 마찬가지로 1회성 액세스 또는 낮은 국부성을 가진 데이터 항목을 빠르게 축출할 수 있다. Clock-Pro는 Clock만큼이나 복잡하며 저비용으로 구현하기 쉽다. 2017년 버전의 리눅스에 구현된 버퍼 캐시 교체 방식은 LRU와 Clock-Pro를 결합한 것이다.[14][15]

단순 빈도 기반 정책

[편집]

최소 빈도 사용 (LFU)

[편집]

LFU 알고리즘은 항목이 얼마나 자주 필요한지를 계산하며, 덜 사용되는 항목을 먼저 폐기한다. 이는 얼마나 최근인 대신 블록이 액세스된 횟수가 저장된다는 점을 제외하면 LRU와 유사하다. 액세스 시퀀스를 실행하는 동안 가장 적은 횟수로 사용된 블록이 캐시에서 제거된다.

최소 빈도 최근 사용 (LFRU)

[편집]

최소 빈도 최근 사용(LFRU)[16] 알고리즘은 LFU와 LRU의 이점을 결합한다. LFRU는 ICN, CDN 및 일반적인 분산 네트워크와 같은 네트워크 캐시 애플리케이션에 적합하다. LFRU에서 캐시는 권한 부여(privileged)와 권한 비부여(unprivileged)라는 두 개의 파티션으로 나뉜다. 권한 부여 파티션은 보호되며, 콘텐츠가 인기가 있으면 권한 부여 파티션으로 밀어 넣어진다. 권한 부여 파티션을 교체할 때 LFRU는 권한 비부여 파티션에서 콘텐츠를 축출하고, 권한 부여 파티션의 콘텐츠를 권한 비부여 파티션으로 밀어내며, 새 콘텐츠를 권한 부여 파티션에 삽입한다. 권한 부여 파티션에는 LRU가 사용되고 권한 비부여 파티션에는 근사 LFU(ALFU) 알고리즘이 사용된다.

동적 에이징 LFU (LFUDA)

[편집]

변형인 동적 에이징 LFU(LFUDA)는 인기 있는 객체 세트의 변화에 적응하기 위해 동적 에이징을 사용한다. 새 객체가 캐시에 추가되거나 기존 객체가 재참조될 때 참조 횟수에 캐시 에이징 팩터를 추가한다. LFUDA는 블록을 축출할 때 캐시 에이징을 축출된 객체의 키 값으로 설정하여 증가시키며, 캐시 에이징은 항상 캐시 내의 최소 키 값보다 작거나 같다.[17] 객체가 과거에 빈번하게 액세스되었으나 나중에 인기가 없어지면 캐시에 오랫동안 남아 있게 된다(새롭거나 덜 인기 있는 객체가 이를 교체하는 것을 방지함). 동적 에이징은 이러한 객체의 수를 줄여 교체 대상으로 만들며, LFUDA는 캐시가 작을 때 LFU로 인한 캐시 오염을 줄인다.

S3-FIFO

[편집]

이는 2023년에 설계된 새로운 축출 알고리즘이다. 대부분 LRU(최근 최소 사용)를 기반으로 구축된 기존 알고리즘과 달리, S3-FIFO는 단 세 개의 FIFO 큐만 사용한다. 캐시 공간의 10%를 차지하는 작은(small) 큐, 캐시 공간의 90%를 사용하는 메인(main) 큐, 그리고 객체 메타데이터만 저장하는 고스트(ghost) 큐이다. 작은 큐는 단일 히트 객체(짧은 시간 내에 한 번만 액세스되는 객체)를 걸러내는 데 사용되며, 메인 큐는 인기 있는 객체를 저장하고 재삽입을 사용하여 캐시에 유지한다. 고스트 큐는 작은 큐에서 축출된 잠재적으로 인기 있는 객체를 포착하는 데 사용된다. 객체는 먼저 작은 큐에 삽입된다(고스트 큐에서 발견되지 않은 경우이며, 발견된 경우에는 메인 큐에 삽입됨). 작은 큐에서 축출될 때 해당 객체가 요청된 적이 있으면 메인 큐에 재삽입되고, 그렇지 않으면 축출되며 메타데이터가 고스트 큐에서 추적된다.[18]

RRIP 스타일 정책

[편집]

RRIP 스타일 정책은 Hawkeye를 포함한 다른 캐시 교체 정책의 기초가 된다.[19]

재참조 간격 예측 (RRIP)

[편집]

RRIP[20]는 인텔에서 제안한 유연한 정책으로, 재사용되지 않은 오래된 캐시 라인을 축출할 수 있게 하면서 우수한 스캔 저항성을 제공하려 시도한다. 모든 캐시 라인은 해당 라인이 재사용될 것으로 예상되는 시점과 상관관계가 있어야 하는 예측 값인 RRPV(Re-Reference Prediction Value)를 갖는다. RRPV는 일반적으로 삽입 시 높게 설정된다. 라인이 곧 재사용되지 않으면 스캔(단 한 번만 사용되는 대량의 데이터)이 캐시를 채우는 것을 방지하기 위해 축출된다. 캐시 라인이 재사용되면 RRPV는 0으로 설정되어 해당 라인이 한 번 재사용되었고 다시 재사용될 가능성이 높음을 나타낸다.

캐시 미스 시, 가능한 최대 RRPV와 같은 RRPV를 가진 라인이 축출된다. 3비트 값의 경우 RRPV가 23 - 1 = 7인 라인이 축출된다. 해당 값을 가진 라인이 없으면 세트 내의 모든 RRPV가 하나라도 도달할 때까지 1씩 증가한다. 동점 처리 규칙이 필요하며, 보통 왼쪽의 첫 번째 라인이 선택된다. 이러한 증가는 오래된 라인이 적절하게 에이징되고 재사용되지 않을 경우 축출되도록 보장하기 위해 필요하다.

정적 RRIP (SRRIP)
[편집]

SRRIP는 maxRRPV의 RRPV 값으로 라인을 삽입한다. 방금 삽입된 라인은 캐시 미스 시 축출될 가능성이 가장 높다.

이봉 RRIP (BRRIP)
[편집]

SRRIP는 일반적으로 잘 작동하지만, 작업 집합이 캐시 크기보다 훨씬 커서 캐시 스래싱(thrashing)이 발생할 때 어려움을 겪는다. 이는 대부분의 경우 maxRRPV 값으로 라인을 삽입하고, 낮은 확률로 무작위로 maxRRPV - 1 값으로 라인을 삽입함으로써 해결된다. 이는 일부 라인이 캐시에 "달라붙게" 하여 스래싱을 방지하는 데 도움이 된다. 그러나 BRRIP는 스래싱이 발생하지 않는 액세스에서는 성능을 저하시킨다. SRRIP는 작업 집합이 캐시보다 작을 때 가장 잘 작동하고, BRRIP는 작업 집합이 캐시보다 클 때 가장 잘 작동한다.

동적 RRIP (DRRIP)
[편집]

DRRIP[20]은 세트 듀얼링(set dueling)[21]을 사용하여 SRRIP를 사용할지 BRRIP를 사용할지 선택한다. 몇 개의 세트(일반적으로 32개)를 SRRIP 사용 전용으로 지정하고 다른 몇 개를 BRRIP 사용 전용으로 지정한 다음, 세트 성능을 모니터링하는 정책 카운터를 사용하여 캐시의 나머지 부분에서 어떤 정책을 사용할지 결정한다.

벨레이디의 알고리즘 근사 정책

[편집]

벨레이디의 알고리즘은 최적의 캐시 교체 정책이지만, 가장 먼 미래에 재사용될 라인을 축출하기 위해 미래에 대한 지식이 필요하다. 과거 액세스 패턴으로부터 미래 재사용 거리를 예측하려는 여러 교체 정책이 제안되었으며,[22] 이를 통해 최적의 교체 정책을 근사화할 수 있다. 성능이 가장 좋은 캐시 교체 정책 중 일부는 벨레이디의 알고리즘을 모방하려고 시도한다.

Hawkeye

[편집]

Hawkeye[19]는 PC에 의한 과거 액세스를 사용하여 그것이 생성하는 액세스가 캐시 친화적(나중에 사용됨)인지 캐시 혐오적(나중에 사용되지 않음)인지를 예측함으로써 벨레이디의 알고리즘을 모방하려 시도한다. 이는 정렬되지 않은 다수의 캐시 세트를 샘플링하고, 길이의 기록을 사용하며 이러한 액세스에 대해 벨레이디의 알고리즘을 모방한다. 이를 통해 정책은 어떤 라인이 캐싱되어야 했고 어떤 라인이 그러지 말았어야 했는지를 결정하여, 명령어가 캐시 친화적인지 혐오적인지 예측할 수 있다. 이 데이터는 RRIP로 전달된다. 캐시 친화적 명령어의 액세스는 낮은 RRPV 값을 가지며(나중에 축출될 가능성), 캐시 혐오적 명령어의 액세스는 높은 RRPV 값을 갖는다(조기에 축출될 가능성). RRIP 백엔드가 축출 결정을 내린다. 샘플링된 캐시와 OPT 생성기가 삽입된 캐시 라인의 초기 RRPV 값을 설정한다. Hawkeye는 2017년 CRC2 캐시 챔피언십에서 우승했으며,[23] Harmony[24]는 프리페칭 성능을 개선한 Hawkeye의 확장 버전이다.

캡션 참조
Mockingjay 캐시 교체 정책의 블록 다이어그램

Mockingjay

[편집]

Mockingjay[25]는 여러 면에서 Hawkeye를 개선하려 시도한다. 이진 예측을 버리고 어떤 캐시 라인을 축출할지에 대해 더 세분화된 결정을 내릴 수 있게 하며, 더 많은 정보를 사용할 수 있을 때까지 어떤 캐시 라인을 축출할지에 대한 결정을 미룬다.

Mockingjay는 고유 액세스, 이를 생성한 PC 및 타임스탬프의 샘플링된 캐시를 유지한다. 샘플링된 캐시의 라인이 다시 액세스되면 시간 차이가 재사용 거리 예측기(RDP)로 전송된다. RDP는 시간차 학습을 사용하며,[26] 여기서 새로운 RDP 값은 이상치를 보상하기 위해 작은 수만큼 증가하거나 감소한다. 이 수는 로 계산된다. 값이 초기화되지 않은 경우 관찰된 재사용 거리가 직접 삽입된다. 샘플링된 캐시가 가득 차서 라인을 폐기해야 하는 경우, RDP는 해당 라인을 마지막으로 액세스한 PC가 스트리밍 액세스를 생성한다고 지시받는다.

액세스 또는 삽입 시, 이 라인에 대한 예상 재사용 시간(ETR)은 예측된 재사용 거리를 반영하도록 업데이트된다. 캐시 미스 시 ETR 값이 가장 높은 라인이 축출된다. Mockingjay는 최적의 벨레이디 알고리즘에 근접한 결과를 보여준다.

기계 학습 정책

[편집]

여러 정책이 어떤 라인을 축출할지 예측하기 위해 퍼셉트론, 마르코프 연쇄 또는 다른 유형의 기계 학습을 사용하려 시도했다.[27][28] 캐시 교체를 위해 학습 강화 알고리즘(Learning augmented algorithms)도 존재한다.[29][30]

기타 정책

[편집]

낮은 상호 참조 최신성 세트 (LIRS)

[편집]

LIRS는 LRU 및 다른 최신 교체 알고리즘보다 성능이 뛰어난 페이지 교체 알고리즘이다. 재사용 거리는 교체 결정을 내리기 위해 액세스된 페이지의 순위를 동적으로 매기는 메트릭이다.[31] LIRS는 최신성을 사용하여 상호 참조 최신성(IRR)을 평가함으로써 LRU의 한계를 해결하고 교체 결정을 내린다.

LIRS 알고리즘의 다이어그램

다이어그램에서 X는 특정 시간에 블록이 액세스됨을 나타낸다. 블록 A1이 시간 1에 액세스되면 최신성은 0이 된다. 이는 처음 액세스된 블록이며, A1이 시간 3에 다시 액세스될 것으로 예측하므로 IRR은 1이 된다. 시간 2에서 A4가 액세스되므로 최신성은 A4의 경우 0이 되고 A1의 경우 1이 된다. A4는 가장 최근에 액세스된 객체이며 IRR은 4가 된다. 시간 10에서 LIRS 알고리즘은 두 개의 세트를 갖는다: LIR 세트 = {A1, A2} 및 HIR 세트 = {A3, A4, A5}. 시간 10에서 A4에 액세스하여 미스가 발생하면, LIRS는 A2 대신 최신성이 더 큰 A5를 축출한다.

적응형 교체 캐시 (ARC)

[편집]

적응형 교체 캐시(ARC)는 결합된 결과를 개선하기 위해 LRU와 LFU 사이의 균형을 지속적으로 유지한다.[32] 최근에 축출된 캐시 항목에 대한 정보를 사용하여 보호 세그먼트와 수습 세그먼트의 크기를 조정함으로써 가용 캐시 공간을 최적으로 사용하도록 SLRU를 개선한다.[33]

적응형 교체 클록 (CAR)

[편집]

적응형 교체 클록(CAR)은 ARC와 Clock의 장점을 결합한다. CAR은 ARC에 필적하는 성능을 보여주며, LRU와 Clock보다 성능이 뛰어나다. ARC와 마찬가지로 CAR은 자체 조정되며 사용자가 지정한 파라미터가 필요하지 않다.

멀티 큐 (MQ)

[편집]

멀티 큐 교체(MQ) 알고리즘은 서버 버퍼 캐시와 같은 2단계 버퍼 캐시의 성능을 개선하기 위해 개발되었으며, 저우(Zhou), 필빈(Philbin), 리(Li)의 논문에서 소개되었다.[34] MQ 캐시는 m개의 LRU 큐를 포함한다: Q0, Q1, ..., Qm-1. m의 값은 해당 큐에 있는 모든 블록의 수명을 기반으로 한 계층 구조를 나타낸다.[35]

멀티 큐 교체 알고리즘의 다이어그램

Pannier

[편집]

Pannier[36]는 블록에 가변 액세스 패턴이 있는 컨테이너를 식별하는 컨테이너 기반 플래시 캐싱 메커니즘이다. Pannier는 컨테이너의 잔존 데이터에 비례하는 생존 시간을 기준으로 컨테이너 순위를 매기는 우선순위 큐 기반 생존 큐 구조를 갖는다.

정적 분석

[편집]

정적 분석은 어떤 액세스가 캐시 히트 또는 미스인지 결정하여 프로그램의 최악 실행 시간을 나타낸다.[37] LRU 캐시의 속성을 분석하는 한 가지 접근 방식은 캐시의 각 블록에 "나이"(가장 최근에 사용된 경우 0)를 부여하고 가능한 나이에 대한 간격을 계산하는 것이다.[38] 이 분석은 동일한 프로그램 지점이 미스 또는 히트를 초래하는 경로를 통해 액세스 가능한 경우를 구별하도록 정밀화될 수 있다.[39] 콤팩트한 이진 결정 다이어그램으로 표현되는 반사슬에 의해 캐시 상태 세트를 추상화함으로써 효율적인 분석을 얻을 수 있다.[40]

LRU 정적 분석은 의사 LRU 정책으로 확장되지 않는다. 계산 복잡도 이론에 따르면 의사 LRU 및 FIFO에 의해 제기된 정적 분석 문제는 LRU의 문제보다 더 높은 복잡도 종류에 속한다.[41][42]

각주

[편집]
  1. 1 2 Alan Jay Smith. "Design of CPU Cache Memories". Proc. IEEE TENCON, 1987.
  2. ↑ Paul V. Bolotoff. "Functional Principles of Cache Memory" 보관됨 14 3월 2012 - 웨이백 머신. 2007.
  3. ↑ ARM Cortex-R Series Programmer's Guide
  4. ↑ An Efficient Simulation Algorithm for Cache of Random Replacement Policy
  5. ↑ Yang, Juncheng; Qiu, Ziyue; Zhang, Yazhuo; Yue, Yao; Rashmi, K. V. (2023년 6월 22일). 〈FIFO can be Better than LRU: The Power of Lazy Promotion and Quick Demotion〉. 《Proceedings of the 19th Workshop on Hot Topics in Operating Systems》. HOTOS '23. New York, NY, USA: Association for Computing Machinery. 70–79쪽. doi:10.1145/3593856.3595887. ISBN 979-8-4007-0195-5.
  6. ↑ Zhang, Yazhuo; Yang, Juncheng; Yue, Yao; Vigfusson, Ymir; Rashmi, K. V. (2024). 《{SIEVE} is Simpler than {LRU}: an Efficient {Turn-Key} Eviction Algorithm for Web Caches》 (영어). 1229–1246쪽. ISBN 978-1-939133-39-7.
  7. ↑ Johnson, Theodore; Shasha, Dennis (1994년 9월 12일). 《2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm》 (PDF). 《Proceedings of the 20th International Conference on Very Large Data Bases》. VLDB '94 (San Francisco, CA: Morgan Kaufmann Publishers Inc.). 439–450쪽. ISBN 978-1-55860-153-6. S2CID 6259428.
  8. ↑ O'Neil, Elizabeth J.; O'Neil, Patrick E.; Weikum, Gerhard (1993). 〈The LRU-K page replacement algorithm for database disk buffering〉. 《Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93》. New York, NY, USA: ACM. 297–306쪽. CiteSeerX 10.1.1.102.8240. doi:10.1145/170035.170081. ISBN 978-0-89791-592-2. S2CID 207177617.
  9. ↑ Bilal, Muhammad 외 (2014). 〈Time Aware Least Recent Used (TLRU) cache management policy in ICN〉. 《16th International Conference on Advanced Communication Technology》. 528–532쪽. arXiv:1801.00390. Bibcode:2018arXiv180100390B. doi:10.1109/ICACT.2014.6779016. ISBN 978-89-968650-3-2. S2CID 830503.
  10. ↑ Hong-Tai Chou and David J. DeWitt. An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB, 1985.
  11. ↑ Shaul Dar, Michael J. Franklin, Björn Þór Jónsson, Divesh Srivastava, and Michael Tan. Semantic Data Caching and Replacement. VLDB, 1996.
  12. ↑ Ramakrishna Karedla, J. Spencer Love, and Bradley G. Wherry. Caching Strategies to Improve Disk System Performance. In 컴퓨터, 1994.
  13. ↑ Jiang, Song; Chen, Feng; Zhang, Xiaodong (2005). 《CLOCK-Pro: An Effective Improvement of the CLOCK Replacement》 (PDF). 《Proceedings of the Annual Conference on USENIX Annual Technical Conference》 (USENIX Association). 323–336쪽.
  14. ↑ “Linux Memory Management: Page Replacement Design.”. 2017년 12월 30일. 2020년 6월 30일에 확인함.
  15. ↑ Corbet, Jonathan (2005년 8월 16일). “A CLOCK-Pro page replacement implementation”. LWN.net. 2020년 6월 30일에 확인함.
  16. ↑ Bilal, Muhammad 외 (2017). 《A Cache Management Scheme for Efficient Content Eviction and Replication in Cache Networks》. 《IEEE Access》 5. 1692–1701쪽. arXiv:1702.04078. Bibcode:2017arXiv170204078B. doi:10.1109/ACCESS.2017.2669344. S2CID 14517299.
  17. ↑ Jayarekha, P.; Nair, T (2010). “An Adaptive Dynamic Replacement Approach for a Multicast-based Popularity Aware Prefix Cache Memory System”. arXiv:1001.4135 [cs.MM].
  18. ↑ Yang, Juncheng; Zhang, Yazhuo; Qiu, Ziyue; Yue, Yao; Vinayak, Rashmi (2023년 10월 23일). 〈FIFO queues are all you need for cache eviction〉. 《Proceedings of the 29th Symposium on Operating Systems Principles》. SOSP '23. New York, NY, USA: Association for Computing Machinery. 130–149쪽. doi:10.1145/3600006.3613147. ISBN 979-8-4007-0229-7.
  19. 1 2 Jain, Akanksha; Lin, Calvin (June 2016). 〈Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement〉. 《2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA)》. 78–89쪽. doi:10.1109/ISCA.2016.17. ISBN 978-1-4673-8947-1.
  20. 1 2 Jaleel, Aamer; Theobald, Kevin B.; Steely, Simon C.; Emer, Joel (2010년 6월 19일). 〈High performance cache replacement using re-reference interval prediction (RRIP)〉. 《Proceedings of the 37th annual international symposium on Computer architecture》. ISCA '10. New York, NY, USA: Association for Computing Machinery. 60–71쪽. doi:10.1145/1815961.1815971. ISBN 978-1-4503-0053-7. S2CID 856628.
  21. ↑ Qureshi, Moinuddin K.; Jaleel, Aamer; Patt, Yale N.; Steely, Simon C.; Emer, Joel (2007년 6월 9일). 《Adaptive insertion policies for high performance caching》. 《ACM SIGARCH Computer Architecture News》 35. 381–391쪽. doi:10.1145/1273440.1250709. ISSN 0163-5964.
  22. ↑ Keramidas, Georgios; Petoumenos, Pavlos; Kaxiras, Stefanos (2007). 〈Cache replacement based on reuse-distance prediction〉. 《2007 25th International Conference on Computer Design》. 245–250쪽. doi:10.1109/ICCD.2007.4601909. ISBN 978-1-4244-1257-0. S2CID 14260179.
  23. ↑ “THE 2ND CACHE REPLACEMENT CHAMPIONSHIP – Co-located with ISCA June 2017”. 《crc2.ece.tamu.edu》. 2022년 3월 24일에 확인함.
  24. ↑ Jain, Akanksha; Lin, Calvin (June 2018). 〈Rethinking Belady's Algorithm to Accommodate Prefetching〉. 《2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA)》. 110–123쪽. doi:10.1109/ISCA.2018.00020. ISBN 978-1-5386-5984-7. S2CID 5079813.
  25. ↑ Shah, Ishan; Jain, Akanksha; Lin, Calvin (April 2022). 《Effective Mimicry of Belady's MIN Policy》. 《HPCA》.
  26. ↑ Sutton, Richard S. (1988년 8월 1일). 《Learning to predict by the methods of temporal differences》 (영어). 《Machine Learning》 3. 9–44쪽. Bibcode:1988MLear...3....9S. doi:10.1007/BF00115009. ISSN 1573-0565. S2CID 207771194.
  27. ↑ Liu, Evan; Hashemi, Milad; Swersky, Kevin; Ranganathan, Parthasarathy; Ahn, Junwhan (2020년 11월 21일). 《An Imitation Learning Approach for Cache Replacement》 (영어). 《International Conference on Machine Learning》 (PMLR). 6237–6247쪽. arXiv:2006.16239.
  28. ↑ Jiménez, Daniel A.; Teran, Elvira (2017년 10월 14일). 〈Multiperspective reuse prediction〉. 《Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture》. New York, NY, USA: ACM. 436–448쪽. doi:10.1145/3123939.3123942. ISBN 9781450349529. S2CID 1811177.
  29. ↑ Lykouris, Thodoris; Vassilvitskii, Sergei (2021년 7월 7일). 《Competitive Caching with Machine Learned Advice》. 《Journal of the ACM》 68. 1–25쪽. arXiv:1802.05399. doi:10.1145/3447579. eISSN 1557-735X. ISSN 0004-5411. S2CID 3625405.
  30. ↑ Mitzenmacher, Michael; Vassilvitskii, Sergei (2020년 12월 31일). 〈Algorithms with Predictions〉. 《Beyond the Worst-Case Analysis of Algorithms》. Cambridge University Press. 646–662쪽. arXiv:2006.09123. doi:10.1017/9781108637435.037. ISBN 9781108637435.
  31. ↑ Jiang, Song; Zhang, Xiaodong (June 2002). 《LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance》 (PDF). 《ACM SIGMETRICS Performance Evaluation Review》 30 (Association for Computing Machinery). 31–42쪽. doi:10.1145/511399.511340. ISSN 0163-5999.
  32. ↑ Nimrod Megiddo and Dharmendra S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. FAST, 2003.
  33. ↑ “Some insight into the read cache of ZFS - or: The ARC - c0t0d0s0.org”. 2009년 2월 24일에 원본 문서에서 보존된 문서.
  34. ↑ Yuanyuan Zhou, James Philbin, and Kai Li. The Multi-Queue Replacement Algorithm for Second Level Buffer Caches. USENIX, 2002.
  35. ↑ Eduardo Pinheiro, Ricardo Bianchini, Energy conservation techniques for disk array-based servers, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
  36. ↑ Cheng Li, Philip Shilane, Fred Douglis and Grant Wallace. Pannier: A Container-based Flash Cache for Compound Objects. ACM/IFIP/USENIX Middleware, 2015.
  37. ↑ Christian Ferdinand; Reinhard Wilhelm (1999). 《Efficient and precise cache behavior prediction for real-time systems》. 《Real-Time Syst.》 17. 131–181쪽. Bibcode:1999RTSys..17..131F. doi:10.1023/A:1008186323068. S2CID 28282721.
  38. ↑ Christian Ferdinand; Florian Martin; Reinhard Wilhelm; Martin Alt (November 1999). 《Cache Behavior Prediction by Abstract Interpretation》. 《Science of Computer Programming》 35 (Springer). 163–189쪽. doi:10.1016/S0167-6423(99)00010-6.
  39. ↑ Valentin Touzeau; Claire Maïza; David Monniaux; Jan Reineke (2017). 〈Ascertaining Uncertainty for Efficient Exact Cache Analysis〉. 《Computer-aided verification (2)》. arXiv:1709.10008. doi:10.1007/978-3-319-63390-9_2.
  40. ↑ Valentin Touzeau; Claire Maïza; David Monniaux; Jan Reineke (2019). 《Fast and exact analysis for LRU caches》. 《Proc. {ACM} Program. Lang》 3. 54:1–54:29쪽. arXiv:1811.01670.
  41. ↑ David Monniaux; Valentin Touzeau (2019년 11월 11일). 《On the complexity of cache analysis for different replacement policies》. 《Journal of the ACM》 66 (Association for Computing Machinery). 1–22쪽. arXiv:1811.01740. doi:10.1145/3366018. S2CID 53219937.
  42. ↑ David Monniaux (2022년 5월 13일). 《The complexity gap in the static analysis of cache accesses grows if procedure calls are added》. 《Formal Methods in System Design》 59 (Springer Verlag). 1–20쪽. arXiv:2201.13056. doi:10.1007/s10703-022-00392-w. S2CID 246430884.

외부 링크

[편집]
원본 주소 "https://ko.wikipedia.org/w/index.php?title=캐시_교체_정책&oldid=41804434"