TY - GEN
T1 - The influence of random delays on parallel execution times
AU - Adve, Vikram Sadanand
AU - Vernon, Mary K.
PY - 1993/6/1
Y1 - 1993/6/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84892843266&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84892843266&partnerID=8YFLogxK
U2 - 10.1145/166955.166982
DO - 10.1145/166955.166982
M3 - Conference contribution
AN - SCOPUS:84892843266
T3 - Proceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993
SP - 61
EP - 73
BT - Proceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993
PB - Association for Computing Machinery, Inc
T2 - 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993
Y2 - 10 May 1993 through 14 May 1993
ER -