APPROXIMATION OF THE PROCESSING TIME FOR A RANDOM GRAPH MODEL OF A PARALLEL COMPUTATION.

Abstract

The task graph of a parallel computation is modeled by a random, acyclic, directed graph (K, p) where K is the number of nodes and p is the probability that an arc exists between two nodes (from a smaller numbered node to a larger one). In this model, each node corresponds to a task that is to be processed and each arc implies a precedence relationship that must be satisfied during processing. An approximation for the expected processing time of a task gaph of this type on an infinite number of processors is derived under the assumption that each task requires an exponentially distributed amount of processing. This approximation shows that the expected processing time grows linearly with K at the rate of 2p/(1 plus p). Furthermore, maximum likelihood estimators for the value of p given specified characteristics of a particular task graph are obtained.