TY - JOUR

T1 - Simulation of the processor array with reconfigurable bus system on the PRAM

AU - Lin, Shun Shii

N1 - Funding Information:
This work was supported in part by National Science Council ofthe Republic ofChina under Contract NSC 84-25ll-S-003-089.

PY - 1996

Y1 - 1996

N2 - 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 [16], 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.

AB - 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 [16], 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.

KW - Computation model

KW - Parallel random access machine

KW - Processor array

KW - Reconfigurable bus system

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

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

U2 - 10.1080/02533839.1996.9677825

DO - 10.1080/02533839.1996.9677825

M3 - Article

AN - SCOPUS:0030233845

SN - 0253-3839

VL - 19

SP - 615

EP - 622

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

IS - 5

ER -