An efficient sorting algorithm on the multi-mesh network

被引：17
作者：
De, M [1 ]
Das, D [1 ]
Ghosh, M [1 ]
Sinha, BP [1 ]
机构：
[1] INDIAN STAT INST, ELECT UNIT, CALCUTTA 700035, W BENGAL, INDIA
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1997年 / 46卷 / 10期
关键词：
2D mesh; multidimensional mesh; wrap-around connection; SIMD; MIMD; sorting; shear-sort;
D O I：
10.1109/12.628397
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The shear-sort algorithm [19] on an SIMD mesh model requires 4 root N + o(root N) time for sorting N elements arranged on a root N x root N mesh. In this paper, we present an algorithm for sorting N elements in time O(N-1/4) On an SIMD Multi-Mesh architecture, thereby significantly improving the order of the time complexity. The Multi-Mesh architecture [23], [24] is built around n(2) blocks, where each block is an n x n mesh with n = N-1/4, SO that each processor will uniformly have four neighbors in the final topology.
引用
收藏
页码：1132 / 1137
页数：6
相关论文
共 25 条
[1]  
AGGARWAL A, 1988, LECT NOTES COMPUT SC, V319, P339
[2]  
AJATAI M, 1983, P 15 ACM STOC, P1
[3]   OPTIMAL PARALLEL MERGING AND SORTING WITHOUT MEMORY CONFLICTS [J].
AKL, SG ;
SANTORO, N .
IEEE TRANSACTIONS ON COMPUTERS, 1987, 36 (11) :1367-1369
[4]  
Batcher Kenneth E., 1968, P AFIPS SPRING JOINT, P307, DOI DOI 10.1145/1468075.1468121
[5]  
COLE R, 1986, P IEEE F COMPUTER SC, P511
[6]   SORTING IN MESH CONNECTED MULTIPROCESSORS [J].
CORBETT, PF ;
SCHERSON, ID .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1992, 3 (05) :626-632
[7]  
CYPHER R, 1988, P INT C PARALLEL PRO, V3, P308
[8]  
CYPHER R, 1990, 22ND P ACM S THEOR C, P193
[9]  
Das D., 1995, Proceedings 9th International Parallel Processing Symposium (Cat. No.95TH8052), P17, DOI 10.1109/IPPS.1995.395908
[10]  
DAS S, UNPUB IEEE T COMPUTE
123