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

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)615-622
Number of pages8
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume19
Issue number5
DOIs
Publication statusPublished - 1996 Jan 1

Keywords

  • Computation model
  • Parallel random access machine
  • Processor array
  • Reconfigurable bus system

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Simulation of the processor array with reconfigurable bus system on the PRAM'. Together they form a unique fingerprint.

Cite this