AbstractConsider a two-dimensional mesh-connected computer with segmented buses (2-MCCSB). A k1n1 x k1n2 2-MCCSB is constructed from a k1n1 x k1n2 mesh organization by enhancing the power of each disjoint n1 x n2 submesh with multiple buses (sub-2-MCCMB). Given a set of n elements, this paper presents a parallel algorithm for finding the median in O(n1/8 log n) time on an n1/2 x n1/2 square 2-MCCSB, where each disjoint sub-2-MCCMB is of dimension n3/8 x n3/8. This result is competitive with the previous result with time bound of O(n1/6(log n)2/3) for finding the median on an n1/2 x n1/2 square 2-MCCMB and our time bound is equal to the previous time bound of O(n1/8 log n) on an n5/8 x n3/8 rectangular 2-MCCMB. Furthermore, the time bound of our parallel algorithm can be reduced to O(n1/10 log n) time on an n3/5 x n2/5 rectangular 2-MCCSB, where each disjoint sub-2-MCCMB is of dimension n1/2 x n3/10. We also show that the time bound can be further reduced to O(n1/11 log n) if O(n10/11) processors are used. Our algorithm can be modified to solve the selection problem.
Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors); F.1.2 [Computation by Abstract Devices]: Modes of Computation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: broadcasting, median finding, meshes, meshes with multiple buses, parallel algorithms, selection