Distribution sort with randomized cycling

ABSTRACT

Parallel independent disks can enhance the performance of external memory (EM) algorithms, but the programming task is often difficult. Each disk can service only one read or write request at a time; the challenge is to keep the disks as busy as possible. In this article, we develop a randomized allocation discipline for parallel independent disks, called randomized cycling. We show how it can be used as the basis for an efficient distribution sort algorithm, which we call randomized cycling distribution sort (RCD). We prove that the expected I/O complexity of RCD is optimal. The analysis uses a novel reduction to a scenario with significantly fewer probabilistic interdependencies. We demonstrate RCD's practicality by experimental simulations. Using the randomized cycling discipline, algorithms developed for the unrealistic multihead disk model can be simulated on the realistic parallel disk model for the class of multipass algorithms, which make a complete pass through their data before accessing any element a second time. In particular, algorithms based upon the well-known distribution and merge paradigms of EM computation can be optimally extended from a single disk to parallel disks.

REFERENCES

• 1: 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]
• 2: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• 3: Lars Arge , Darren Erik Vengroff , Jeffrey Scott Vitter, External-Memory Algorithms for Processing Line Segments in Geographic Information Systems, Algorithmica, v.47 n.1, p.1-25, January 2007 [doi>10.1007/s00453-006-1208-z]
• 4: Lars Arge , Jeffrey Scott Vitter, Optimal External Memory Interval Management, SIAM Journal on Computing, v.32 n.6, p.1488-1508, 2003 [doi>10.1137/S009753970240481X]
• 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: Barve, R. D., and Vitter, J. S. 2002. A simple and efficient parallel disk mergesort. ACM Trans. Comput. Syst. 35, 2 (Mar./Apr.), 189--215.
• 7: Dehne, F., Dittrich, W., and Hutchinson, D. 2003. Efficient external memory algorithms by simulating coarse-grained parallel algorithms. Algorithmica 36, 87--122.
• 8: Dehne, F., Hutchinson, D., and Maheshwari, A. 2002. Bulk synchronous parallel algorithms for the external memory model. Theory Comput. Syst. 35, 567--597.
• 9: Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M]
• 10: Goodrich, M. T., Tsay, J.-J., Vengroff, D. E., and Vitter, J. S. 1993. External-memory computational geometry. In Proceedings of the IEEE Symposium on Foundations of Computer Science. (Palo Alto, CA) IEEE Computer Society Press, Los Alamitos, CA, 714--723.
• 11: Henzinger, M. R., Raghavan, P., and Rajagopalan, S. 1998. Computing on data streams. Tech. Rep. 1998--011, Digital Equipment Corporation Systems Research Center, Palo Alto, CA.
• 12: David A. Hutchinson , Peter Sanders , Jeffrey Scott Vitter, Duality Between Prefetching and Queued Writing with Parallel Disks, SIAM Journal on Computing, v.34 n.6, p.1443-1463, 2005 [doi>10.1137/S0097539703431573]
• 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: 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]
• 15: 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]
• 16: 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
• 17: TPIE 1999. TPIE user manual and reference. The manual and software distribution are available on the web at http://www.cs.duke.edu/TPIE/.
• 18: Vengroff, D. E. 1994. A transparent parallel I/O environment. In Proceedings of the DAGS Symposium on Parallel Computation (Hanover, NH). 117--134.
• 19: D. E. Vengroff , J. Scott Vitter, Supporting I/O-efficient scientific computation in TPIE, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.74, October 25-28, 1995
• 20: 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]
• 21: Jeffrey Scott Vitter , Philippe Flajolet, Average-case analysis of algorithms and data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 22: Vitter, J. S., and Shriver, E. A. M. 1994. Algorithms for parallel memory I: Two-level memories. Algorithmica 12, 2--3, 110--147.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

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

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

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

Keywords:
distribution, external memory, external sorting, input/output, merging, multipass algorithms, multiple disks, parallel disks, randomization, sorting