Emulations between QSM, BSP and LogP: A framework for general-purpose parallel algorithm design

We present work-preserving emulations with small slowdown between LogP and two other parallel models: 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. Our results 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 – Ô, the number of processors, and �, a bandwidth parameter. The simplicity of the QSM parameters makes QSM a convenient model for parallel algorithm design, and simple work-preserving emulations of QSM on BSP and QSM on LogP show that algorithms designed for the QSM will also map quite well to these other models. The simplicity and generality of QSM present a strong case for the use of QSM as the model of choice for parallel algorithm design. We present QSM algorithms for three basic problems – prefix sums, sample sort and list ranking. Using appropriate cost measures, we examine the predicted and simulated performance of these algorithms. These results suggest that QSM analysis will predict algorithm performance quite accurately for problem sizes that arise in practice