ON THE POWER OF TWO-DIMENSIONAL PROCESSOR ARRAYS WITH RECONFIGURABLE BUS SYSTEMS
Stephan Olariu, James L. Schwing, Jingyuan Zhang · Parallel Processing Letters · 1991
Quite recently it has been proved that a two-dimensional processor array with a reconfigurable bus system (PARBS, for short) is at least as powerful as the CRCW shared memory computer. In this note we argue that the well-known PARITY problem can be solved in O(1) time on a two-dimensional PARBS of (n+1)×n processors. Since it is known that PARITY cannot be solved in constant time on a CRCW even if a polynomial number of processors is available, our result shows that the two-dimensional PARBS is strictly more powerful than the CRCW.