F. Afrati et A. Stafylopatis, PERFORMANCE CONSIDERATIONS ON A RANDOM GRAPH MODEL FOR PARALLEL-PROCESSING, Informatique theorique et applications, 27(4), 1993, pp. 367-388
Consider a random directed acyclic graph (dag) with nodes 1, 2, ..., n
, and an edge from node i to node j (only if i >j) with fixed probabil
ity p. Such a graph can be thought of as the task graph associated wit
h a job and thus it serves as a parallel processing model; the vertice
s correspond to tasks and the edges correspond to precedence constrain
ts between tasks. In this case, the length of the graph corresponds to
the parallel processing time of the job (an infinite number of availa
ble processors is assumed) and the width of the graph corresponds to t
he parallelism of the job. We estimate here the average length of the
random dag (that is, the average processing time of the job) as a func
tion of the probability p and the number of tasks n hy establishing ti
ght lower and upper bounds. The lower (resp. upper) bound is determine
d as being equal to the average length of a random dag considerably si
mpler to manipulate than the original one. Furthermore, the asymptotic
behaviour of the average length is studied and the results obtained i
mprove previously published results. Finally, asymptotic results are o
btained concerning the average width of the task graph; it is shown th
at the average width tends to 1/p as n --> infinity.