Thumbnail
Access Restriction
Subscribed

Author LaMarca, Anthony ♦ Ladner, Richard
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1996
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Abstract As memory access times grow larger relative to processor cycletimes, the cache performance of algorithms has an increasinglylarge impact on overall performance. Unfortunately, most commonlyused algorithms were not designed with cache performance in mind.This paper investigates the cache performance of implicit heaps. Wepresent optimizations which significantly reduce the cache missesthat heaps incur and improve their overall performance. We presentan analytical model called collective analysis that allows cacheperformance to be predicted as a function of both cacheconfiguration and algorithm configuration. As part of ourinvestigation, we perform an approximate analysis of the cacheperformance of both traditional heaps and our improved heaps in ourmodel. In addition empirical data is given for five architecturesto show the impact our optimizations have on overall performance.We also revisit a priority queue study originally performed byJones [25]. Due to the increases in cache miss penalties, therelative performance results we obtain on today's machines differgreatly from the machines of only ten years ago. We compare theperformance of implicit heaps, skew heaps and splay trees anddiscuss the difference between our results and Jones's.
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 1996-01-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 1


Open content in new tab

   Open content in new tab
Source: ACM Digital Library