| 摘要: |
| 排序是计算机事务处理的重要操作之一.前人已经就内部排序、外部排序和并行排序提出各种方法.从一种全新的视角研究了排序算法,提出一种在单机上实现的并行排序算法THSORT(Tsinghua SORT).它用多个进程分别控制不同的硬件部件,使输入、排序和输出能够同时进行,从而大大提高了硬件部件的并行性和运行效率.在带有双磁盘阵列的硬件平台上进行的测试表明,THSORT的性能达到了NTSORT(new technology SORT)的1倍左右,并成为2002年PennySort(Daytona类)世界排序纪录的保持者. |
| 关键词: 并行I/O 单机并行排序 THSORT(Tsinghua SORT) PennySort |
| DOI： |
| 分类号: |
| 基金项目:Supported by the Doctor's Scientific Research and Innovation Foundation of Tsinghua University of China (清华大学博士生科研创新基金) |
|
| THSORT: A Single-Processor Parallel Sorting Algorithm |
|
SHI Yao,ZHANG Li,LIU Peng
|
| 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. |
| Key words: parallel I/O single-processor parallel sorting THSORT (Tsinghua SORT) PennySort |
