THSORT:单机并行排序算法  

THSORT: A Single-Processor Parallel Sorting Algorithm

作　　者：施遥[1] 张力[1] 刘鹏[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《软件学报》2003年第2期159-165,共7页Journal of Software

基　　金：清华大学博士生科研创新基金~~

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

关 键 词：THSORT 单机 并行排序算法 事务处理 计算机 

分 类 号：O223[理学—运筹学与控制论] TP301.6[理学—数学]