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.