Chen, Yanhao ; Hua, Fei ; Jin, Yuwei ; Zhang, Eddy Z BGPQ: A Heap-Based Priority Queue Design for GPUs Conference 50th International Conference on Parallel Processing (ICPP 2021), Association for Computing Machinery, New York, NY, USA, 2021, ISBN: 9781450390682. Abstract | Links | BibTeX | Tags: Batched Heap, GPUs, Priority Queue
2021
@conference{chen+:icpp21,
title = {BGPQ: A Heap-Based Priority Queue Design for GPUs},
author = {Chen, Yanhao and Hua, Fei and Jin, Yuwei and Zhang, Eddy Z.},
url = {https://doi.org/10.1145/3472456.3472463},
doi = {10.1145/3472456.3472463},
isbn = {9781450390682},
year = {2021},
date = {2021-08-09},
booktitle = {50th International Conference on Parallel Processing (ICPP 2021)},
pages = {10},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
abstract = {Programming today’s many-core processor is challenging. Due to the enormous amount of parallelism, synchronization is expensive. We need efficient data structures for providing automatic and scalable synchronization methods. In this paper, we focus on the priority queue data structure. We develop a heap-based priority queue implementation called BGPQ. BGPQ uses batched key nodes as the internal data representation, exploits both task parallelism and data parallelism, and is linearizable. We show that BGPQ achieves up to 88X speedup compared with four state-of-the-art CPU parallel priority queue implementations and up to 11.2X speedup over an existing GPU implementation. We also apply BGPQ to search problems, including 0-1 Knapsack and A* search. We achieve 45X-100X and 12X-46X speedup respectively over best known concurrent CPU priority queues.},
keywords = {Batched Heap, GPUs, Priority Queue},
pubstate = {published},
tppubtype = {conference}
}
Programming today’s many-core processor is challenging. Due to the enormous amount of parallelism, synchronization is expensive. We need efficient data structures for providing automatic and scalable synchronization methods. In this paper, we focus on the priority queue data structure. We develop a heap-based priority queue implementation called BGPQ. BGPQ uses batched key nodes as the internal data representation, exploits both task parallelism and data parallelism, and is linearizable. We show that BGPQ achieves up to 88X speedup compared with four state-of-the-art CPU parallel priority queue implementations and up to 11.2X speedup over an existing GPU implementation. We also apply BGPQ to search problems, including 0-1 Knapsack and A* search. We achieve 45X-100X and 12X-46X speedup respectively over best known concurrent CPU priority queues.
