AN EFFICIENT SORTING ALGORITHM ON THE MULTI-MESH NETWORK

Authors
DE M DAS D GHOSH M SINHA BP
Citation
M. De et al., AN EFFICIENT SORTING ALGORITHM ON THE MULTI-MESH NETWORK, I.E.E.E. transactions on computers, 46(10), 1997, pp. 1132-1137
Citations number
25
Categorie Soggetti
Computer Sciences","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
Journal title
I.E.E.E. transactions on computers → ACNP
ISSN journal
00189340
Volume
46
Issue
10
Year of publication
1997
Pages
1132 - 1137
Database
ISI
SICI code
0018-9340(1997)46:10<1132:AESAOT>2.0.ZU;2-G
Abstract
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 significant ly improving the order of the time complexity. The Multi-Mesh architec ture [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 fo ur neighbors in the final topology.