hide
Free keywords:
-
Abstract:
The cache hierarchy prevalent in todays high performance processors
has to be taken into account in order to design algorithms that
perform well in practice. This paper advocates the adaption of
external memory algorithms to this purpose. This idea and the
practical issues involved are exemplified by engineering a fast
priority queue suited to external memory and cached memory that 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 at least two times faster than an optimized implementation of
binary heaps and 4-ary heaps for large inputs.
