캐시 교체 정책 (Cache Replacement Policy)

캐시 교체 정책 (Cache Replacement Policy)

캐시가 가득 찼을 때 어떤 캐시 라인을 제거할지 결정하는 알고리즘

특징: 시간적/공간적 지역성 활용, 하드웨어 구현, 히트율에 직접 영향

LRU(Least Recently Used): 가장 오래 미사용 라인 교체, 시간 지역성 활용, Pseudo-LRU(N-1비트)로 근사

• •장점: OPT에 근접한 히트율, 단점: HW 복잡도, 스캔 공격에 취약(워킹셋 축출)

FIFO: 삽입 순서대로 교체, 순환 포인터로 구현 극히 단순

• •단점: 시간 지역성 무시, Belady의 모순 발생 가능(캐시 증가 시 미스율 증가)

LFU(Least Frequently Used): 참조 횟수 최소 라인 교체, Aging 문제(과거 Hot 블록 잔류)

Random: 무작위 교체, 구현 최소(LFSR), 병적 패턴 없음, ARM L2/L3에서 사용

RRIP: RRPV(2비트) 기반 재참조 간격 예측, 스캔 저항성 우수, DRRIP(워크로드 적응형)

성능 비교: 일반(LRU≈RRIP>FIFO>Random), 스캔(RRIP>LRU), Thrashing(Random≈FIFO>LRU)

적용 기준: L1(Pseudo-LRU/지연중시), L2/L3(RRIP 또는 Random/면적·전력 중시)

비교: LRU(시간지역성/스캔취약) vs FIFO(단순/Belady모순) vs LFU(빈도/Aging) vs Random(단순) vs RRIP(스캔내성/적응형)

연관: 캐시 메모리, 지역성, 페이지 교체, 히트율, 메모리 계층