Stochastic bounds on execution times of parallel programs

Author

Yazia-Pekergin, N. ; Vincent, Jean-Marc

Author_Institution

EHEI, Rene Descartes, Paris, France

Volume

17

Issue

10

fYear

1991

fDate

10/1/1991 12:00:00 AM

Firstpage

1005

Lastpage

1012

Abstract

Stochastic bounds are obtained on execution times of parallel programs when the number of processors is unlimited. A parallel program is considered to consist of interdependent tasks with synchronization constraints. These constraints are described by an acyclic directed graph called a task graph. The execution times of tasks are considered to be independently identically distributed (i.i.d.) random variables. The performance measure of interest is the overall execution of the considered parallel program (task graph). Stochastic bound methods are applied to obtain lower and upper bounds on this measure. Another upper bound is obtained for parallel programs having `new better than used in expectation´ (NBUE) random variables as task execution times. NBUE random variables are replaced with exponential random variables of the same mean to derive this upper bound

Keywords

directed graphs; parallel programming; performance evaluation; stochastic processes; NBUE; acyclic directed graph; execution times; exponential random variables; interdependent tasks; parallel programs; performance measure; stochastic bound methods; synchronization constraints; task graph; Distributed computing; Equations; Parallel processing; Probability distribution; Random variables; Stability analysis; Stochastic processes; Stochastic systems; Tree graphs; Upper bound;

fLanguage

English

Journal_Title

Software Engineering, IEEE Transactions on

Publisher

ieee

ISSN

0098-5589

Type

jour

DOI

10.1109/32.99189

Filename

99189