ScaleOPT: A Scalable Optimal Page Replacement Policy Simulator

This paper proposes ScaleOPT, a scalable optimal page replacement policy (OPT) simulator by leveraging multi-core parallelism. Specifically, we first propose AccessMap which enables calculating the next reference time of the accessed page in a constant time by collecting the future references of pages in parallel before the OPT simulation. Second, we introduce Pipelined-Tree consisting of multiple trees which organize caches based on min-max reference times. It enables traverse and update operations of each cache to be performed in a partially parallel manner (i.e., pipelined), thereby scaling out the OPT simulation on multi-cores. The experimental results demonstrate that ScaleOPT improves the simulation time on a 72-core machine by 6.3×, 20.5×, and 13.9× compared with the long-established standard algorithm-based simulator along with our AccessMap, and two widely-used cache simulators, respectively.