Emulations Between QSM, BSP and LogP:A Framework for General-Purpose Parallel Algorithm Design \Lambda

Abstract We present work-preserving emulations with small slowdown between LogP and two other parallelmodels: BSP and QSM. In conjunction with earlier work-preserving emulations between QSM and BSP these results establish a close correspondence between these three general-purpose parallel models. Ourresults also correct and improve on results reported earlier on emulations between BSP and LogP. In particular we shed new light on the relative power of stalling and nonstalling LogP models.The QSM is a shared-memory model with only two parameters-p, the number of processors, and g, a bandwidth parameter. These features of the QSM make it a convenient model for parallel algorithmdesign, and the simple work-preserving emulations of QSM on BSP and LogP show that algorithms designed on the QSM will map well on to these other models. This presents a strong case for the use ofQSM as the model of choice for parallel algorithm design