Performance prediction for a class of parallel computations
Athar B. Tayyab · 1993
The main objective of this dissertation is development of approximate analytic models for performance prediction of a class of parallel computations executed on shared-memory multiprocessors. The models developed in this dissertation are useful for both qualitative and quantitative performance analysis and contribute significantly to the field. Previous studies in this area have considered a restricted set of parallel task systems such as parallel loops. For more complex structures such as partitioning or multiphased algorithms, the analyses have not considered the cost of enforcing intertask synchronization constraints and the effect of architectural features on this cost. The task graphs considered in this dissertation are more general than those previously studied in the literature and represent a large class of parallel computations. The models are solvable for a number of distribution functions and are applicable to shared-memory multiprocessors with significantly different architectural and synchronization performance characteristics. The models are based on a new formulation technique based on stochastic bound analysis. The formulation explicitly models the computation behavior, synchronization constraints, and the effect of architectural features on synchronization overheads. The performance models based on this formulation technique are much simpler than earlier queueing models and are solved using concepts and results from order statistics and extreme-value theory. The accuracy of the performance models is validated via measurements on different two shared-memory multiprocessor systems, a 24 processor Alliant FX/2800 and a 12 processor Encore Multimax. The results show the model to be quite accurate, even when some of the assumptions are violated. The analytic models are used to compare the performance of two different synchronization mechanisms for layered task systems, namely barriers and explicit intertask synchronization. A major conclusion is that the choice of a synchronization mechanism for layered task systems can dramatically impact the performance of such systems. Although the choice of a particular synchronization mechanism is dependent on various application and architectural features, a wide range of experiments and analysis show that barriers can be an efficient synchronization mechanism for layered task systems with even relatively small amount of intertask dependencies.