Searching for the sorting record
Andrea Carol Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, David Culler, Joseph M. Hellerstein, David A. Patterson · 1998
We present our experiences in developing and tuning the performance of NOW-Sort, a parallel, disk-to-disk sorting algorithm.NOW-Sort currently holds two world records in databaseindustry standard benchmarks.Critical to the tuning process was the setting of expectations, which tell the programmer both where to tune and when to stop.We found three categories of useful tools: tools that help set expectations and configure the application to different hardware parameters, visualization tools that animate performance counters, and search tools that track down performance anomalies.All such tools must interact well with all layers of the underlying software (e.g., the operating system), as well as with applications that leverage modem OS features, such as threads and memory-mapped I/O.1 Introduction On March I, 1996, after much debate about how to benchmark our prototype cluster system, we decided to implement an external, or disk-to-disk, parallel sort.External sorting had all of the qualities we desired in a benchmark.First, external sorting is both memory and I/O intensive.Second, sorting stresses many aspects of both local and distributed operating system performance.Third, well-understood sorting algorithms exist for both sequential and parallel environments.Finally, the presence of industry-standard benchmarks allows us to compare our performance to that of other large-scale systems.At that time, a l2-processor SGI Challenge held the worldrecords on the two existing benchmarks.For the Datamation benchmark [ 131, the SGI had sorted I million loo-byte records with IO-byte keys from disk to disk in 3.52 seconds.For MinuteSort [25], I .6GB of these loo-byte records were sorted within one minute [32].Our goal was to surpass these records with a cluster of I05 UltraSPARC I workstations connected with a high-speed network.Over one year later, on April I, 1997 (April Fool's day), with the help of many people in the U.C. Berkeley NOW project [3], we laid claim to both benchmark records.On 32 machines, we reduced the time to sort I million records Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy otherwise, to