SheenkSort: 2003 Performance / Price Sort and PennySort
Lei Yang, Hui Huang, Zheng Wan, Tao Song · 2003
The technology of sorting is one of the most fundamental and important technologies in computer science. The external sorting deals with various operations including disk I/O, memory management and CPU-burdened computation, thus has been widely accepted as an overall benchmark to evaluate the processing power of computers. Among such benchmarks the PennySort and the Performance / Price are both aiming at the highest cost efficiency. SheenkSort, with the new YHSort Framework fully considering the statistic properties of the data to be processed, and with carefully designed system architecture, exploits much deeper the potential of popular desktop PC than before. It is able to sort 42.28 GB data (454,033,408 records of 100 bytes each) for a penny, which is quite over four times of the last year ’s Daytona PennySort record setup by THSort (9.8GB data), or about three and a half times of the last year’s Indy PennySort record setup by DMSort (12.2GB data). This paper presents the main considerations for SheenkSort and reports the results for PennySort, Performance / Price Sort, as well as Datamation Sort and Minute Sort. 2003 Daytona & Indy PennySort Result Hardware Considerations Hardware components of SheenkSort may be all purchased at http://www.ussa.com. With the help of the new YHSort Framework CPU is unburdened and the AMD Athlon XP 1700 is found to be powerful but cheap enough to meet our request. When considering the motherboard which is the most important among all parts, the new nForce-2 chipset (SPP + MCP) attracts us after 1 State Key Laboratory of Intelligent Technology and Systems, Department of Computer Science & Technology, Tsinghua University, Beijing, China 2 NSFOCUS Information Technology Co., Ltd., Beijing, China 3 Department of Physics, Tsinghua University, Beijing, China 4 Institute of Computer Network Technology, Department of Computer Science & Technology, Tsinghua University, Beijing, China 5 Sort Benchmark homepage at http://research.microsoft.com/barc/SortBenchmark/. 6 Named after the team. 7 Named after the designers, Yang, L. and Huang, H. The YHSort Framework includes both the External YHSort and the Internal YHSort algorithms. The key idea is to minimize the number of comparing and exchanging operations between records by estimating the target position of each record using statistic information. The YHSort Framework uses a general method to gather this statistic information at running-time and it is able to handle all popular cases (including those of non-uniform distributions). The lengthen details of YHSort are not included in this paper. Contact the authors if this interests you. 8 Throughout this paper KB = 1024 bytes, MB = 1024 = 1048576 bytes, and GB = 1024 = 1073741824 bytes. careful comparison. It shows excellent performances of both IDE and memory I/O. Unfortunately the nForce-2 chipset is still not widely supported until today, and the MSI K7N2-L becomes our choice. The nForce-2 has a 128-bit DDR memory channel which helps a lot the internal sorting as one of the fundamental procedures of the external sort. PC2700 had been considered and was shown to benefit this internal sorting procedure, but that required an expensive AMD Athlon XP 2600+ which cost us almost $200 more than the economic Athlon XP 1700. That is the reason we choose PC2100. The choice of hard disk drive is also very import since the external sorting is almost fully disk-I/O-bounded. After the comparison of various brands of various capacities, the Maxtor DiamondMax Plus 8 of 40GB (7200RPM, ATA133) outperformed the others, whose throughput reaches about 50MBps in the test of stand-alone sequentially reading or writing, and the overall throughput of all the four hard disks is as high as 125MBps at running time.