skip to main content
10.1145/183018.183054acmconferencesArticle/Chapter ViewAbstractPublication PagesmetricsConference Proceedingsconference-collections
Article
Free access

Stochastic performance models of parallel task systems (extended abstract)

Published: 01 May 1994 Publication History

Abstract

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%.

References

[1]
Athar B Tayyab. Performance Prediction for a Clare o:f Parall~t Computations. Ph D Dissertation, The University of Iowa. Iowa City, IA, August, 1993.]]
[2]
N Yazici-Pekergm and J-M Vincent, "'Stochasue Bounds on Execution Times of Parallel Programs", IEEE Transa,:ttons on Software Engineering, vol SE-}7, No 10, Oct 1991, pp 1005- 1012]]
[3]
T.S Axelrod, "Effects on Synchronization Barriers on Multiprocessor Performance," Parallel Computing, Vol. 3, 1986]]
[4]
Carl J Beckmann and Constantine D Polychronopoulos, "The Effect of Barrier Synchronization and Scheduhng Overhead on Parallel Loops," Internattonal Conference on Parallel Processtng, Vol II, August 1989, pp 200-204.]]
[5]
L. Brochard. J-P Prost. and F Faurie, "Synchronization and Load Unbalance Effects of Parallel Iterative Algorithms", 1989 Internattonal Conference on Parallel Processing, August, 1989, Vol III, pp. 153- 160]]
[6]
C Kruskal and A Weiss, "Allocating Independent Subtasks on Parallel Processors," in Proceedtngs of the 1984 International Conference on Parallel Processing, August, 1984, pp 236-240]]
[7]
Sridhar Madata and James B. Sinclair, "Performance of Synchronous Parallel Algor, thms with Regular Structures" IEEE Transacttons on Parallel and Distributed Systems, Vol 2, No 1, January 1991, pp 105-116.]]
[8]
Constantine D. Polychronopoulos and Utpal Banerjee, "Processor Allocation for Horizontal and Vertical Parallelism and Related Speedup Bounds," IEEE Transacttons on Computers, Vol C-36, No, 4, Apml 1987, pp 410-420]]
[9]
John T Robinson, "Some Analysis Techniques for Asynchronous Multiprocessor Algorithms." IEEE Transactton on Software Engmeermg, Vol SE-5, No 1, January 1979, pp 24-31]]
[10]
Athar B Tayyab and Jon G, Kuhl, "Analyzing Performance of Sequenc,ng Mechamsm~ for Simple Layered Task Systems," Proceedings of the 6th lnrernattonal Sympostum on Parallel Procezsms~ Beverly Hill, CA, March, I992~ pp. 173-178.]]
[11]
Athar B. Tayyab and Jon G. Kuhl, "Experimental Validation of a Performance Model for Simple Layered Task Systems," in the Proceedings of the 22nd Internattonal Conference on Parallel Processing, Vol I, St Charles, IL, August, 1993, pp. 197-201]]

Cited By

View all
  • (2018)Performance modeling and analysis of correlated parallel computationsParallel Computing10.1016/j.parco.2008.05.00234:9(521-538)Online publication date: 31-Dec-2018
  • (2009)Performance under Failures of DAG-based Parallel ComputingProceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid10.1109/CCGRID.2009.55(236-243)Online publication date: 18-May-2009
  • (1997)Performance analysis for parallel solutions to generic search problemsProceedings of the 1997 ACM symposium on Applied computing10.1145/331697.332327(422-430)Online publication date: 1-Apr-1997
  • Show More Cited By

Index Terms

  1. Stochastic performance models of parallel task systems (extended abstract)

                      Recommendations

                      Comments

                      Information & Contributors

                      Information

                      Published In

                      cover image ACM Conferences
                      SIGMETRICS '94: Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems
                      May 1994
                      294 pages
                      ISBN:089791659X
                      DOI:10.1145/183018
                      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                      Sponsors

                      Publisher

                      Association for Computing Machinery

                      New York, NY, United States

                      Publication History

                      Published: 01 May 1994

                      Permissions

                      Request permissions for this article.

                      Check for updates

                      Qualifiers

                      • Article

                      Conference

                      SIGMETRICS94
                      Sponsor:

                      Acceptance Rates

                      Overall Acceptance Rate 459 of 2,691 submissions, 17%

                      Contributors

                      Other Metrics

                      Bibliometrics & Citations

                      Bibliometrics

                      Article Metrics

                      • Downloads (Last 12 months)47
                      • Downloads (Last 6 weeks)15
                      Reflects downloads up to 30 Jan 2025

                      Other Metrics

                      Citations

                      Cited By

                      View all
                      • (2018)Performance modeling and analysis of correlated parallel computationsParallel Computing10.1016/j.parco.2008.05.00234:9(521-538)Online publication date: 31-Dec-2018
                      • (2009)Performance under Failures of DAG-based Parallel ComputingProceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid10.1109/CCGRID.2009.55(236-243)Online publication date: 18-May-2009
                      • (1997)Performance analysis for parallel solutions to generic search problemsProceedings of the 1997 ACM symposium on Applied computing10.1145/331697.332327(422-430)Online publication date: 1-Apr-1997
                      • (1997)Minimizing communication conflicts with load-skewing task assignment techniques on network of workstationsProceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)10.1109/ISPAN.1997.645107(268-274)Online publication date: 1997
                      • (1997)Estimating the execution time distribution for a task graph in a heterogeneous computing systemProceedings Sixth Heterogeneous Computing Workshop (HCW'97)10.1109/HCW.1997.581419(172-184)Online publication date: 1997
                      • (2000)Load-skewing task assignment to minimize communication conflicts on network of workstationsParallel Computing10.1016/S0167-8191(99)00102-726:2-3(179-197)Online publication date: 1-Feb-2000
                      • (2000)A hierarchical approach for bounding the completion time distribution of stochastic task graphsPerformance Evaluation10.1016/S0166-5316(99)00054-141:1(1-22)Online publication date: 1-May-2000

                      View Options

                      View options

                      PDF

                      View or Download as a PDF file.

                      PDF

                      eReader

                      View online with eReader.

                      eReader

                      Login options

                      Figures

                      Tables

                      Media

                      Share

                      Share

                      Share this Publication link

                      Share on social media