KIT | KIT-Bibliothek | Impressum | Datenschutz

Bulk-Parallel Priority Queue in External Memory

Keh, Thomas

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, 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.

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000042468
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2014
Sprache Englisch
Identifikator urn:nbn:de:swb:90-424687
KITopen-ID: 1000042468
Art der Arbeit Abschlussarbeit - Bachelor
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page