Cost-effective algorithms for processor arrays with reconfigurable bus systems

A processor array with a reconfigurable bus system (abbreviated to PARBS) is a computation model which consists of a processor array and areconfigurable bus system. It is a very powerful computation model in thatit possesses the ability to solve many problems efficiently. However, mostexisting efficient algorithms on PARBS’s use a large number of processorsto solve problems. For example, to determine the maximum (minimum) ofndata items in0(1) time,0(n2)processors are required [12]. To solvethe all-pairs shortest paths and the minimum spanning tree problems in 0(logn)time,0(n4)processors are required [20]. These networks will thereforebecome very expensive for largen.In this paper, we introduce the conceptof iterative-PARBS, which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block throughwhich the processing data can be routed several times. We can think of itas a “hardware subroutine.” Based on this scheme, it is possible to exploremore cost-effective, time-efficient parallel algorithms for use in a PARBS. The following new results are derived in this study: 1) The minimum (maximum) ofndata items can be determined in 0(1)time on a PARBS with 0(n1+£) processors for any fixed S > 0. 2) The all-pairs shortest paths and the minimum spanning tree problemscan be solved in 0(logn)time on a PARBS with 0(n3+s) processorsfor any fixed S > 0.