Performance Trade-offs in Series-Parallel Programming

Arturo González Escribano, Arjan J.C. van Gemund, and Valentin Cardenoso Payo

Most parallel programming models allow the DAG that is associated with the program to have unrestricted topology. While attractive from problem parallelism expression point of view, the lack of topological restrictions, however, is unattractive from mapping and cost estimation point of view. Hence, a number of more structured programming models exist that essentially map to the subset of series-parallel (SP) DAGs which offer more ease of programming, mapping, and cost estimation. despite their obvious advantages, however, a critical question is to what extent the ability to express parallelism has been sacrificed by restricting parallelism to SP form. We provide emprirical and theoretical evidence that the loss of parallelism, although theoretically unlimited, is typically limited to a small factor.