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
    AKL, SG
    SANTORO, N
    [J]. 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
    CORBETT, PF
    SCHERSON, ID
    [J]. 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