Optimization of linked list prefix computations on multithreaded GPUs using CUDA

Zheng Wei, Joseph JaJa
Department of Electrical and Computer Engineering, Institute for Advanced Computer Studies, University of Maryland, College Park, U.S.A.
In 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS) (April 2010), pp. 1-8.


   title={Optimization of linked list prefix computations on multithreaded GPUs using CUDA},

   author={Wei, Z. and JaJa, J.},

   booktitle={Parallel & Distributed Processing (IPDPS), 2010 IEEE International Symposium on},






Download Download (PDF)   View View   Source Source   



We present a number of optimization techniques to compute prefix sums on linked lists and implement them on multithreaded GPUs using CUDA. Prefix computations on linked structures involve in general highly irregular fine grain memory accesses that are typical of many computations on linked lists, trees, and graphs. While the current generation of GPUs provides substantial computational power and extremely high bandwidth memory accesses, they may appear at first to be primarily geared toward streamed, highly data parallel computations. In this paper, we introduce an optimized multithreaded GPU algorithm for prefix computations through a randomization process that reduces the problem to a large number of fine-grain computations. We map these fine-grain computations onto multithreaded GPUs in such a way that the processing cost per element is shown to be close to the best possible. Our experimental results show scalability for list sizes ranging from 1M nodes to 256M nodes, and significantly improve on the recently published parallel implementations of list ranking, including implementations on the Cell Processor, the MTA-8, and the NVIDIA GeForce 200 series. They also compare favorably to the performance of the best known CUDA algorithm for the scan operation on the Tesla C1060.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: