Data parallel acceleration of decision support queries using Cell/BE and GPUs

ABSTRACT

Decision Support System (DSS) workloads are known to be one of the most time-consuming database workloads that processes large data sets. Traditionally, DSS queries have been accelerated using large-scale multiprocessor. The topic addressed in this work is to analyze the benefits of using high-performance/low-cost processors such as the GPUs and the Cell/BE to accelerate DSS query execution. In order to overcome the programming effort of developing code for different architectures, in this work we explore the use of a platform, Rapidmind, which offers the possibility of executing the same program on both Cell/BE and GPUs. To achieve this goal we propose data-parallel versions of the original database scan and join algorithms. In our experimental results we compare the execution of three queries from the standard DSS benchmark TPC-H on two systems with two different GPU models, a system with the Cell/BE processor, and a system with dual quad-core Xeon processors. The results show that parallelism can be well exploited by the GPUs. The speedup values observed were up to 21x compared to a single processor system.

REFERENCES

• 1: N. Bandi, C. Sun, D. Agrawal, and A. E. Abbadi. Hardware acceleration in commercial databases: A case study of spatial operations. Technical report, Computer Science Department, University of California, Santa Barbara, 2004.
• 2: Gianfranco Bilardi , Alexandru Nicolau, Adaptive bitonic sorting: an optimal parallel algorithm for shared-memory machines, SIAM Journal on Computing, v.18 n.2, p.216-228, April 1989 [doi>10.1137/0218014]
• 3: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 4: M. Charalambous, P. Trancoso, and A. Stamatakis. Initial Experiences Porting a Bioinformatics Application to a Graphics Processor. In Proceedings of the 10th Panhellenic Conference on Informatics(PCI 2005), pages 415--425, November 2005.
• 5: J. Cieslewicz and K. A. Ross. Database optimizations for modern hardware. Proceedings of the IEEE, 96(5):863--878, 2008.
• 6: Buǧra Gedik , Philip S. Yu , Rajesh R. Bordawekar, Executing stream joins on the cell processor, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 7: 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]
• 8: Naga K. Govindaraju , Brandon Lloyd , Wei Wang , Ming Lin , Dinesh Manocha, Fast computation of database operations using graphics processors, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007594]
• 9: N. K. Govindaraju, N. Raghuvanshi, M. Henson, and D. Manocha. A Cache-Efficient Sorting Algorithm for Database and Data Mining Computations using Graphics Processors. Technical report, UNC, 2005.
• 10: Naga K. Govindaraju , Nikunj Raghuvanshi , Dinesh Manocha, Fast and approximate stream mining of quantiles and frequencies using graphics processors, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066227]
• 11: A. Greb and G. Zachmann. GPU-ABiSort: Optimal parallel sorting on stream architectures. In Proceedings of the 20th IEEE IPDPS, 2006.
• 12: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 13: J. D. Hall and J. C. Hart. GPU Acceleration of Iterative Clustering. In Proceedings of the ACM Workshop on General Purpose Computing on Graphics Processors, August 2004.
• 14: T. Jansen, B. v. Rymon-Lipinski, N. Hanssen, and E. Keeve. Fourier volume rendering on the gpu using a split-stream fft. In Proceedings of Vision, Modelling and Visualization, 2004.
• 15: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 16: Jens Krüger , Rüdiger Westermann, Linear algebra operators for GPU implementation of numerical algorithms, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198795]
• 17: E. Scott Larsen , David McAllister, Fast matrix multiplies using graphics hardware, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.55-55, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582089]
• 18: Michael D. McCool , Zheng Qin , Tiberiu S. Popa, Shader metaprogramming, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 19: NVIDIA. NVIDIA CUDA Technology. http://developer.nvidia.com/object/cuda.html.
• 20: Ordinal. Nsort: Fast parallel sorting. http://www.ordinal.com/.
• 21: John Owens, Streaming architectures and technology trends, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198766]
• 22: Rapidmind. Writing Applications for the GPU Using the RapidMind Development Platform. http://www.rapidmind.net.
• 23: Rapidmind. Rapidmind Platform. http://www.rapidmind.net, 2007.
• 24: Harald Servat , Cecilia Gonzalez , Xavier Aguilar , Daniel Cabrera , Daniel Jimenez, Drug Design on the Cell BroadBand Engine, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.425, September 15-19, 2007 [doi>10.1109/PACT.2007.26]
• 25: Alexandros Stamatakis, An Efficient Program for Phylogenetic Inference Using Simulated Annealing, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 7, p.198.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.90]
• 26: Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Hardware acceleration for spatial selections and joins, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872813]
• 27: 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]
• 28: Transaction Processing Council. TPC Benchmark H (Decision Support) Standard Specification Revision 2.6.1. June 2006.
• 29: J. Wang, T.-T. Wong, P.-A. Heng, and C.-S. Leung. Discrete wavelet transform on gpu. http://www.cse.cuhk.edu.hk/ttwong/demo/dwtgpu/dwtgpu.htm
• 30: Samuel Williams , John Shalf , Leonid Oliker , Shoaib Kamil , Parry Husbands , Katherine Yelick, The potential of the cell processor for scientific computing, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128027]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

General Terms:
Algorithms, Performance

Keywords:
Cell/BE, GPU, data-parallel model, decision support system, performance evaluation, rapidmind