KIT | KIT-Bibliothek | Impressum | Datenschutz

Performance Evaluation of Priority Queues for Fine-Grained Parallel Tasks on GPUs

Baudis, Nikolai; Jacob, Florian; Andelfinger, Philipp

Abstract:
Graphics processing units (GPUs) are increasingly applied to accelerate tasks such as graph problems and discreteevent simulation that are characterized by irregularity, i.e., a strong dependence of the control flow and memory accesses on the input. The core data structure in many of these irregular tasks are priority queues that guide the progress of the computations and which can easily become the bottleneck of an application. To our knowledge, currently no systematic comparison of priority queue implementations on GPUs exists in the literature. We close this gap by a performance evaluation of GPU-based priority queue implementations for two applications: discrete-event simulation and parallel A* path searches on grids. We focus on scenarios requiring large numbers of priority queues holding up to a few thousand items each. We present performance measurements covering linear queue designs, implicit binary heaps, splay trees, and a GPU-specific proposal from the literature. The measurement results show that up to about 500 items per queue, circular buffers frequently outperform tree-based queues for the considered applications, particularly under a simple parallelization of individual item enqueue operations. ... mehr

Open Access Logo


Postprint §
DOI: 10.5445/IR/1000079038
Veröffentlicht am 14.01.2019
Originalveröffentlichung
DOI: 10.1109/MASCOTS.2017.15
Coverbild
Zugehörige Institution(en) am KIT Institut für Telematik (TM)
Publikationstyp Proceedingsbeitrag
Jahr 2017
Sprache Englisch
Identifikator ISBN: 978-1-5386-2764-8
urn:nbn:de:swb:90-790389
KITopen-ID: 1000079038
Erschienen in Proceedings of the 25th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), Banff, Canada, 20th - 22nd September 2017
Verlag IEEE, Piscataway (NJ)
Seiten 1-11
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page