Inherent Limitations on Parallel Program Performance

Abstract

We analyse the inherent performance of parallel software. For this end we use a task graph to model software structure, and apply measures of performance based on the graph?s execution time, given enough processors. The task graph consists of tasks and precedence constraints between tasks: we show that performance cannot be improved by adding constraints to a task graph. Using this we derive known bounds on performance in a systematic manner by comparing the structure of a program to benchmark structures for which performance can be easily determined. Further, we simplify these bounds to highlight the importance of some summary parameters of the precedence structure. To conclude we examine an existing model of families of programs. We find bounds on performance within a family and simplify them by restricting the family specification. These bounds yield interesting insights into the scaled performance model of Gustafson, which models the effect of increasing the number of processors in tandem with program size.