Cost-effective algorithms for processor arrays with reconfigurable bus systems

Shun Shii Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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 languageEnglish
Pages (from-to)279-288
Number of pages10
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Issue number2
Publication statusPublished - 1994 Mar


  • All-pairs shortest paths problem
  • Computation model
  • Minimum spanning tree problem
  • Parallel processing
  • Processor array
  • Reconfigurable bus system

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Cost-effective algorithms for processor arrays with reconfigurable bus systems'. Together they form a unique fingerprint.

Cite this