Performance-based quality measures for parallel software design
Robert Seymour Todd · 1994
The design of parallel software for shared memory architectures requires an iterative process of structuring, partitioning, allocating, and scheduling processing in such a way as to avoid idling processors while conflicting communication through critical sections is occurring. While each of these design activities has received considerable research attention, little is known about their interdependencies. Thus, the design process is fundamentally iterative. This study attempts to define performance-based quality measures for parallel software which will enable a designer to know how well his/her program will perform relative to a 'perfect' implementation, where the performance bottlenecks are, and whether extensive effort is likely to pay performance dividends. First, a perfect implementation is defined for both single- and a restricted class of multi-stage deterministic CFGs with various types of precedence. In this perfect implementation, the optimal number of processors, minimum execution time, and minimum wasted capacity are determined. Second, measures of quality based on these values are defined. Third, a design methodology based on these measures is presented. Lastly, a simulation implementing these ideas is described and the results presented and analysed. The primary results are that by viewing requirements as work and by defining work-based performance measures, it is possible to predict when design effort will pay performance dividends and when it will not. It is also possible to include the relative merits of time cost, processor requirements, and processor utilization to compare competing designs and to begin a study of the interaction of the various design activities.