A processor array with a reconfigurable bus system (abbreviated to PARBS) is a computation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. The power of a computation model usually indicates how fast a problem can be solved under that model. In , Wang and Chen have shown that the two-dimensional PARBS is at least as powerful as the PRAM (parallel random access machine). That is, if a problem can be solved in O(f(n)) time on the PRAM with n processors and m memory cells, it can also be solved in O(f(n)) time on the two-dimensional PARBS with n*m processors. The reverse assertion has not been proven yet. The difficulty arises from the great flexibility in the configurations of reconfigurable system. In this paper, we show that a restricted version of the PARBS, called ORTHOGONAL PARBS, which includes all one-dimensional PARBS with two-neighbor connections and many two-dimensional PARBS with four-neighbor connections used by some researchers, can be simulated accordingly on the SUM CRCW PRAM. That is, if a problem can be solved in O(f(n)) time on the ORTHOGONAL PARBS with n processors, it can also be solved in O(f(n)) time and O(n) memory cells on the SUM CRCW PRAM.
|頁（從 - 到）||615-622|
|期刊||Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an|
|出版狀態||已發佈 - 1996|
ASJC Scopus subject areas
- 工程 (全部)