Bitonic sorting on 2D-PEC: an algorithmic study on a hierarchy of meshes network
Donna J. Quammen, P.Y. Wang · 2002
Packed exponential connections (PEC) is a new type of network that attempts to solve the scalability and connectivity problems of very large interconnection networks by augmenting a 2D mesh with a uniform distribution of longer connections. In order to gain insight into the use of a MIMD system that has an underlying PEC network, this paper presents the results of an investigation of bitonic sorting on the PEC. It was determined that, by utilizing properties associated with PEC processor farms, it is possible to design an efficient implementation of bitonic sorting that requires O(/spl radic/N) comparisons and has an upper bound estimate of O/spl lsqbspl radic/(log/sup 3/N)/spl middot/2/sup /spl radic/(log/spl radic/N/)/spl rsqb/ on the amount of communications. These complexity results compare favorably with other sorting implementations.>