A new horizon for sorting on mesh architectures
Hossam El Gindy · 2002
The author introduces the use of data duplication in massively parallel architectures as a tool for improving the running time of the basic data movement operations. He demonstrates its use by presenting two algorithms for sorting N items on mesh architectures of square root N* square root N processors. The first algorithm has an O(N/sup 1/3/ log N) running time and requires the use of O(N/sup 2/3/) memory locations per processor. The second has an O((N log N)/sup 1/3/) running time and requires the use of O(N/sup 2/3//log/sup 1/3/N) memory locations per processor and multiple broadcasting buses.>