We present a priority queue implementation with support for external memory. The focus of our work has been to derive a benefit from parallel shared-memory machines. It’s the first parallel optimization of an external-memory priority queue. An additional bulk insertion interface accelerates longer sequences of homogeneous operations, as they are more likely to occur in applications that process large amounts of data. The algorithm will be available as an extension to the Stxxl [6], a popular C++ template library for extra large data sets. Experiments have shown great improvements over the current external-memory priority queue of the Stxxl for homogeneous bulk operations. However, the high overhead for spawning threads, as well as the need for cache synchronization in the global ExtractMin operation, show the inherent limitations of the parallelizability of priority queues.

Wir präsentieren eine Priority Queue mit Unterstützung für externen Speicher. Besonderes Augenmerk wurde darauf gelegt, Vorteile aus parallelen Rechnerarchitekturen mit gemeinsamem Speicher zu ziehen. Es ist die erste parallele Optimierung einer Priority Queue für externen Speicher. Eine zusätzliche Schnittstelle zum blockweisen Einfügen beschleunigt längere Sequenzen von gleichartigen Operationen, wie sie besonders bei Anwendungen auftreten, die große Datenmengen verarbeiten. Der Algorithmus wird als Erweiterung zur Stxxl [6] verfügbar sein, einer bekannten C++-Templatebibliothek für sehr große Datenmengen. Für homogene, blockweise Operationen ergibt sich eine deutliche Verbesserung gegenüber der aktuellen Stxxl Priority Queue für externen Speicher. Die hohen Fixkosten bei der Threaderzeugung, sowie der hohe Aufwand für Cache-Synchronisierung bei der globalen ExtractMin-Operation, zeigen jedoch die inhärenten Grenzen der Parallelisierbarkeit von Priority Queues auf.