The Shared Memory Hierarchy: The PRAM is as Powerful as the BSR

摘要

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. This result also has significant implications in the area of real-time computations.