GPUTeraSort: high performance graphics co-processor sorting for large database management

ABSTRACT

We present a novel external sorting algorithm using graphics processors (GPUs) on large databases composed of billions of records and wide keys. Our algorithm uses the data parallelism within a GPU along with task parallelism by scheduling some of the memory-intensive and compute-intensive threads on the GPU. Our new sorting architecture provides multiple memory interfaces on the same PC -- a fast and dedicated memory interface on the GPU along with the main memory interface for CPU computations. As a result, we achieve higher memory bandwidth as compared to CPU-based algorithms running on commodity PCs. Our approach takes into account the limited communication bandwidth between the CPU and the GPU, and reduces the data communication between the two processors. Our algorithm also improves the performance of disk transfers and achieves close to peak I/O performance. We have tested the performance of our algorithm on the SortBenchmark and applied it to large databases composed of a few hundred Gigabytes of data. Our results on a 3 GHz Pentium IV PC with $300 NVIDIA 7800 GT GPU indicate a significant performance improvement over optimized CPU-based algorithms on high-end PCs with 3.6 GHz Dual Xeon processors. Our implementation is able to outperform the current high-end PennySort benchmark and results in a higher performance to price ratio. Overall, our results indicate that using a GPU as a co-processor can significantly improve the performance of sorting algorithms on large databases.

REFERENCES

• 1: Clearspeed technology. (http://www.clearspeed.com), 2005.
• 2: Ramesh C. Agarwal, A super scalar sort algorithm for RISC processors, ACM SIGMOD Record, v.25 n.2, p.240-246, June 1996
• 3: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 4: A. Ailamaki. Database architectures for new hardware. VLDB Tutorial Notes, 2004.
• 5: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , Marios Skounakis, Weaving Relations for Cache Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.169-180, September 11-14, 2001
• 6: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 7: A measure of transaction processing power, Datamation, v.31 n.7, p.112-118, March 15, 1985
• 8: Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau , David E. Culler , Joseph M. Hellerstein , David A. Patterson, High-performance sorting on networks of workstations, ACM SIGMOD Record, v.26 n.2, p.243-254, June 1997
• 9: N. Bandi, C. Sun, D. Agrawal, and A. El Abbadi. Hardware acceleration in commercial databases: A case study of spatial operations. VLDB, 2004.
• 10: K.E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computer Conference, 1968.
• 11: Bjørn Arild W. Baugstø , Jarle Fredrik Greipsland , J. Kamerbeek, Sorting Large Data Files on POOMA, Proceedings of the Joint International Conference on Vector and Parallel Processing, p.536-547, September 10-13, 1990
• 12: Peter A. Boncz , Stefan Manegold , Martin L. Kersten, Database Architecture Optimized for the New Bottleneck: Memory Access, Proceedings of the 25th International Conference on Very Large Data Bases, p.54-65, September 07-10, 1999
• 13: Introduction to algorithms, MIT Press, Cambridge, MA, 2001
• 14: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, Parallel sorting on a shared-nothing architecture using probabilistic splitting, Proceedings of the first international conference on Parallel and distributed information systems, p.280-291, December 1991, Miami, Florida, United States
• 15: A measure of transaction processing power, Datamation, v.31 n.7, p.112-118, March 15, 1985
• 16: Edward H. Friend, Sorting on Electronic Computer Systems, Journal of the ACM (JACM), v.3 n.3, p.134-168, July 1956 [doi>10.1145/320831.320833]
• 17: Phil Garcia, Multithreaded architectures and the sort benchmark, Proceedings of the 1st international workshop on Data management on new hardware, June 12-12, 2005, Baltimore, Maryland [doi>10.1145/1114252.1114254]
• 18: 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]
• 19: Naga K. Govindaraju , Dinesh Manocha, Efficient relational database management using graphics processors, Proceedings of the 1st international workshop on Data management on new hardware, June 12-12, 2005, Baltimore, Maryland [doi>10.1145/1114252.1114256]
• 20: 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]
• 21: Naga K. Govindaraju, Jim Gray, and Dinesh Manocha. Cache-efficient general purpose algorithms on GPUs. Technical report, Microsoft Research, December 2005.
• 22: Peter Kipfer , Mark Segal , Rüdiger Westermann, UberFlow: a GPU-based particle engine, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058146]
• 23: D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973.
• 24: Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
• 25: S. J. Smith , X. Li , G. Linoff , C. Stanfill , K. Thearling, A practical external sort for shared disk MPP's, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.666-675, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169815]
• 26: Stefan Manegold , Peter A. Boncz , Martin L. Kersten, What Happens During a Join? Dissecting CPU and Memory Optimization Effects, Proceedings of the 26th International Conference on Very Large Data Bases, p.339-350, September 10-14, 2000
• 27: Stefan Manegold, Peter A. Boncz, and Martin L. Kersten. Generic database cost models for hierarchical memory systems. In VLDB 2002: proceedings of the Twenty-Eighth International Conference on Very Large Data Bases, pages 191--202, 2002.
• 28: Shintaro Meki and Yahiko Kambayashi. Acceleration of relational database operations on vector processors. Systems and Computers in Japan, 31(8):79--88, August 2000.
• 29: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 30: Mark H. Nodine , Jeffrey Scott Vitter, Greed sort: optimal deterministic sorting on parallel disks, Journal of the ACM (JACM), v.42 n.4, p.919-933, July 1995 [doi>10.1145/210332.210343]
• 31: Nsort: Fast parallel sorting. http://www.ordinal.com/.
• 32: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a RISC machine sort, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.233-242, May 24-27, 1994, Minneapolis, Minnesota, United States
• 33: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a cache-sensitive parallel external sort, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.4, October 1995
• 34: J. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. Lefohn, and T. Purcell. A survey of general-purpose computation on graphics hardware. 2005.
• 35: 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
• 36: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• 37: Kenneth A. Ross, Conjunctive selection conditions in main memory, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543628]
• 38: Betty Salzberg , Alex Tsukerman , Jim Gray , Michael Stuewart , Susan Uren , Bonnie Vaughan, FastSort: a distributed single-input single-output external sort, ACM SIGMOD Record, v.19 n.2, p.94-101, Jun. 1990
• 39: Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton, Cache Conscious Algorithms for Relational Query Processing, Proceedings of the 20th International Conference on Very Large Data Bases, p.510-521, September 12-15, 1994
• 40: 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]
• 41: S. Venkatasubramanian. The graphics card as a stream computer. Workshop on Management and Processing of Data Streams, 2003.
• 42: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 43: J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory II: Hierarchical multilevel memories. Algorithmica, 12:148--169, 1994.
• 44: Marco Zagha , Guy E. Blelloch, Radix sort for vector multiprocessors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.712-721, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126164]
• 45: Jingren Zhou , Kenneth A. Ross, Implementing database operations using SIMD instructions, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564709]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Algorithms, Design, Experimentation, Management, Performance