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 BibTeX

[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 BibTeX

[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 BibTeX

[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 BibTeX

[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) BibTeX

[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) BibTeX

[15]

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

[16]

...

[17]

...

[18]

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

[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) BibTeX

[23]

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

[24]

...

[25]

...

[26]

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

[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 BibTeX

[28]

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

[29]

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

[30]

...

[31]

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

[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 BibTeX

[34]

...

[35]

...

[36]

...

Referenced by

1. Ron Avnur, Joseph M. Hellerstein: Eddies: Continuously Adaptive Query Processing. SIGMOD Conference 2000: 261-272
2. Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, David A. Wood: DBMSs on a Modern Processor: Where Does Time Go? VLDB 1999: 266-277
3. Botao Wang, Hiroyuki Horinokuchi, Kunihiko Kaneko, Akifumi Makinouchi: Parallel R-Tree Search Algorithm on DSVM. DASFAA 1999: 237-245
4. Kimberly Keeton, David A. Patterson, Joseph M. Hellerstein: A Case for Intelligent Disks (IDISKs). SIGMOD Record 27(3): 42-52(1998)
5. Erik Riedel, Garth A. Gibson, Christos Faloutsos: Active Storage for Large-Scale Data Mining and Multimedia. VLDB 1998: 62-73
6. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581