Access Restriction

Author Moruz, Gabriel ♦ Negoescu, Andrei ♦ Neumann, Christian ♦ Weichert, Volker
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Paging ♦ Algorithm engineering
Abstract In the field of online algorithms, paging is a well-studied problem. LRU is a simple paging algorithm that incurs few cache misses and supports efficient implementations. Algorithms outperforming LRU in terms of cache misses exist but are in general more complex and thus not automatically better, since their increased runtime might annihilate the gains in cache misses. In this article, we focus on efficient implementations for the OnOPT class described in Moruz and Negoescu [2012], particularly on an algorithm in this class, denoted RDM, that was shown to typically incur fewer misses than LRU. We provide experimental evidence on a wide range of cache traces showing that our implementation of RDM is competitive to LRU with respect to runtime. In a scenario incurring realistic time penalties for cache misses, we show that our implementation consistently outperforms LRU, even if the runtime of LRU is set to zero.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-01-07
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 19
Page Count 19
Starting Page 1
Ending Page 19

Open content in new tab

   Open content in new tab
Source: ACM Digital Library