Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 279-288 |
Number of pages | 10 |
Journal | Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an |
Volume | 17 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1994 Mar |
Keywords
- All-pairs shortest paths problem
- Computation model
- Minimum spanning tree problem
- Parallel processing
- Processor array
- Reconfigurable bus system
ASJC Scopus subject areas
- Engineering(all)