A translation system for enabling data mining applications on GPUs

ABSTRACT

Modern GPUs offer much computing power at a very modest cost. Even though CUDA and other related recent developments are accelerating the use of GPUs for general purpose applications, several challenges still remain in programming the GPUs. Thus, it is clearly desirable to be able to program GPUs using a higher-level interface.

In this paper, we offer a solution that targets a specific class of applications, which are the data mining and scientific data analysis applications. Our work is driven by the observation that a common processing structure, that of generalized reductions, fits a large number of popular data mining algorithms. In our solution, the programmers simply need to specify the sequential reduction loop(s) with some additional information about the parameters. We use program analysis and code generation to map the applications to a GPU. Several additional optimizations are also performed by the system.

We have evaluated our system using three popular data mining applications, k-means clustering, EM clustering, and Principal Component Analysis (PCA). The main observations from our experiments are as follows. The speedup that each of these applications achieve over a sequential CPU version ranges between 20 and 50. The automatically generated version did not have any noticeable overheads compared to hand written codes. Finally, the optimizations performed in the system resulted in significant performance improvements.

REFERENCES

• 1: Vikram Adve , John Mellor-Crummey, Using integer sets for data-parallel program analysis and optimization, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.186-198, June 17-19, 1998, Montreal, Quebec, Canada
• 2: Rakesh Agrawal , John C. Shafer, Parallel Mining of Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.962-969, December 1996 [doi>10.1109/69.553164]
• 3: P. Anderson, D. Binkley, G. Rosay, and T. Teitelbaum. Flow Insensitive Points-To Sets. scam, 00:0081, 2001.
• 4: Sara Baghsorkhi, Melvin Lathara, and Wen mei Hwu. CUDA-lite: Reducing GPU Programming Complexity. In LCPC 2008, 2008.
• 5: Prithviraj Banerjee , John A. Chandy , Manish Gupta , Eugene W. Hodges IV , John G. Holm , Antonio Lain , Daniel J. Palermo , Shankar Ramaswamy , Ernesto Su, The Paradigm Compiler for Distributed-Memory Multicomputers, Computer, v.28 n.10, p.37-47, October 1995 [doi>10.1109/2.467577]
• 6: Muthu Manikandan Baskaran , Uday Bondhugula , Sriram Krishnamoorthy , J. Ramanujam , Atanas Rountev , P. Sadayappan, A compiler framework for optimization of affine loop nests for gpgpus, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece [doi>10.1145/1375527.1375562]
• 7: William Blume , Ramon Doallo , Rudolf Eigenmann , John Grout , Jay Hoeflinger , Thomas Lawrence , Jaejin Lee , David Padua , Yunheung Paek , Bill Pottenger , Lawrence Rauchwerger , Peng Tu, Parallel Programming with Polaris, Computer, v.29 n.12, p.78-82, December 1996 [doi>10.1109/2.546612]
• 8: Randal E. Bryant. Data-Intensive Supercomputing: The Case for DISC. Technical Report CMU-CS-07-128, School of Computer Science, Carnegie Mellon University, 2007.
• 9: I. Buck, T. Foley, D. Horn, J. Sugerman, K. Mike, and H. Pat. Brook for GPUs: Stream Computing on Graphics Hardware, 2004.
• 10: Benjamin Bustos, Oliver Deussen, Stefan Hiller, and Daniel Keim. A Graphics Hardware Accelerated Algorithm for Nearest Neighbor Search. In Vassil N. Alexandrov, Geert Dick van Albada, Peter M. A. Sloot, and Jack Dongarra, editors, Computational Science-ICCS 2006, volume 3994 of LNCS, pages 196--199. Springer, 2006.
• 11: Maria Charalambous, Pedro Trancoso, and Alexandros Stamatakis. Initial experiences porting a bioinformatics application to a graphics processor. In Panhellenic Conference on Informatics, pages 415--425, 2005.
• 12: Shuai Che, Jiayuan Meng, and Jeremy W. Sheaffer. A Performance Study of General Purpose Applications on Graphics Processors.
• 13: Peter Cheeseman , John Stutz, Bayesian classification (AutoClass): theory and results, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 14: Matthias Christen, Olaf Schenk, and Helmar Burkhart. General-Purpose Sparse Matrix Building Blocks using the NVIDIA CUDA Technology Platform. In First Workshop on General Purpose Processing on Graphics Processing Units, Oct 2007.
• 15: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 16: Arthur Dempster, Nan Laird, and Donald Rubin. Maximum Likelihood Estimation from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society, 39(1):1--38, 1977.
• 17: Zhe Fan , Feng Qiu , Arie Kaufman , Suzanne Yoakum-Stover, GPU Cluster for High Performance Computing, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.47, November 06-12, 2004 [doi>10.1109/SC.2004.26]
• 18: Vincent Garcia, Eric Debreuve, and Michel Barlaud. Fast k Nearest Neighbor Search using GPU, 2008.
• 19: Naga Govindaraju , Jim Gray , Ritesh Kumar , Dinesh Manocha, GPUTeraSort: high performance graphics co-processor sorting for large database management, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142511]
• 20: Manish Gupta , Edith Schonberg, Static analysis to reduce synchronization costs in data-parallel programs, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237799]
• 21: Jesse D. Hall and John C. Hart. GPU Acceleration of Iterative Clustering. Jun 2004.
• 22: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 23: Hwansoo Han , Chau-Wen Tseng, Improving Compiler and Run-Time Support for Irregular Reductions Using Local Writes, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.181-196, August 07-09, 1998
• 24: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 25: Bingsheng He , Wenbin Fang , Qiong Luo , Naga K. Govindaraju , Tuyong Wang, Mars: a MapReduce framework on graphics processors, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454152]
• 26: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 27: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 28: R. Jin and G. Agrawal. Shared memory parallelization of data mining algorithms: Techniques. citeseer.ist.psu.edu/article/jin02shared.html, 2002.
• 29: Ruoming Jin and Gagan Agrawal. A Middleware for Developing Parallel Data Mining Implementations. In Proceedings of the first SIAM conference on Data Mining, April 2001.
• 30: Andreas Klockner. PyCuda, 2008.
• 31: C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991 [doi>10.1109/71.97901]
• 32: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 33: Seyong Lee , Seung-Jai Min , Rudolf Eigenmann, OpenMP to GPGPU: a compiler framework for automatic translation and optimization, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 34: Shih-Wei Liao. Parallelizing user-defined and implicit reductions globally on multiprocessors. In Chris R. Jesshope and Colin Egan, editors, Asia-Pacific Computer Systems Architecture Conference, volume 4186 of Lecture Notes in Computer Science, pages 189--202. Springer, 2006.
• 35: Yuan Lin , David A. Padua, On the Automatic Parallelization of Sparse and Irregular Fortran Programs, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.41-56, May 28-30, 1998
• 36: Compiler Optimization of Implicit Reductions for Distributed Memory Multiprocessors, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.42, March 30-April 03, 1998
• 37: Sreerama K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey, Data Mining and Knowledge Discovery, v.2 n.4, p.345-389, December 1998 [doi>10.1023/A:1009744630224]
• 38: NVidia. NVIDIA CUDA Compute Unified Device Architecture Programming Guide. version 2.0. http://developer.download.nvidia.com/compute/cuda/2.0-Beta2/docs/Programming_Guide_2.0beta2.pdf, June 7 2008.
• 39: Carlos Ordonez , Paul Cereghini, SQLEM: fast clustering in SQL using the EM algorithm, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.559-570, May 15-18, 2000, Dallas, Texas, United States
• 40: Mark Peercy , Mark Segal , Derek Gerstmann, A performance-oriented data parallel virtual machine for GPUs, ACM SIGGRAPH 2006 Sketches, July 30-August 03, 2006, Boston, Massachusetts [doi>10.1145/1179849.1180079]
• 41: William M. Pottenger, The role of associativity and commutativity in the detection and transformation of loop-level parallelism, Proceedings of the 12th international conference on Supercomputing, p.188-195, July 1998, Melbourne, Australia [doi>10.1145/277830.277870]
• 42: Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 43: Erik Sintorn and Ulf Assarsson. Fast Parallel GPU-Sorting Using a Hybrid Algorithm. In First Workshop on General Purpose Processing on Graphics Processing Units, Oct 2007.
• 44: John Stratton, Sam Stone, and Wen mei Hwu. MCUDA: An Efficient Implementation of CUDA Kernels for Multi-Core CPUs. In 21st Annual Workshop on Languages and Compilers for Parallel Computing (LCPC'2008), July 2008.
• 45: David Tarditi , Sidd Puri , Jose Oglesby, Accelerator: using data parallelism to program GPUs for general-purpose uses, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 46: Pedro Trancoso , Maria Charalambous, Exploring Graphics Processor Performance for General Purpose Applications, Proceedings of the 8th Euromicro Conference on Digital System Design, p.306-313, August 30-September 03, 2005 [doi>10.1109/DSD.2005.40]
• 47: Neil Trevett. OpenCL: The Open Standdard for Heterogeneous Parallel Programming, 2008.
• 48: Hao Yu , Lawrence Rauchwerger, Adaptive reduction parallelization techniques, Proceedings of the 14th international conference on Supercomputing, p.66-77, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335238]
• 49: Hans P. Zima and Barbara Mary Chapman. Compiling for Distributed-Memory Systems. Proceedings of the IEEE, 81(2):264--287, February 1993. In Special Section on Languages and Compilers for Parallel Machines.

INDEX TERMS

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

General Terms:
Design

Keywords:
cuda, data mining, gpgpu