Title :
Stochastic bounds for parallel program execution times with processor constraints
Author_Institution :
Dept. of Math. & Comput. Sci., State Univ. of New York, New Paltz, NY, USA
fDate :
5/1/1997 12:00:00 AM
Abstract :
A parallel program can be modeled as an acyclic directed graph, where a node represents a task, which is the smallest grain of computation to be assigned to a processor, and arcs stand for precedence (synchronization) constraints among the tasks. Due to different input data and unpredictable dynamic run time environments, the execution times of tasks as well as the entire program can be treated as random variables. In this paper, we develop some stochastic lower and upper bounds for parallel program execution times when there are limited processors. Such analysis can provide important information for job scheduling and resource allocation. For several typical classes of parallel programs, we derive very accurate closed form approximations for the bounds. Examples are also given to demonstrate the quality of the bounds derived
Keywords :
directed graphs; parallel programming; processor scheduling; resource allocation; stochastic processes; acyclic directed graph; closed form approximations; dynamic run time environments; job scheduling; lower bounds; parallel program execution times; processor constraints; random variables; resource allocation; stochastic bounds; synchronization constraints; upper bounds; Algorithm design and analysis; Concurrent computing; Parallel processing; Performance analysis; Processor scheduling; Random variables; Resource management; Stochastic processes; Time factors; Upper bound;
Journal_Title :
Computers, IEEE Transactions on
