Relations Between Several Parallel Computational Models

Abstract

We investigate the relative computational power of parallel models
with shared memory. Based on feasibility considerations present in
the literature, we split these models into lightweight and
heavyweight, and then find that the heavyweight class is
strictly more powerful than the lightweight class, as expected. On
the other hand, we contradict the long held belief that the
heavyweight models (namely, the Combining CRCW PRAM and the
BSR) form a hierarchy, showing that they are identical in
computational power with each other. We thus introduce the BSR
into the family of practically meaningful massively parallel models.
We also investigate the power of concurrent-write on models with
reconfigurable buses, finding that it does not add computational
power over exclusive-write under certain reasonable assumptions.
Overall, the Combining CRCW PRAM and the CREW models with
directed reconfigurable buses are found to be the simplest of the
heavyweight models, which now also include the BSR and all the
models with directed reconfigurable buses. These results also have
significant implications in the area of real-time computations.