High-Performance Sorting on Networks of Workstations.

@inproceedings{DBLP:conf/sigmod/Arpaci-DusseauACHP97,
  author    = {Andrea C. Arpaci-Dusseau and
               Remzi H. Arpaci-Dusseau and
               David E. Culler and
               Joseph M. Hellerstein and
               David A. Patterson},
  editor    = {Joan Peckham},
  title     = {High-Performance Sorting on Networks of Workstations},
  booktitle = {SIGMOD 1997, Proceedings ACM SIGMOD International Conference
               on Management of Data, May 13-15, 1997, Tucson, Arizona, USA},
  publisher = {ACM Press},
  year      = {1997},
  pages     = {243-254},
  ee        = {http://doi.acm.org/10.1145/253260.253322, db/conf/sigmod/Arpaci-DusseauACHP97.html},
  crossref  = {DBLP:conf/sigmod/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Ramesh C. Agarwal: A Super Scalar Sort Algorithm for RISC Processors. SIGMOD Conference 1996: 240-246

[2]

...

[3]

Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau, Amin Vahdat, Lok T. Liu, Thomas E. Anderson, David A. Patterson: The Interaction of Parallel and Sequential Workloads on a Network of Workstations. SIGMETRICS 1995: 267-278

[4]

Chaitanya K. Baru, Gilles Fecteau, Ambuj Goyal, Hui-I Hsiao, Anant Jhingran, Sriram Padmanabhan, Walter G. Wilson: An Overview of DB2 Parallel Edition. SIGMOD Conference 1995: 460-462

[5]

Thorsten von Eicken, Anindya Basu, Vineet Buch, Werner Vogels: U-Net: A User-Level Network Interface for Parallel and Distributed Computing. SOSP 1995: 40-53

[6]

...

[7]

...

[8]

...

[9]

...

[10]

...

[11]

Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990)

[12]

...

[13]

...

[14]

David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990)

[15]

David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting. PDIS 1991: 280-291

[16]

...

[17]

...

[18]

Robert H. Gerber: Informix Online XPS. SIGMOD Conference 1995: 463

[19]

...

[20]

...

[21]

...

[22]

Mark D. Hill, James R. Larus, Steven K. Reinhardt, David A. Wood: Cooperative Shared Memory: Software and Hardware Support for Scalable Multiprocesors. ACM Trans. Comput. Syst. 11(4): 300-318(1993)

[23]

C. A. R. Hoare: Quicksort. Comput. J. 5(1): 10-15(1962)

[24]

...

[25]

...

[26]

Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242

[27]

Betty Salzberg, Alex Tsukerman, Jim Gray, Michael Stewart, Susan Uren, Bonnie Vaughan: FastSort: A Distributed Single-Input Single-Output External Sort. SIGMOD Conference 1990: 94-101

[28]

Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981)

[29]

Michael Stonebraker: The Case for Shared Nothing. IEEE Database Eng. Bull. 9(1): 4-9(1986)

[30]

...

[31]

The Tandem Performance Group: A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper). SIGMOD Conference 1988: 337-341

[32]

...

[33]

Thorsten von Eicken, David E. Culler, Seth Copen Goldstein, Klaus E. Schauser: Active Messages: A Mechanism for Integrated Communication and Computation. ISCA 1992: 256-266

[34]

...

[35]

...

[36]

...