Parallel buffers for chip multiprocessors

ABSTRACT

Chip multiprocessors (CMPs) present new opportunities for improving database performance on large queries. Because CMPs often share execution, cache, or bandwidth resources among many hardware threads, implementing parallel database operators that efficiently share these resources is key to maximizing performance. A crucial aspect of this parallelism is managing concurrent, shared input and output to the parallel operators. In this paper we propose and evaluate a parallel buffer that enables intra-operator parallelism on CMPs by avoiding contention between hardware threads that need to concurrently read or write to the same buffer. The parallel buffer handles parallel input and output coordination as well as load balancing so individual operators do not need to reimplement that functionality.

REFERENCES

• 1: 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
• 2: P. A. Boncz, M. Zukowski, and N. Nes. Monetdb/x100: Hyper-pipelining query execution. In CIDR, pages 225--237, 2005.
• 3: John Cieslewicz , Jonathan Berry , Bruce Hendrickson , Kenneth A. Ross, Realizing parallelism in database operations: insights from a massively multithreaded architecture, Proceedings of the 2nd international workshop on Data management on new hardware, June 25-25, 2006, Chicago, Illinois [doi>10.1145/1140402.1140408]
• 4: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• 5: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 6: Philip Garcia , Henry F. Korth, Database hash-join algorithms on multithreaded computer architectures, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128055]
• 7: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 8: G. Graefe, Volcano— An Extensible and Parallel Query Evaluation System, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.120-135, February 1994 [doi>10.1109/69.273032]
• 9: Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: N. Hardavellas, I. Pandis, R. Johnson, N. Mancheril, A. Ailamaki, and B. Falsafi. Database servers on chip multiprocessors: Limitations and opportunities. In CIDR, pages 79--87, 2007.
• 11: J. L. Hennessy and D. A. Patterson. Computer Architecture. Morgan Kaufman, 4th edition, 2007.
• 12: Martin L. Kersten , Stefan Manegold , Peter A. Boncz , Niels Nes, Macro- and Micro-parallelism in a DBMS, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.6-15, August 28-31, 2001
• 13: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 14: E. Ladan-Mozes and N. Shavit. An optimistic approach to lock-free fifo queues. In DISC, pages 117--131, 2004.
• 15: Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248106]
• 16: Maged M. Michael , Michael L. Scott, Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors, Journal of Parallel and Distributed Computing, v.51 n.1, p.1-26, May 25, 1998 [doi>10.1006/jpdc.1998.1446]
• 17: Sriram Padmanabhan , Timothy Malkemus , Ramesh C. Agarwal , Anant Jhingran, Block Oriented Processing of Relational Database Operations in Modern Computer Architectures, Proceedings of the 17th International Conference on Data Engineering, p.567-574, April 02-06, 2001
• 18: Chien-Hua Shann , Ting-Lu Huang , Cheng Chen, A Practical Nonblocking Queue Algorithm Using Compare-and-Swap, Proceedings of the Seventh International Conference on Parallel and Distributed Systems (ICPADS'00), p.470, July 04-07, 2000
• 19: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 20: Jingren Zhou , John Cieslewicz , Kenneth A. Ross , Mihir Shah, Improving database performance on simultaneous multithreading processors, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 21: Jingren Zhou , Kenneth A. Ross, Buffering databse operations for enhanced instruction cache performance, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007592]