### 摘要

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.

原文 | 英語 |
---|---|

頁（從 - 到） | 279-288 |

頁數 | 10 |

期刊 | Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an |

卷 | 17 |

發行號 | 2 |

DOIs | |

出版狀態 | 已發佈 - 1994 三月 |

### ASJC Scopus subject areas

- Engineering(all)

## 指紋 深入研究「Cost-effective algorithms for processor arrays with reconfigurable bus systems」主題。共同形成了獨特的指紋。

## 引用此

*Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an*,

*17*(2), 279-288. https://doi.org/10.1080/02533839.1994.9677591