Stochastic performance models of parallel task systems (extended abstract)

• Main Authors: Tayyab, Athar B., Kuhl, Jon G.
• Format: Conference Proceeding
• Language: English
• Subjects: Computing methodologies > Modeling and simulation > Model development and analysis; Computing methodologies > Modeling and simulation > Model development and analysis > Model verification and validation; Computing methodologies > Parallel computing methodologies > Parallel programming languages; General and reference > Cross-computing tools and techniques > Performance; Mathematics of computing > Discrete mathematics > Graph theory > Network flows; Social and professional topics > Professional topics > Management of computing and information systems > Software management > Software selection and adaptation; Software and its engineering > Software notations and tools > General programming languages > Language types > Parallel programming languages; Software and its engineering > Software organization and properties > Extra-functional properties > Software performance; Theory of computation > Design and analysis of algorithms > Graph algorithms analysis > Network flows; Theory of computation > Models of computation > Probabilistic computation; Theory of computation > Randomness, geometry and discrete structures
• ISSN: 0163-5999
• DOI: 10.1145/183018.183054

This paper considers the class of parallel computations represented by directed, acyclic task graphs. These include parallel loops, multiphase algorithms, partitioning and merging algorithms, as well as any arbitrary parallel computation that can be structured by a task graph. The paper reviews the current state of the art in stochastic bound models of parallel programs and presents new stochastic bound performance models that predict the expected execution time of parallel programs on a given shared-memory multiprocessor system; and provide qualitative and quantitative description of the relationships between the structure of parallel programs, computation and synchronization behavior of the program, and architectural features of the underlying multiprocessor system. The models use a new formulation based on stochastic bound analysis and are solvable for a number of distribution functions. They are applicable to shared-memory multiprocessors with significantly different architectural and synchronization performance characteristics. The accuracy of the models is validated via several measurements on two different shared-memory multiprocessor systems, the Alliant FX/2800 and the Encore Multimax. The results show the models to be quite accurate, even when some of the modeling assumptions are violated. The maximum error of prediction ranges from about 10% to under 1%.