Asynchronous parallel disk sorting

ABSTRACT

We develop an algorithm for parallel disk sorting, whose I/O cost approaches the lower bound and that guarantees almost perfect overlap between I/O and computation. Previous algorithms have either suboptimal I/O volume or cannot guarantee that I/O and computations can always be overlapped. We give an efficient implementation that can (at least) compete with the best practical implementations but gives additional performance guarantees. For the experiments we have configured a state of the art machine that can sustain full bandwidth I/O with eight disks and is very cost effective.

REFERENCES

• 1: Ramesh C. Agarwal, A super scalar sort algorithm for RISC processors, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.240-246, June 04-06, 1996, Montreal, Quebec, Canada
• 2: A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems.
• 3: Susanne Albers , Naveen Garg , Stefano Leonardi, Minimizing stall time in single and parallel disk systems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.454-462, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276858]
• 4: Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter, Implementing I/O-efficient Data Structures Using TPIE, Proceedings of the 10th Annual European Symposium on Algorithms, p.88-100, September 17-21, 2002
• 5: Rakesh D. Barve , Edward F. Grove , Jeffrey Scott Vitter, Simple randomized mergesort on parallel disks, Parallel Computing, v.23 n.4-5, p.601-631, June 1, 1997 [doi>10.1016/S0167-8191(97)00015-X]
• 6: Rakesh D. Barve , Jeffrey Scott Vitter, A simple and efficient parallel disk mergesort, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.232-241, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305646]
• 7: Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.311-343, Nov. 1996 [doi>10.1145/235543.235544]
• 8: Geeta Chaudhry , Thomas H. Cormen, Getting More from Out-of-Core Columnsort, Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments, p.143-154, January 04-05, 2002
• 9: Geeta Chaudhry , Thomas H. Cormen , Leonard F. Wisniewski, Columnsort lives! an efficient out-of-core sorting program, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.169-178, July 2001, Crete Island, Greece [doi>10.1145/378580.378627]
• 10: A. Crauser and K. Mehlhorn. LEDA-SM a platform for secondary memory computations. Technical report, MPII, 2000. draft.
• 11: R. Dementiev and P. Sanders. Asynchronous parallel disk sorting. Technical Report MPI-I-2003-1-001, MPI Informatik, Germany, 2003.
• 12: David A. Hutchinson , Peter Sanders , Jeffrey Scott Vitter, Duality between Prefetching and Queued Writing with Parallel Disks, Proceedings of the 9th Annual European Symposium on Algorithms, p.62-73, August 28-31, 2001
• 13: Mahesh Kallahalla , Peter J. Varman, Optimal prefetching and caching for parallel I/O sytems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.219-228, July 2001, Crete Island, Greece [doi>10.1145/378580.378648]
• 14: Tracy Kimbrel , Anna R. Karlin, Near-Optimal Parallel Prefetching and Caching, SIAM Journal on Computing, v.29 n.4, p.1051-1082, Feb. 2000 to March 2000 [doi>10.1137/S0097539797326976]
• 15: 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
• 16: Per-Åke Larson , Goetz Graefe, Memory management during run generation in external sorting, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.472-483, June 01-04, 1998, Seattle, Washington, United States
• 17: Mark H. Nodine , Jeffrey Scott Vitter, Deterministic distribution sort in shared and distributed memory multiprocessors, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.120-129, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165247]
• 18: 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]
• 19: 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
• 20: C. Nyberg, C. Koester, and J. Gray. Nsort: A parallel sorting program for NUMA and SMP machines, 2000. http://www.ordinal.com/lit.html.
• 21: Vinay S. Pai , Peter J. Varman, Prefetching with Multiple Disks for External Mergesort: Simulation and Analysis, Proceedings of the Eighth International Conference on Data Engineering, p.273-282, February 03-07, 1992
• 22: Sanguthevar Rajasekaran, A framework for simple sorting algorithms on parallel disk systems (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.88-97, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277675]
• 23: Peter Sanders, Fast priority queues for cached memory, Journal of Experimental Algorithmics (JEA), 5, p.7-es, 2000 [doi>10.1145/351827.384249]
• 24: Peter Sanders , Sebastian Egner , Jan Korst, Fast concurrent access to parallel disks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.849-858, January 09-11, 2000, San Francisco, California, United States
• 25: Jochen Van den Bercken , Björn Blohsfeld , Jens-Peter Dittrich , Jürgen Krämer , Tobias Schäfer , Martin Schneider , Bernhard Seeger, XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.39-48, September 11-14, 2001
• 26: Jochen van den Bercken , Jens-Peter Dittrich , Bernhard Seeger, javax.XXL: a prototype for a library of query processing algorithms, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.588, May 15-18, 2000, Dallas, Texas, United States
• 27: D. E. Vengroff. TPIE User Manual and Reference. Duke University, 1995. http://www.cs.duke.edu/ dev/tpie_home_page.html.
• 28: Jeffrey Scott Vitter , David A. Hutchinson, Distribution sort with randomized cycle, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.77-86, January 07-09, 2001, Washington, D.C., United States
• 29: J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory, I: Two level memories. Algorithmica, 12(2/3):110--147, 1994.
• 30: J. Wyllie. SPsort: How to sort a terabyte quickly.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Performance, Theory

Keywords:
algorithm engineering, algorithm library, external memory sorting, large data sets, overlapping I/O and computation, parallel disks, prefetching, randomized algorithm, secondary memory