Bitonic sorting on 2D-PEC: an algorithmic study on a hierarchy of meshes network

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(√N) comparisons and has an upper bound estimate of O[√(log³N)·2/sup √(log√N/)] on the amount of communications. These complexity results compare favorably with other sorting implementations