Home
Resource
A model for concurrent priority queue on many-core architectures
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(804.03 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Huang, Chaozhang. A model for concurrent priority queue on many-core architectures. Retrieved from https://doi.org/doi:10.7282/t3-79sn-az74

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleA model for concurrent priority queue on many-core architectures
NameHuang, Chaozhang (author); Zhang, Zheng (chair); Zhang, Desheng (internal member); Zhang, Yongfeng (internal member); Rutgers University; School of Graduate Studies
Date Created2019
Other Date2019-10 (degree)
SubjectComputer Science, Concurrency, Graphics processing units -- Design, Computer multitasking
Extent1 online resource (v, 48 pages) : illustrations
DescriptionThe concurrent priority queue is one of the shared memory data structures that can be dynamically maintained and updated for communication among co-running threads, which allows data with high priority to be served before others in applications that require complex asynchronous communication patterns. For instance, the following algorithms can take advantages of a concurrent priority queue: Dijkstra’s shortest path algorithm, Prim’s minimal spanning tree algorithm, data compression and A* search in artificial intelligence, which are building blocks for complex system software including operating system scheduler, interruption handler, and garbage collection. However, it is challenging to exploit the performance of heap-based priority queue on many-core architectures like GPUs due to control divergence and memory irregularity. This thesis focuses on the development and evaluation of a model for concurrent priority queue on GPU. We present an efficient model for heap-based concurrent priority queue, called the generalized heap, which exploits both inter-node and intra-node parallelism by incorporating with multi-state locking mechanism and batch processing on data nodes. The performance of the concurrent priority queue based on the generalized heap model is thoroughly evaluated against previous serial and GPU implementations. We show a maximum of 19.49X and 2.11X speedup compared to previous serial and GPU implementation, respectively. We also apply our generalized heap model in real-world applications such as single-source shortest path and 0/1 knapsack problem with up to 1.23X and 12.19X speedup, respectively.
NoteM.S.
NoteIncludes bibliographical references
Genretheses, ETD graduate
Persistent URLhttps://doi.org/doi:10.7282/t3-79sn-az74
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024