Journal of Software:2003.14(2):159-165

THSORT: A Single-Processor Parallel Sorting Algorithm
Chart / table
Similar Articles
Article :Browse 3541   Download 3424
Received:November 19, 2002    Revised:December 10, 2002
> 中文摘要: 排序是计算机事务处理的重要操作之一.前人已经就内部排序、外部排序和并行排序提出各种方法.从一种全新的视角研究了排序算法,提出一种在单机上实现的并行排序算法THSORT(Tsinghua SORT).它用多个进程分别控制不同的硬件部件,使输入、排序和输出能够同时进行,从而大大提高了硬件部件的并行性和运行效率.在带有双磁盘阵列的硬件平台上进行的测试表明,THSORT的性能达到了NTSORT(new technology SORT)的1倍左右,并成为2002年PennySort(Daytona类)世界排序纪录的保持者.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the Doctor's Scientific Research and Innovation Foundation of Tsinghua University of China (清华大学博士生科研创新基金) Supported by the Doctor's Scientific Research and Innovation Foundation of Tsinghua University of China (清华大学博士生科研创新基金)
Foundation items:
Reference text:


SHI Yao,ZHANG Li,LIU Peng.THSORT: A Single-Processor Parallel Sorting Algorithm.Journal of Software,2003,14(2):159-165