Two-Dimensional Processor Array with a Reconfigurable Bus System is at Least as Powerful as CRCW Model.
Journal
Inf. Process. Lett.
Journal Volume
36
Journal Issue
1
Pages
31-36
Date Issued
1990
Author(s)
Wang, Biing-Feng
Abstract
The power of a computation model usually indicates how fast a problem can be solved under that model. The CRCW shared-memory computer has been considered the most powerful computation model. Recently, the two-dimensional processor array with a reconfigurable bus system (such as the reconfigurable mesh and the polymorphic-torus network) has been proposed for solving many problems efficiently. Since the structure of the two-dimensional processor array with a reconfigurable bus system is regular, it is suitable for VLSI implementation. In this paper, we show that the two-dimensional processor array with a reconfigurable bus system is at least as powerful as the CRCW shared-memory computer. To say more concretely, we show that if a problem can be solved in O(f(n)) time on the CRCW shared-memory computer, it can also be solved in O(f(n)) time on the two-dimensional processor array with a reconfigurable bus system. Also, the proof suggests a general method to convert algorithms designed on the former into algorithms on the latter. © 1990.
Subjects
Computational complexity; CRCW shared-memory computer; MIMD; processor array; reconfigurable bus; SIMD
SDGs
Other Subjects
Computer Programming--Algorithms; Concurrent Read Concurrent Write; Reconfigurable Bus; Shared Memory Computers; Computer Systems, Digital
Type
journal article