About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Fall Joint Computer Conference 1985
Conference paper
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.