2015-04-07

High-Performance Sorting on Networks of Workstations

Authors

Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein, David A. Patterson

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.

Discussion Notes

• It was interesting to read about the hardware probing tools the authors made, reminding of exercises each of us performed in an Operating Systems course.
• The discussion of hardware limitations in the paper is still relevant today, since we face similar limitations but on a different scale with larger datasets and more powerful hardware.
• Interesting note of Radix sort and sorting without using comparisons.
• Branched into a discussion of various Operating Systems topics.
• The paper was an early example of networked workstations surpassing high end shared memory machines.