Efficient Cache Simulation under Optimal Replacement on Large-Scale Traces

Abstract

As the memory footprint of modern software continues to grow, efficient memory management is essential. Accordingly, studies on memory management policies are being actively conducted. To verify the policies and find the upper-bound performance of them, most studies use optimal replacement algorithm (OPT). Unfortunately, the existing well-known scheme of simulating OPT takes a lot of time, especially, when the trace size is large. Thus, it cannot calculate the hit ratio of the huge traces in a reasonable time. In this paper, we propose high-performance OPT simulation techniques to reduce the time complexity and execution time of large-scale trace-driven simulation. To do this, first, we devised a data structure consists of an array and queues called AccessMap which reads the trace and stores the reference times per page in ascending order. It allows calculating the reference time of the accessed page in a constant time. Second, we applied a min-max heap to organize a cache based on min-max reference times. The min-max heap enables searching for the page and selecting an eviction target page optimally in a constant time. Finally, we leverage a Link-Tree for simulating multiple cache sizes on a single run as the previous study can do. Our evaluation demonstrates that the proposed scheme reduces the simulation time by up to 5.4x in single-size cache simulation and up to 4.4x in multiple-size cache simulation than the existing stack algorithm based scheme.

현대 소프트웨어의 메모리 요구량이 점점 늘어남에 따라, 효율적인 메모리 관리를 위한 연구들이 활발히 이루어지고 있다. 최적 페이지 교체 알고리즘(이하 OPT)는 가장 나중에 참조되는 페이지를 교체하는 오프라인 알고리즘으로, 페이지 교체 정책에 대한 연구에서 상한 성능으로써 사용된다. 하지만 기존의 OPT 시뮬레이션 기법은 현대 소프트웨어의 대용량 메모리 트레이스를 합리적인 시간 안에 시뮬레이션하지 못하고 있다. 본 논문에서는 대용량 트레이스를 효율적으로 처리할 수 있는 새로운 시뮬레이션 기법을 제안한다. 기존 기법의 다음 참조 시간 계산의 시간 복잡도를 개선하기 위해, 배열과 큐로 구성된 AccessMap을 새롭게 적용한다. AccessMap의 각 큐에는 해당하는 페이지가 접근하는 시간이 오름차순으로 정리되어 다음 참조 시간을 상수 시간에 계산할 수 있도록 했다. 또한 최댓값과 최소값을 상수 시간에 수행할 수 있는 Min-Max 힙을 적용해, 페이지 검색과 교체할 페이지 선정에 걸리는 시간을 최적화한다. 마지막으로, 여러 캐시 크기에서의 적중률을 한 번의 실행으로 효율적으로 계산할 수 있는 Link-Tree를 새롭게 고안해 적용한다. 실험 결과, 제안한 기법은 기존 기법 대비 단일 크기의 캐시 시뮬레이션에서는 최대 약 5.4배 높은 처리량을 보였으며, 여러 크기의 캐시를 동시에 시뮬레이션 할 때는 최대 약 4.4배 높은 처리량을 보였다. 또한 트레이스의 크기가 커짐에 따라 더 높은 성능 향상을 확인할 수 있었다.