Problem space promotion and its evaluation as a technique for efficient parallel computation
Bradford L. Chamberlain, E. Christopher Lewis, Lawrence Snyder · 1999
In this paper we describe a parallelprogrammingparadigm called problem space promotion (PSP), a technique that increases parallelism by reducing communication and synchronization.We present four algorithms that exploit PSP and evaluate their communication characteristics relative non-PSP solutions.Our analysis is aided by the use ofparallel algorithm notation that is concise, yet accurately reflects parallelism and communication costs.Our analysis illustrates circumstances under which the use of PSP is benejcial and detrimental to performance, and experiments on the Cray T3E attest to the validity of the analysis.We find that PSP can signtficantly improve the per$ormance and scaling behavior of certain computations, even when compared to existing high quality parallel algorithms.