Date of Award
1-1-2022
Document Type
Thesis
Degree Name
M.S. in Engineering Science
First Advisor
Byunghyun Jang
Second Advisor
Philip J. Rhodes
Third Advisor
Feng Wang
School
University of Mississippi
Relational Format
dissertation/thesis
Abstract
Concurrent data structures play a critical role in the overall performance of GPGPU applications. Stack is one of the basic data structures and finds numerous applications where data is processed in a Last In First Out (LIFO) fashion. Although concurrent stack is well researched for multi-core CPUs, there is little research pointing to the conversion of CPU stacks into a GPU-friendly form. In this paper, we propose a concurrent search-based GPU stack named "Scan Stack." The proposed stack is designed to take advantage of GPU memory access patterns, memory coalescence, and thread structures (i.e., warps) to increase throughput. Our experiments on an NVIDIA RTX 3090 shows that our proposed scan stack significantly improves the throughput and scalability for all benchmarks when reducing the search area. However, the greatest improvements are shown when elimination is possible, and this improvement reaches nearly 39 times what a non-optimized structure is capable of.
Recommended Citation
South, Noah Brennen, "Scan Stack: A Search-based Concurrent Stack for GPU" (2022). Electronic Theses and Dissertations. 2459.
https://egrove.olemiss.edu/etd/2459
Concentration/Emphasis
Computer science