Data partitioning on chip multiprocessors

ABSTRACT

Partitioning is a key database task. In this paper we explore partitioning performance on a chip multiprocessor (CMP) that provides a relatively high degree of on-chip thread-level parallelism. It is therefore important to implement the partitioning algorithm to take advantage of the CMP's parallel execution resources. We identify the coordination of writing partition output as the main challenge in a parallel partitioning implementation and evaluate four techniques for enabling parallel partitioning. We confirm previous work in single threaded partitioning that finds L2 cache misses and translation lookaside buffer misses to be important performance issues, but we now add the management of concurrent threads to this analysis.

REFERENCES

• 1: John Cieslewicz , Kenneth A. Ross , Ioannis Giannakakis, Parallel buffers for chip multiprocessors, Proceedings of the 3rd international workshop on Data management on new hardware, June 15-15, 2007, Beijing, China [doi>10.1145/1363189.1363192]
• 2: John Cieslewicz , Kenneth A. Ross, Adaptive aggregation on chip multiprocessors, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 3: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 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 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
• 6: G. Graefe. Parallel external sorting in volcano. Technical Report CU-CS-459-90, University of Colorado, 1990.
• 7: J. L. Hennessy and D. A. Patterson. Computer Architecture. Morgan Kaufman, 4^th edition, 2007.
• 8: Stefan Manegold , Peter Boncz , Martin Kersten, Optimizing Main-Memory Join on Modern Hardware, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.709-730, July 2002 [doi>10.1109/TKDE.2002.1019210]
• 9: R. McDougall and J. Mauro. Solaris Internals, chapter 8--13. Prentice Hall, 2^nd edition, 2007.
• 10: 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
• 11: Sun Microsystems, Inc. OpenSPARC T1 microarchitecture specification, August 2006.
• 12: Sun Microsystems, Inc. UltraSPARC T1 supplement to the UltraSPARC architecture 2005, March 2006.

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)

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Experimentation, Performance