Average Execution Times of Series–Parallel Networks

W. J. Gutjahr and G. Ch. Pflug Institute of Statistics and Computer Science University of Vienna

Abstract

The papers investigates a model for series–parallel processing structures developed by E. Gelenbe. We show that, under the so–called combinatorial distribution assumption, the average total execution time of a series–parallel processing structure cannot grow essentially slower than n^{1/2}, where n is the number of primitive tasks in the structure.

1 Introduction

Since MacMahon’s article [7], published exactly a hundred years ago, series–parallel networks have found continuous interest among combinatorialists (a survey and some new results are given in Moon [8]). In the present paper, we study a combinatorial parameter of such networks which plays an important role in the analysis of partially parallel processing structures.

In [2], chapter 5, Gelenbe develops a model for series–parallel processing structures. He supposes that a program is composed of (primitive) tasks; some of them are to be performed in series, others may be performed in parallel. The execution times of the tasks are independent identically distributed random variables. The question is: what can be said about the execution time of the whole program?

Obviously, an answer to this question will not only depend on the execution time distribution of a task, but also on the assumed distribution of processing structures. If we consider the processing structure as (deterministically) given, then the derivation of properties of the total execution time is a computational problem. This is the usual viewpoint in the theory of project planning, where processing structures with random execution times of primitive tasks are represented by PERT–networks. Recent results on this version of the problem can be found in Yazici-Pekergin and Vincent [9].

In Gelenbe’s model, however, also the processing structure is considered as a random variable. He assumes that the structure originates as the result of a branching process (which models stepwise refinement of a program). Given the execution time distribution of a task and the characteristic parameters of the branching process, Gelenbe shows how to compute numerically the execution time distribution of the program.

This approach has two drawbacks:

• It does not supply information on the average total execution time, since there is no way to determine the (infinite) tail of the distribution.

• As the result of the branching process, processing structures of different size may occur. Their properties get “mixed” in the model. One does not obtain information on the behavior of processing structures of a given size n.

In this paper, we follow the usual line of investigation in the average case analysis of algorithms (see e. g. Kemp [5]): The average performance of the system is studied as a function of the “problem size” n, with the emphasis on the examination of the asymptotic behavior of this function. Applied to the present problem, this approach means that we have to condition the processing structure resulting from Gelenbe’s branching process on a fixed size n.

(Series–parallel) processing structures will be represented by series–parallel networks:

Definition 1.1. A series–parallel network (abbreviated SPN) is defined by:

(i) A task, denoted by □, is a SPN.

(ii) If N_{1}, …, N_{k} (k ≥ 2) are SPNs, then also series (N_{1}, …, N_{k}) and parall (N_{1}, …, N_{k}) are SPNs.

series (N_{1}, …, N_{k}) resp. parall (N_{1}, …, N_{k}) means that N_{1}, …, N_{k} are executed in series resp. in parallel.

We measure the size of an SPN by the number of tasks contained in it. For example, series (parall (□, □, □), □) is an SPN of size 4.

Without loss of generality, we may confine ourselves to SPNs where the operations “series” and “parall” always have exactly two operands. For example, the SPN series (N_{1}, …, N_{4}) may also be represented as

series (N_{1}, series (N_{2}, series (N_{3}, N_{4}))).

(Clearly, this representation is not unique.)

An SPN with this restriction may be represented in an obvious way by a binary tree, where the operations “series” and “parall” are internal nodes, and the tasks are leaves.

Gelenbe’s probabilistic model, applied to SPNs of the described “binary” type, is the following:

a) Start with an unspecified symbol ×.

b) Replace each ×

– by □ with probability 1 − w,

– by parall (×, ×) with probability αw,

– by series (×, ×) with probability (1 − α)w.

(0 < w < 1, 0 ≤ α ≤ 1).

If w < 1/2, w = 1/2 and w > 1/2, this yields a subcritical, critical and supercritical binary splitting process, respectively (cf. Jagers [4], p. 20). In the subcritical and in the critical case, the resulting SPN is almost surely finite.

α may be interpreted as the degree of parallelism.

It can be shown (cf. Kolchin [6], Aldous [1], Gutjahr [3]) that conditioning the family tree of a Galton–Watson branching process to a fixed number m of nodes leads to uniform distribution on the family of trees with m nodes (the so–called combinatorial distribution model). Since in binary trees with n leaves the total number of nodes is m = 2n − 1, we obtain uniform distribution in our case also by conditioning on n leaves. So our distribution model can be described as follows:

• Choose a binary tree with n leaves (each such tree being equally likely),

• assign “parall” or “series” to its internal nodes, independently with probabilities α resp. 1 − α.

2 Growth of the average total execution time

Now let F_{0} denote the distribution of the execution time of a single task, given by its distribution function. First of all, we consider the case where F_{0} is the point mass in 1, i. e. we assume deterministic execution time 1 for each task. If one knows the SPN N, then the total execution time τ of N can be computed recursively in the following way:

τ(□) = 1,  (1)
τ (parall (N_{1}, N_{2})) = max (τ( N_{1}), τ( N_{2})),  (2)
τ (series (N_{1}, N_{2})) = τ( N_{1}) + τ( N_{2}).  (3)

For a binary tree t, let τ̄(t) be the expected value of τ(N) for all SPNs N whose tree structure is t. In other words, τ̄(t) is obtained by taking the expected value of τ(N) for all different assignments of “parall” resp. “series” to the internal nodes of t, weighted by their probabilities.

Definition 2.1. We denote by e_{n} the average value of τ̄ for all binary trees with n leaves. Thus, e_{n} is the average total execution time of SPNs of size n in our model.

For rational α = p/q (p, q integers), it is possible to compute e_{n} by means of a recursion: The numbers a_{n,k} of SPNs N of size n with τ(N) ≤ k are given recursively by

a_{n,k} = ∑_{j=1}^{n−1} {pa_{j,k}a_{n−j,k} + (q − p) ∑_{l=1}^{k−1}(a_{j,l} − a_{j,l−1})a_{n−j,k−l}} (n > 1, 1 ≤ k ≤ n),

a_{n,0} = 0 (n ≥ 1),
a_{n,k} = a_{n,n} (n > 1, k > n),
a_{1,k} = 1 (k ≥ 1),

and one easily finds

e_{n} = n − \frac{1}{a_{n,n}} ∑_{k=1}^{n−1} a_{n,k}.

Hence the numbers e_{n} can be computed numerically. For α = 1/2, e. g., one obtains:

\begin{matrix}n & 10 & 20 & 30 & 40 & 50 & 60 & 70 & 80 \\ e_{n} & 4.989 & 8.598 & 11.866 & 14.929 & 17.852 & 20.667 & 23.395 & 26.051 \end{matrix}

It would be tempting to derive (e. g. by generating function methods) information on the asymptotic behavior of (e_{n}) from the recursion above, but this seems to be very difficult. So we follow another approach. We try to “translate” information on τ̄ from the corresponding unconditioned branching process (the binary splitting process described in Section 1) to the size–conditioned process.

The same approach can be applied to a far more general class of problems (see Gutjahr [3]). We shall use the following relation, which is proved in [3]:

Lemma 2.1. Let Π be a function assigning to each binary tree t a real value Π(t). Let e^{crit} be the expected value of Π(t) for family trees t of a critical binary splitting process, and let e_{n} be the expected value of Π(t) for binary trees t with n leaves, where each such tree has the same probability. Then

∑_{n=1}^{∞} e_{n}n^{−3/2} < ∞ iff e^{crit} < ∞.

We apply this lemma to the function Π = τ̄ defined above (such that Definition 2.1 is consistent with the definition of e_{n} in Lemma 2.1). This makes it possible to derive a kind of asymptotic upper bound for the growth of the numbers e_{n}. In order to formulate the result, the following definition is useful:

Definition 2.2. The growth exponent η of a series (e_{n}) of real numbers is the number

η = inf{y : e_{n} = O(n^{y}) (n → ∞)}.

For the proof of the result, we need a technical lemma concerning the recursion

a_{k+1} = a_{k}(1 − γa_{k}),  (4)

which resembles the famous logistic recursion

a_{k+1} = γa_{k}(1 − a_{k})

investigated in biodynamics and chaos theory.

Lemma 2.2. Let γ > 0. For the numbers a_{k} defined by (4) and by an initial value a_{1} with 0 < a_{1} ≤ 1/(2γ), the estimation

a_{k} > a_{2}/k (k ≥ 1)

holds. Proof. Let

f(x) = x(1 − γx).  (5)

f(x) is increasing in the interval [0, 1/(2γ)]. We show by induction a_{k} ≤ 1/(kγ) (k ≥ 2). The case k = 2 is clear. For k ≥ 2, one finds

a_{k+1} = f(a_{k}) ≤ f (\frac{1}{kγ} ) ≤ \frac{1}{(k + 1)γ} .

Next, we show by induction a_{k} ≥ a_{2}/(k − 1) (k ≥ 2). k = 2 is clear again. For k ≥ 2,

a_{k+1} ≥ a_{k}(1 − γ/(kγ)) ≥ a_{2}/k = a_{2}/((k + 1) − 1).

Hence

a_{k} > a_{2}/k (k ≥ 2),

and evidently a_{1} > a_{2}.

Theorem 2.1. For each degree of parallelism α < 1, the average total execution times e_{n} given by Definition 2.1 have a growth exponent η ≥ 1/2.

Proof. The case α = 0 is clear, so assume 0 < α < 1. Because of Lemma 2.1, it is sufficient to show that e^{crit} = ∞, since ∑ e_{n}n^{−3/2} = ∞ implies that e_{n} = O(n^{y}) cannot hold for an exponent y < 1/2. Consider the critical binary splitting process. The start symbol × is replaced by the symbol □ with probability 1/2, by parall (×, ×) with probability α/2, and by series (×, ×) with probability (1 − α)/2. If the start symbol is “split”, i. e. not replaced by □, then the branching processes starting with the left resp. the right successor of the root are identical in distribution to the original binary splitting process. This yields the following recursion for the distribution function of the total execution time:

F (k) = \frac{1}{2} + \frac{α}{2} F (k)^{2} + \frac{1 − α}{2} (F ∗ F) (k) (k ≥ 1),  F (0) = 0,  (6)

where ∗ denotes the convolution of distribution functions. Since τ(N) ≥ 1, one has

τ( N_{1}) + τ( N_{2}) ≥ max (τ( N_{1}), τ( N_{2})) + 1.

It will be shown that we get infinite average total execution time even if, in the definition of τ, we replace (3) by

τ (series (N_{1}, N_{2})) = max(τ( N_{1}), τ( N_{2})) + 1.  (7)

By this replacement, (6) turns into

F (k) = \frac{1}{2} + \frac{α}{2} F (k)^{2} + \frac{1 − α}{2} F (k − 1)^{2} (k ≥ 1),  F (0) = 0.  (8)

Solution of the quadratic equation yields

F (k) = \frac{1}{α} (1 − \sqrt{1 − α} · \sqrt{1 − α F (k − 1)^{2}}) .  (9)

With g_{k} = 1 − F (k), the expected value of a random variable with distribution F is finite iff ∑ g_{k} < ∞. In terms of g_{k}, (9) reads

g_{k+1} = β [\sqrt{1 + (2g_{k} − g_{k}^{2}) / β} − 1] ,  (10)

where β = (1 − α)/α (0 < β < ∞).

It is not difficult to show that the solution F of the functional equation (8) exists and that F is a distribution function. Hence g_{k} ↓ 0 (k → ∞). Expansion of the square root in (10) and some straightforward lower bound estimations lead to

g_{k+1} ≥ g_{k}(1 − γg_{k}),  (11)

where γ = (β + 1)/(2β).

Because of g_{k} ↓ 0, there is an m such that g_{m+1} ≤ 1/(2γ). Let (a_{k}) be the numbers defined by (4) with a_{1} = g_{m+1}. We show by induction that g_{m+l} ≥ a_{l} (l ≥ 1). With f given by (5),

g_{m+l+1} ≥ g_{m+l} (1 − γg_{m+l}) = f(g_{m+l}).

Because of g_{m+l} ≤ g_{m+1} ≤ 1/(2γ) and of f increasing in [0, 1/(2γ)],

f(g_{m+l}) ≥ f(a_{l}) = a_{l+1}.

So g_{m+l} ≥ a_{l} has been shown for all l.

Lemma 2.2 yields

a_{l} > a_{2}/l = c/l

with c = f(g_{m+1}). Thus also

g_{m+l} ≥ c/l,

and hence ∑ g_{k} diverges.

Now we return to the more general case of an arbitrary execution time distribution for the single tasks.

Corollary. Let the distribution F_{0} of the execution time of a primitive task be arbitrary, except the point mass in zero, and α < 1. Then Theorem 2.1 still holds.

Proof. Since F_{0} is not the point mass in 0, there is an ϵ > 0 such that F_{0}(ϵ) < 1. Without loss of generality one may assume ϵ = 1 (otherwise use another unit of time). Then if we replace F_{0} by the Bernoulli distribution with p = 1 − F_{0}(1), all average execution times will decrease (or at least remain constant). In this case we may use the “best case estimation”

τ (series (N_{1}, N_{2})) = \{ \begin{matrix}max(τ(N_{1}), τ(N_{2})) + 1 & if τ(N_{1}) > 0, τ(N_{2}) > 0, \\ max(τ(N_{1}), τ(N_{2})) & otherwise \end{matrix}

instead of (7). This leads to

F (k) = \frac{1}{2} + \frac{α}{2} F (k)^{2} + \frac{1 − α}{2} \{(1 − F (0))^{2} · F (k − 1)^{2} + [1 − (1 − F (0))^{2}] · F (k)^{2}\} (k ≥ 1)

and

F (0) = \frac{1}{2}(1 − p) + \frac{1}{2}F (0)^{2}.

Hence

F (k) = \frac{1}{2} + \frac{α̃}{2} F (k)^{2} + \frac{1 − α̃}{2} F (k − 1)^{2} (k ≥ 1), F (0) = 1 − \sqrt{p},

with α̃ = α + (1 − α)(1 − p). As in the proof of Theorem 2.1 one shows that F has infinite expectation.

Without proof we remark that in the case α = 1 (pure parallelism), the growth exponent is not always ≥ 1/2; it turns out that for α = 1 the numbers e_{n} have a growth exponent η ≥ 1/2 iff

∫_{0}^{∞} \sqrt{1 − F_{0}(t)} dt = ∞.

3 Conclusion

Theorem 2.1 and its corollary yield only rough information on the growth of the average total execution times. Nevertheless, it seems remarkable that the result holds for arbitrary primitive execution time distribution F_{0} and for any degree of parallelism α < 1. Informally speaking, we have shown that the average total execution times of series–parallel processing structures cannot grow essentially slower than n^{1/2}, where n is the number of primitive tasks contained in the processing structure. In the purely sequential case (α = 0), the average total execution time is of order n. So our result states that in the indicated situation a speed–up of an order larger than n^{1/2} cannot be expected — even if an unlimited number of processors is available, no memory conflicts occur, the communication overhead is negligible and the degree of parallelism is high.

As to the mathematical technique of our investigation, we used a branching process approach which can also be applied to other recursively defined structures under the combinatorial distribution model.

References

[1] D. J. Aldous, The continuum random tree II: an overview, Proc. Durham Symp. Stochastic Analysis 1990, Cambridge University Press (1991), 23 – 70.

[2] E. Gelenbe, Multiprocessor Performance, Wiley (1989).

[3] W. J. Gutjahr, Expectation transfer between branching processes and random trees, accepted for publication in: Random Structures and Algorithms.

[4] P. Jagers, Branching Processes with Biological Applications, Wiley (1975).

[5] R. Kemp, Fundamentals of the Average Case Analysis of Particular Algorithms, Wiley– Teubner Series in Computer Science (1984).

[6] V. F. Kolchin, Random Mappings, Optimization Software, New York (1986).

[7] P. A. MacMahon, The combination of resistances, The Electrician 28 (1892), 601 – 602.

[8] J. W. Moon, Some enumerative results on series–parallel networks, Annals of Discrete Mathematics 33 (1987), 199 – 226.

[9] N. Yazici-Pekergin and J.-M. Vincent, Stochastic bounds on execution times of parallel programs, IEEE Trans. Software Eng. 17 (1991), 1005 – 1012.