Title :
Stochastic bounds on execution times of parallel computations
Author :
Presti, F. Lo ; Colajanni, M. ; Tucci, S.
Author_Institution :
Dipartimento Ingegneria Elettronica, Rome Univ., Italy
fDate :
31 Jan-2 Feb 1994
Abstract :
We obtain stochastic bounds on execution times of parallel computations assuming ideal conditions for shared resources. A parallel computation is modelled as a task system with precedence constraints expressed as a directed acyclic graph (DAG). The task execution times are assumed independent random variables. The performance measure considered is the overall execution time of the computation. To obtain upper bounds on this measure, we apply stochastic ordering and stochastic comparison techniques
Keywords :
directed graphs; parallel programming; stochastic processes; DAG; directed acyclic graph; execution times; independent random variables; parallel computations; performance measure; precedence constraints; shared resources; stochastic bounds; stochastic comparison techniques; stochastic ordering; task system; Computational modeling; Concurrent computing; Distributed computing; Equations; Random variables; Stochastic processes; Time measurement; Time sharing computer systems; Upper bound;
Conference_Titel :
Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 1994., MASCOTS '94., Proceedings of the Second International Workshop on
Conference_Location :
Durham, NC
Print_ISBN :
0-8186-5292-6
DOI :
10.1109/MASCOT.1994.284380
