High-performance sorting on networks of workstations

ABSTRACT

We report the performance of NOW-Sort, a collection of sorting implementations on a Network of Workstations (NOW). We find that parallel sorting on a NOW is competitive to sorting on the large-scale SMPs that have traditionally held the performance records. On a 64-node cluster, we sort 6.0 GB in just under one minute, while a 32-node cluster finishes the Datamation benchmark in 2.41 seconds. Our implementations can be applied to a variety of disk, memory, and processor configurations; we highlight salient issues for tuning each component of the system. We evaluate the use of commodity operating systems and hardware for parallel sorting. We find existing OS primitives for memory management and file access adequate. Due to aggregate communication and disk bandwidth requirements, the bottleneck of our system is the workstation I/O bus.

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: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 3: Remzi H. Arpaci , Andrea C. Dusseau , Amin M. Vahdat , Lok T. Liu , Thomas E. Anderson , David A. Patterson, The interaction of parallel and sequential workloads on a network of workstations, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.267-278, May 15-19, 1995, Ottawa, Ontario, Canada
• 4: Chaitanya Baru , Gilles Fecteau, An overview of DB2 parallel edition, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.460-462, May 22-25, 1995, San Jose, California, United States
• 5: T. von Eicken , A. Basu , V. Buch , W. Vogels, U-Net: a user-level network interface for parallel and distributed computing (includes URL), Proceedings of the fifteenth ACM symposium on Operating systems principles, p.40-53, December 03-06, 1995, Copper Mountain, Colorado, United States
• 6: B. A. W. Baugstø , J. F. Greipsland , J. Kamerbeek, Sorting large data files on POOMA, Proceedings of the joint international conference on Vector and parallel processing, p.536-547, September 1990, Zurich, Switzerland
• 7: Micah Beck , Dina Bitton , W. K Wilkinson, Sorting Large Files on a Backend Multiprocessor, Cornell University, Ithaca, NY, 1986
• 8: Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
• 9: M. A. Blumrich , K. Li , R. Alpert , C. Dubnicki , E. W. Felten , J. Sandberg, Virtual memory mapped network interface for the SHRIMP multicomputer, Proceedings of the 21ST annual international symposium on Computer architecture, p.142-153, April 18-21, 1994, Chicago, Illinois, United States
• 10: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• 11: H. Boral , W. Alexander , L. Clay , G. Copeland , S. Danforth , M. Franklin , B. Hart , M. Smith , P. Valduriez, Prototyping Bubba, A Highly Parallel Database System, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.4-24, March 1990 [doi>10.1109/69.50903]
• 12: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 13: David E. Culler , Lok Tin Liu , Richard P. Martin , Chad O. Yoshikawa, Assessing Fast Network Interfaces, IEEE Micro, v.16 n.1, p.35-43, February 1996 [doi>10.1109/40.482310]
• 14: 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]
• 15: 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
• 16: Andrea C. Dusseau , David E. Culler , Klaus Erik Schauser , Richard P. Martin, Fast Parallel Sorting Under LogP: Experience with the CM-5, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.791-805, August 1996 [doi>10.1109/71.532111]
• 17: A measure of transaction processing power, Datamation, v.31 n.7, p.112-118, March 15, 1985
• 18: Bob Gerber, Informix online XPS, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.463, May 22-25, 1995, San Jose, California, United States
• 19: D. P. Ghormley, D. Petrou, A. M. Vahdat, and T. E. Anderson. GLUnix: A Global Layer Unix for NOW. http://now.cs.berkeley.edu/Glunix/glunix.html.
• 20: G. Graefe. Volcano: An Extensible and Parallel Dataflow Query Processing System. Technical report, Oregon Graudate Center, June 1989.
• 21: G. Graefe. Parallel External Sorting in Volcano. Technical Report CU-CS-459, Computer Science, University of Colorado at Boulder, June 1990.
• 22: Mark D. Hill , James R. Larus , Steven K. Reinhardt , David A. Wood, Cooperative shared memory: software and hardware for scalable multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.300-318, Nov. 1993 [doi>10.1145/161541.161544]
• 23: C. A. R. Hoare. Quicksort. Computer Journal, 5( 1): 10-15,1962.
• 24: Steven Kleiman , Jim Voll , Joe Eykholt , Anil Shivalingiah , Dock Williams, Symmetric multiprocessing in Solaris 2.0, Proceedings of the thirty-seventh international conference on COMPCON, p.181-186, January 1992, San Francisco, California, 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: 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
• 27: 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
• 28: Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981 [doi>10.1145/358699.358703]
• 29: M. Stonebraker. The Case for Shared Nothing. Database Engineering, 9(1 ), 1986.
• 30: A. Sweeney, D. Doucette, W. Hu, C. Anderson, M. Nishimoto, and G. Peck. Scalability in the XFS File System. in Proceedings of the USENIX 1996 Annual Technical Conference, Jan. 1996.
• 31: CORPORATE Tandem Performance Group, A benchmark of non-stop SQL on the debit credit transaction, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.337-341, June 01-03, 1988, Chicago, Illinois, United States
• 32: Teradata Corporation. DBC/IO12 Data Base Computer System Manual, release 2.0 edition, Nov. 1985. Document Number c 10- 0001-02.
• 33: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 34: Honesty C. Young , Arun N. Swami, The parameterized Round-Robin partitioned algorithm for parallel external sort, Proceedings of the 9th International Symposium on Parallel Processing, p.213, April 25-28, 1995
• 35: 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]
• 36: Weiye Zhang , Per-Åke Larson, A memory-adaptive sort (MASORT) for database systems, Proceedings of the 1996 conference of the Centre for Advanced Studies on Collaborative research, p.41, November 12-14, 1996, Toronto, Ontario, Canada

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Workstations

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

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