Fast and scalable list ranking on the GPU

ABSTRACT

General purpose programming on the graphics processing units (GPGPU) has received a lot of attention in the parallel computing community as it promises to offer the highest performance per dollar. The GPUs have been used extensively on regular problems that can be easily parallelized. In this paper, we describe two implementations of List Ranking, a traditional irregular algorithm that is difficult to parallelize on such massively multi-threaded hardware. We first present an implementation of Wyllie's algorithm based on pointer jumping. This technique does not scale well to large lists due to the suboptimal work done. We then present a GPU-optimized, Recursive Helman-JaJa (RHJ) algorithm. Our RHJ implementation can rank a random list of 32 million elements in about a second and achieves a speedup of about 8-9 over a CPU implementation as well as a speedup of 3-4 over the best reported implementation on the Cell Broadband engine. We also discuss the practical issues relating to the implementation of irregular algorithms on massively multi-threaded architectures like that of the GPU. Regular or coalesced memory accesses pattern and balanced load are critical to achieve good performance on the GPU.

REFERENCES

• 1: R. J. Anderson , G. L. Miller, A simple randomized parallel algorithm for list-ranking, Information Processing Letters, v.33 n.5, p.269-273, January 1990 [doi>10.1016/0020-0190(90)90196-5]
• 2: David A. Bader , Guojing Cong , John Feo, On the Architectural Requirements for Efficient Execution of Graph Algorithms, Proceedings of the 2005 International Conference on Parallel Processing, p.547-556, June 14-17, 2005 [doi>10.1109/ICPP.2005.55]
• 3: D. A. Bader, V. Agarwal, and K. Madduri. On the Design and Analysis of Irregular Algorithms on the Cell Processor: A Case Study of List Ranking. In 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1--10. IEEE, 2007.
• 4: David A. Bader , Guojing Cong, A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs), Journal of Parallel and Distributed Computing, v.65 n.9, p.994-1006, September 2005 [doi>10.1016/j.jpdc.2005.03.011]
• 5: David A. Bader , Sukanya Sreshta , Nina R. Weisse-Bernstein, Evaluating Arithmetic Expressions Using Tree Contraction: A Fast and Scalable Parallel Implementation for Symmetric Multiprocessors (SMPs) (Extended Abstract), Proceedings of the 9th International Conference on High Performance Computing, p.63-78, December 18-21, 2002
• 6: Ian Buck, GPU computing with NVIDIA CUDA, ACM SIGGRAPH 2007 courses, August 05-09, 2007, San Diego, California [doi>10.1145/1281500.1281647]
• 7: Richard Cole , Uzi Vishkin, Faster optimal parallel prefix sums and list ranking, Information and Computation, v.81 n.3, p.334-352, June 1989 [doi>10.1016/0890-5401(89)90036-9]
• 8: Yuri Dotsenko , Naga K. Govindaraju , Peter-Pike Sloan , Charles Boyd , John Manferdelli, Fast scan algorithms on graphics processors, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece [doi>10.1145/1375527.1375559]
• 9: Naga K. Govindaraju , Dinesh Manocha, Cache-efficient numerical algorithms using graphics hardware, Parallel Computing, v.33 n.10-11, p.663-684, November, 2007 [doi>10.1016/j.parco.2007.09.006]
• 10: Naga K. Govindaraju , Scott Larsen , Jim Gray , Dinesh Manocha, A memory model for scientific algorithms on graphics processors, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188549]
• 11: M. Harris, J. Owens, S. Sengupta, Y. Zhang, and A. Davidson. CUDPP: CUDA Data Parallel Primitives Library. http://gpgpu.org/developer/cudpp.
• 12: David R. Helman , Joseph JáJá, Designing Practical Efficient Algorithms for Symmetric Multiprocessors, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.37-56, January 15-16, 1999
• 13: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 14: G. L. Miller and J. H. Reif. Parallel Tree Contraction and its Application. pages 478--489, Oct. 1985.
• 15: A. Munshi. OpenCL Specification V1.0. Technical report, Khronos OpenCL Working Group, 2008.
• 16: NVIDIA Corporation. CUDA: Compute Unified Device Architecture Programming Guide. Technical report, NVIDIA, 2007.
• 17: Margaret Reid-Miller, List ranking and list scan on the Cray C-90, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.104-113, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181049]
• 18: Shane Ryoo , Christopher I. Rodrigues , Sam S. Stone , Sara S. Baghsorkhi , Sain-Zee Ueng , John A. Stratton , Wen-mei W. Hwu, Program optimization space pruning for a multithreaded gpu, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, April 05-09, 2008, Boston, MA, USA [doi>10.1145/1356058.1356084]
• 19: Shubhabrata Sengupta , Mark Harris , Yao Zhang , John D. Owens, Scan primitives for GPU computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
• 20: J. Sibeyn. Minimizing Global Communication in Parallel List Ranking. In Euro-Par Parallel Processing, Lecture Notes in Computer Science, pages 894--902. Springer, 2003.
• 21: James Christopher Wyllie, The complexity of parallel computations, Cornell University, Ithaca, NY, 1979

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
gpgpu, irregular algorithm, list ranking, many-core, parallel algorithm