Fast Priority Queues for Cached Memory

Sanders, Peter

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Fast Priority Queues for Cached Memory

MPS-Authors

/persons/resource/persons45344

Sanders, Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Sanders, P. (1999). Fast Priority Queues for Cached Memory. In M. T. Goodrich, & C. C. McGeoch (Eds.), Selected papers of the International Workshop on Algorithm Engineering and Experimentation (ALENEX-99) (pp. 312-327). Berlin: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-35C8-C

Abstract

The cache hierarchy prevalent in todays high performance processors has to be taken into account in order to design algorithms which perform well in practice. We advocates the approach to adapt external memory algorithms to this purpose. We exemplify this approach and the practical issues involved by engineering a fast priority queue suited to external memory and cached memory which is based on $k$-way merging. It improves previous external memory algorithms by constant factors crucial for transferring it to cached memory. Running in the cache hierarchy of a workstation the algorithm is up to $4.7$ times faster than an optimized binary heap implementation.