The output of a cache under the independent reference model - Where did the locality of reference go?

Simple item page
dc.contributor.authorVanichpun, Saruten_US
dc.contributor.authorMakowski, Armand M.en_US
dc.contributor.departmentISRen_US
dc.contributor.departmentCSHCNen_US
dc.date.accessioned2007-05-23T10:14:55Z
dc.date.available2007-05-23T10:14:55Z
dc.date.issued2004en_US
dc.description.abstractWe consider a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). We characterize the popularity pmf of the stream of misses from the cache, the so-called output of the cache, for a large class of cache replacement policies, including standard on-demand replacement algorithms such as the policy A_0 and the random policy, as well as the LRU and CLIMB policies. We measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution. Using the notion of majorization to capture the degree of skewness, we show that for the policy A_0 and the random policy, the output always has less locality of reference than the input. However, we show by counterexamples that this is not always the case under the LRU and CLIMB policies when the input is selected according to a Zipf-like pmf. In that case, conjectures are offered (and supported by simulations) as to when LRU or CLIMB caching indeed reduces locality of reference. <p>en_US
dc.format.extent417625 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/6417
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 2004-11en_US
dc.relation.ispartofseriesCSHCN; TR 2004-7en_US
dc.subjectNext-Generation Product Realization Systemsen_US
dc.titleThe output of a cache under the independent reference model - Where did the locality of reference go?en_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_2004-11.pdf
Size:
407.84 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports