The influence of random delays on parallel execution times

Vikram Sadanand Adve, Mary K. Vernon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Stochastic models are widely used for the performance evaluation of parallel programs and systems. The stochastic assumptions in such models are intended to represent non-deterrninistic processing requirements as well as random delays due to inter-process communication and resource contention. In this paper, we provide compelling analytical and experimental evidence that in current and foreseeable shared-memory programs, communication delays introduce negligible variance into the execution time between synchronization points. Furthermore, we show using direct measurements of variance that other sources of randomness, particularly non-deterministic computational requirements, also do not introduce significant variance in many programs. We then use two examples to demonstrate the implications of these results for parallel program performance prediction models, as well as for general stochastic models of parallel systems.

Original languageEnglish (US)
Title of host publicationProceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993
PublisherAssociation for Computing Machinery, Inc
Pages61-73
Number of pages13
ISBN (Electronic)0897915801, 9780897915809
DOIs
StatePublished - Jun 1 1993
Externally publishedYes
Event1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993 - Santa Clara, United States
Duration: May 10 1993May 14 1993

Publication series

NameProceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993

Other

Other1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993
CountryUnited States
CitySanta Clara
Period5/10/935/14/93

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The influence of random delays on parallel execution times'. Together they form a unique fingerprint.

Cite this