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

共 50 条

[1] Parallel sorting algorithm using multiway merge and its implementation on a multi-mesh network
Sinha, BP
Mukherjee, A
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2000, 60 (07) : 891 - 907
[2] k-k Sorting on the multi-mesh
Avermiddig, A
Kunde, M
Osterloh, A
FUNDAMENTALS OF COMPUTATION THEORY, PROCEEDINGS, 1997, 1279 : 93 - 104
[3] Parallel prefix computation on extended multi-mesh network
Jana, PK
Naidu, BD
Kumar, S
Arora, M
Sinha, BP
INFORMATION PROCESSING LETTERS, 2002, 84 (06) : 295 - 303
[4] A peer-to-peer network based on multi-mesh architecture
Murthy, S
Sen, A
GLOBECOM'03: IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE, VOLS 1-7, 2003, : 3840 - 3844
[5] Analysis of Multi-Sort Algorithm on Multi-Mesh of Trees (MMT) architecture
Nitin Rakesh
The Journal of Supercomputing, 2011, 57 : 276 - 313
[6] Analysis of Multi-Sort Algorithm on Multi-Mesh of Trees (MMT) architecture
Rakesh, Nitin
Nitin
JOURNAL OF SUPERCOMPUTING, 2011, 57 (03): : 276 - 313
[7] DIRECT REDUCTION OF A MULTI-MESH CIRCUIT TO A FOUR-TERMINAL NETWORK
ROGERS, DWW
ELECTRONIC ENGINEERING, 1965, 37 (452): : 678 - &
[8] An Efficient Parallel Sorting Algorithm on OTIS Mesh of Trees
Lucas, Keny T.
Jana, Prasanta K.
2009 IEEE INTERNATIONAL ADVANCE COMPUTING CONFERENCE, VOLS 1-3, 2009, : 175 - +
[9] Shortest Path Routing on Multi-Mesh of Trees
Jha, Sudhanshu Kumar
Jana, Prasanta K.
WORLD CONGRESS ON ENGINEERING, WCE 2011, VOL II, 2011, : 1538 - 1542
[10] On multi-mesh H-adaptive methods
Li, R
JOURNAL OF SCIENTIFIC COMPUTING, 2005, 24 (03) : 321 - 341

← 1 2 3 4 5 →