TIME-SPACE OPTIMAL PARALLEL MERGING AND SORTING

被引：15

作者：

GUAN, XJ ^{[1
]}

LANGSTON, MA ^{[1
]}

机构：

[1] UNIV TENNESSEE,DEPT COMP SCI,KNOXVILLE,TN 37996

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1991年 / 40卷 / 05期

关键词：

BLOCK REARRANGING; INTERNAL BUFFERING; MEMORY MANAGEMENT; MERGING AND SORTING; PARALLEL COMPUTATION; TIME-SPACE OPTIMALITY;

D O I：

10.1109/12.88483

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A parallel algorithm is time-space optimal if it achieves optimal speedup and if it uses only a constant amount of extra space per processor even when the number of processors is fixed. Previously published parallel merging and sorting algorithms fail to meet at least one of these criteria. In this paper, we present a parallel merging algorithm that, on an EREW PRAM with k processors, merges two sorted lists of total length n in O(n/k + log n) time and O(k) extra space, and is thus time-space optimal for any value of k less-than-or-equal-to n/(log n). We also describe a stable version of our parallel merging algorithm that is similarly time-space optimal on an EREW PRAM. These two parallel merges naturally lead to time-space optimal parallel sorting algorithms.

引用

页码：596 / 602

页数：7

共 22 条

[1] OPTIMAL PARALLEL MERGING AND SORTING WITHOUT MEMORY CONFLICTS [J].