TY - JOUR

T1 - Cost-effective algorithms for processor arrays with reconfigurable bus systems

AU - Lin, Shun Shii

N1 - Funding Information:
This work was partially supported by the National Science Council, Taipei, Taiwan, the Republic of China, under Contract No. NSC 81-0408-E-003-503.

PY - 1994/3

Y1 - 1994/3

N2 - 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.

AB - 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.

KW - All-pairs shortest paths problem

KW - Computation model

KW - Minimum spanning tree problem

KW - Parallel processing

KW - Processor array

KW - Reconfigurable bus system

UR - http://www.scopus.com/inward/record.url?scp=0028387598&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028387598&partnerID=8YFLogxK

U2 - 10.1080/02533839.1994.9677591

DO - 10.1080/02533839.1994.9677591

M3 - Article

AN - SCOPUS:0028387598

VL - 17

SP - 279

EP - 288

JO - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

JF - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

SN - 0253-3839

IS - 2

ER -