THSORT:单机并行排序算法

排序是计算机事务处理的重要操作之一.前人已经就内部排序、外部排序和并行排序提出各种方法.从一种全新的视角研究了排序算法,提出一种在单机上实现的并行排序算法THSORT(Tsinghua SORT).它用多个进程分别控制不同的硬件部件,使输入、排序和输出能够同时进行,从而大大提高了硬件部件的并行性和运行效率.在带有双磁盘阵列的硬件平台上进行的测试表明,THSORT的性能达到了NTSORT(new technology SORT)的1倍左右,并成为2002年PennySort(Daytona类)世界排序纪录的保持者.

THSORT: A Single-Processor Parallel Sorting Algorithm

Sorting is an important operation of transaction processing. It is a relatively mature field, as many algorithms for memory sorting, disk sorting and parallel sorting have come forth in the past decades. In this paper, the sorting algorithm is studied from a thoroughly different standpoint, and the THSORT (Tsinghua SORT), a parallel sorting algorithm on a single computer, is brought forward. THSORT uses several processes to control different components of a computer, which enables the data input, sorting and output to be run concurrently, and thus greatly enhances the parallelism and efficiency of the hardware. Experimental results based on a computer with two RAIDs (redundant array of inexpensive disks) indicate that THSORT has almost doubled the performance of NTSORT (new technology SORT), a famous sorting program. Moreover, THSORT has won the 2002 PennySort competition and is still holding the world record in the Daytona category.