이번에 리뷰할 논문은 ‘Learning Forward Reuse Distance’. 저자는 Pengcheng Li, Yongbin Gu 로 2020년도 Arxiv jornal에 발표된 논문이다.
1 INTRODUCTION
Cache
캐시 적중률이 1% 증가하면 지연시간이 35% 감소하는 만큼 웹 서버에 자주 액세스하는 항목을 웹 cache에 캐시 하면 빠르게 접근할 수 있다.
좋은 성능의 캐시를 구현하기 위해서는 데이터의 지역성이 중요하다.
지역성 : Peter J. Denning은 지역성의 원리를 “프로그램이 주소 공간의 하위 집합에 대한 참조를 장기간 클러스터링 하는 경향” 이라고 정의, 즉 주소공간에 대한 참조가 발생할 때 해당 주소와 공간적, 시간적으로 관련이 있는 주소들이 이어서 참조되는것을 의미한다.
Reuse distance
reusedistance란 그림과 같이 특정 주소가 다시 참조될 때 까지의 거리를 의미한다.
Backward Reusedistance : 현재를 시점으로 이전에 참조되었던 동일 주소와의 거리
Forward Reusedistance : 현재를 시점으로 미래에 참조될 동일 주소와의 거리
Belady’s Optimal algorithm
belady’s optimal algorithm은 최적의 캐시 교체 정책이다. 캐시 교체가 발생할 때 캐시 안의 각 데이터들의 reusedistance를 확인하고 reusedistance가 가장 긴 (가장 늦게 참조될) 데이터를 교체 대상으로 정하는 알고리즘이다. 이론적으로는 최적의 알고리즘이지만, 캐시 안의 데이터들이 미래에 언제 참조될지를 알 수 없기 때문에 현실적으로는 구현이 불가능한 알고리즘이다.