AbstractConsider a two-dimensional mesh-connected computer with segmented buses (2-MCCSB). A

k_{1}n_{1}xk_{1}n_{2}2-MCCSB is constructed from ak_{1}n_{1}xk_{1}n_{2}mesh organization by enhancing the power of each disjointn_{1}xn_{2}submesh with multiple buses (sub-2-MCCMB). Given a set ofnelements, this paper presents a parallel algorithm for finding the median inO(n^{1/8}logn) time on ann^{1/2}xn^{1/2}square 2-MCCSB, where each disjoint sub-2-MCCMB is of dimensionn^{3/8}xn^{3/8}. This result is competitive with the previous result with time bound ofO(n^{1/6}(logn)^{2/3}) for finding the median on ann^{1/2}xn^{1/2}square 2-MCCMB and our time bound is equal to the previous time bound ofO(n^{1/8}logn) on ann^{5/8}xn^{3/8}rectangular 2-MCCMB. Furthermore, the time bound of our parallel algorithm can be reduced toO(n^{1/10}logn) time on ann^{3/5}xn^{2/5}rectangular 2-MCCSB, where each disjoint sub-2-MCCMB is of dimensionn^{1/2}xn^{3/10}. We also show that the time bound can be further reduced to O(n^{1/11}logn) ifO(n^{10/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