Can a Shared-Memory Model Serve as a Bridging Model for Parallel Computation?

There has been a great deal of interest recently in the development of general-purpose bridging models for parallel computation. Models such asthe bsp and logp have been proposed as more realistic alternatives to the widely-used pram model. The bsp and logp models imply a rather different style for designing algorithms when compared to the pram model. Indeed, while many consider data parallelism as a convenient style, and the shared-memory abstraction as an easyto-use platform, the bandwidth limitations of current machines have diverted much attention to message-passing and distributed-memory models (such as the bsp and logp) that account more properly for these limitations. In this paper we consider the question of whether a shared-memory model can serve as an effective bridging model for parallel computation. In particular, can a shared-memory model be as effective as, say, the bsp? As a candidate for a bridging model, we introduce the Queuing Shared Memory (qsm) model, which accounts for limited communication bandwidth while still providing a simple shared-memory abstraction. We substantiate the ability of the qsm to serv