Architecture-Independent Locality Analysis and Efficient PRAM Simulations

摘要

The Parallel Random Access Machine(PRAM) model remains ubiquitous in the-oretical parallel algorithm design and analysis. The architectural challenge of producing a PRAM-a genuinely scalable machine with unit communication costs-has not been resolved. The Bulk Synchronous Parallel (BSP) model provides high level abstraction of parallel architectures, whilst allowing architecture-independent programs to deliver scalable performance. Our contribution is to unify the appraoches into a single parallel programming rframework. For a survey of previous approaches, and the BSP model, see (LS96).