Title :
Sorting n2 numbers on n×n meshes
Author :
Nigam, Madhusudan ; Sahni, Sartaj
Author_Institution :
Dept. of Comput. & Inf. Sci., Florida Univ., Gainesville, FL, USA
fDate :
12/1/1995 12:00:00 AM
Abstract :
We show that by folding data from an n×n mesh onto an n×(n/k) submesh, sorting on the submesh, and finally unfolding back onto the entire n×n mesh it is possible to sort on bidirectional and strict unidirectional meshes using a number of routing steps that is very close to the distance lower bound for these architectures
Keywords :
computational complexity; parallel algorithms; sorting; bidirectional meshes; data folding; data unfolding; distance lower bound; mesh architectures; routing steps; submesh; unidirectional meshes; Computer architecture; Concurrent computing; Distributed computing; Notice of Violation; Routing; Sorting;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
