Proposed Running Head: \Emulations Between QSM, BSP and LogP"

We present work-preserving emulations with small slowdown between LogP and two other parallel models: BSP and QSM. In conjunction with earlier work-preserving emula-tions 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 re-ported 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 pro-cessors, and g, 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 { prex sums, sample sort and list ranking. We show that these algorithms are optimal in terms of both the total wor