
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Comparison between the Computational Power of PARBS and RMBM
Kensuke MIYASHITA Yoshihiro TSUJINO Nobuki TOKURA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E79D
No.5
pp.570578 Publication Date: 1996/05/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: parallel computational model, processor array, reconfigurable bus, PARBS, RMBM,
Full Text: PDF>>
Summary:
Processor networks connected by buses have attracted considerable attention. Since a reconfigurable array is more powerful than a PRAM and more practical, it becomes the focus of attention. The Processor Array with Reconfigurable Bus System (PARBS) and the Reconfigurable Multiple Bus Machine (RMBM) are both models of parallel computation based on reconfigurable bus and processor array. The PARBS is a processor array that consists of processors arranged to a 2dimensional grid with a reconfigurable bus system. The RMBM is also made of processors and reconfigurable bus system, but the processors are located in a row and the number of processors and the number of buses are independent of each other. Four versions of RMBM has been proposed and Extended RMBM (ERMBM) is regarded as the most powerful one among them. In this paper, we describe that a PARBS of size N M can be simulated in constant time by a ERMBM of 4NM processors, M + 3 buses and 1 read buffer, and that a ERMBM of P processors, B buses and D read buffers can be also simulated in constant time by a PARBS of size B P. A PARBS or RMBM that solves a computational problem of size n is polynomially bounded iff the product of the number of processors and buses and red and write ports is O (n^{c}), for some constant c. When a PARBS is polynomially bounded, the ERMBM which simulates it is also polynomially bounded, and vice versa.

