RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

The complexity
of parallel evaluation
of linear recurrences

Laurent
L. Hyafil, H.T. Kung

Rapport de Recherche n° 96

Janvier 1975
THE COMPLEXITY OF PARALLEL EVALUATION
OF LINEAR RECURRENCES

L. Hyafil - H.T. Kung

Résumé

Nous nous intéressons à l'évaluation de $x_n$ défini par

$$x_i = x_{i-1} b_i + a_{i+1} \quad i \ge 1, x_0 = a_1$$

ou ce qui revient au même, à l'évaluation de l'expression de Horner

$$(... (a_1 b_1 + a_2 b_2 + ... + a_n b_n) + a_{n+1},$$

Nous montrons que le coefficient d'accélération obtenu sur un ordinateur idéalisé utilisant k processeurs en parallèle, est au plus $\frac{2}{k} + \frac{1}{3}$ (plutôt que k). D'après un résultat de S. Winograd on sait que cette borne est très fine.

This research was supported in part by IRIA, France, and in part by
the National Science Foundation under Grant GJ32111 and the Office
of Naval Research under Contract N0014-67-A-0314-0010, NR 044-422.
Much of this work was carried out at IRIA, while H. T. Kung was
visiting there in the summer of 1974.

L. Hyafil
IRIA-Laboria
78150 Rocquencourt, France

H. T. Kung
Department of Computer Science
Carnegie-Mellon University
Pittsburgh, Pa. 15213
ABSTRACT

The problem of evaluating $x_n$ defined by the linear recurrence

$$x_i = x_{i-1} + a_{i+1}, \quad i \ge 1, x_0 = a_1,$$

or, equivalently, evaluating the Horner expression,

$$(... (a_1 b_1 + a_2 b_2 + ... + a_n b_n) + a_{n+1},$$

is considered. It is shown that by using an idealized k-processor parallel computer, the speed-up for the problem is at most $\frac{2}{3}k + \frac{1}{3}$ rather than k. The bound is known to be essentially sharp by a result of S. Winograd.

1. INTRODUCTION

The concept of computers such as C.mmp and ILLIAC IV is to achieve computational speed-up by performing several operations simultaneously with parallel processors. This type of computer organization is referred to as a parallel computer. In this paper, we prove upper bounds on speed-ups achievable by parallel computers for a particular problem, the solution of first order linear recurrences. We consider this problem because it is important in practice and also because it is simply stated so that we might obtain some insight into the nature of parallel computation by studying it.

Consider a k-processor parallel computer. It is understood that because of possible memory conflicts, delays due to inter-processors communication, etc., k-fold speed-up is rarely achieved. In this paper, we show that the speed-up for a linear recurrence problem is at most $\frac{2}{3}k + \frac{1}{3}$, even under the assumption that the k-processor machine is idealized so that there are no memory conflicts or communication delays. By a result of Winograd [74], the bound $\frac{2}{3}k + \frac{1}{3}$ can be shown to be almost the best possible. Of course, the actual speed-up obtained from a real k-processor machine would be $\le \frac{2}{3}k + \frac{1}{3}$. The difference between $\frac{2}{3}k + \frac{1}{3}$ and k is rather significant. For example, if k = 16, 64, then the speed-up for the problem is at most 11, 43, respectively, no matter how efficient the k-processor machine is.

This result tells us that there are some inherent constraints of the linear recurrence problem, independent of machine, which prevent us from getting the k-fold speed-up. A related result in Kung [74] states that many nonlinear recurrences can be sped up at most by a constant factor, no matter how many processors are used. Hence nonlinear recurrences are even more constrained than linear ones. We believe that the study of these constraints is fundamental for understanding parallel computation.

A graph representation of parallel algorithms is given in the next section. In Section 3 we state the results of this paper and discuss their significance. The proof of our main theorem (Theorem 1) is given in Section 4. An illustration of the algorithm used in the proof of Theorem 1', a generalized
version of Theorem 1, is provided in the Appendix.

## 2. MODEL OF COMPUTATION

Let $\lambda$ be an infinite field and $a_i, b_i, i = 1, 2, \dots$ indeterminates over $\lambda$. Suppose that we perform computations in the extension field $\lambda(a_1, b_1, a_2, b_2, \dots)$. We consider the problem of evaluating rational expressions $E$ in $\lambda(a_1, b_1, a_2, b_2, \dots)$ given an input set $I$ such that $\{a_1, b_1, a_2, b_2, \dots\} \cup \lambda \subseteq I \subseteq \lambda(a_1, b_1, a_2, b_2, \dots)$. (The recurrence considered in this paper in fact is an expression $E$ of a special form. See Section 3.)

An algorithm for evaluating $E$ given $I$ is defined by a directed acyclic graph such that:

a. The in-degree of any node is either zero or two. A node whose in-degree is zero is called an *input node*.

b. There exists exactly one node whose out-degree is zero, and it is called the *output node*. The out-degree of any other node is $\ge 1$.

c. Each input node contains a value which is an element from the input set $I$. Each of the rest of the nodes contains an operation, $+$, $-$, $\times$ or $/$ and a value which is the result of the operation on the values of the two predecessors. The value of the output node is $E$. (We shall often refer to a node by its value or its operation, if there is no ambiguity.)

d. Each node belongs to one of $t+1$ sets, called levels and denoted by $l_0, l_1, \dots, l_t$, such that
d1. all input nodes are at level $l_0$,

d2. for $i \ge 1$, the predecessors of any node at level $l_i$ are from levels $l_0, \dots, l_{i-1}$,

d3. no level is empty.

Then it can be easily verified that the output node is the only node at level $l_t$ and that $t$ is bounded below by the maximal length of a path from any input node to the output node. We define $t$ to be the *time*,

the *number of processors*, and

$$k = \max_{1 \le i \le t} |l_i|$$

$$w = \sum_{1 \le i \le t} |l_i|$$

the *number of total operations* needed by the algorithm. An algorithm is called a sequential algorithm if $k = 1$ and a parallel algorithm if $k \ge 2$.

### Example 2.1

The following graph defines a parallel algorithm for evaluating the Horner expression of seven variables:
$$H_7 = ((a_1 b_1 + a_2) b_2 + a_3) b_3 + a_4,$$

given $I = \{a_1, b_1, a_2, b_2, a_3, b_3, a_4\}$ in time $t = 4$, with $k = 3$ processors and $w = 8$ operations.

<figure><img src="image_1.png" /></figure>

Input nodes: $a_1, b_1, a_2, b_2, a_3, b_3, a_4$

Output node: $H_7$

Hence a parallel algorithm for evaluating an expression E can be viewed as a circuit for computing E, of which $t$ is the depth, $k$ is the width and $w$ is the number of gates.

It seems to us that this model is very general, and includes any algorithm for evaluating expressions. One should note, however, that we have implicitly assumed that each operation takes one unit of time and the following machine idealizations:

a. Each processor can perform any of the four binary operations, but all processors do not necessarily perform the same operation at any time.

b. No time is required to communicate data between processors.

Since we are interested in lower bounds on time and upper bounds on speed-up, as we mentioned in the previous section, the results obtained in this paper for the idealized machine are certainly applicable for any real machine.

We now define some notation. For an expression E and an input set $I$, define

$T_k(E \bmod I) = \text{minimum time needed to evaluate E given } I \text{ by an algorithm using } k \text{ processors,}$

and define the speed-up of the problem of evaluating E given I by using $k$ processors to be

$$S_k(E \bmod I) = \frac{T_1(E \bmod I)}{T_k(E \bmod I)}.$$

For simplicity, we shall often write $T_k(E)$, $S_k(E)$ for $T_k(E \bmod I)$, $S_k(E \bmod I)$ if there is no ambiguity. In this paper we will obtain lower bounds on $T_k(E)$ and upper bounds on $S_k(E)$ for E defined by linear recurrences.
### 3. STATEMENTS OF RESULTS

The problem considered in this paper is the following first order linear recurrence problem:

$$ (3.1) \qquad \begin{array}{l} \text{given } a_1, \dots, a_{n+1}, b_1, \dots, b_n, \\ x_0 = a_1, \\ x_i = x_{i-1} b_i + a_{i+1} \quad \text{for } i \ge 1, \\ \text{compute } x_n. \end{array} $$

This is one of the most frequently occurring recurrences in practice. Consider the Horner expression of $H_{2n+1}$ variables:

$$ H_{2n+1} = ((\dots((a_1b_1+a_2)b_2+a_3)b_3+\dots+a_{n-1})b_{n-1}+a_n)b_n+a_{n+1}. $$

It is clear that $x_n = H_{2n+1}$. Hence the recurrence problem is just the problem of evaluating $H_{2n+1}$ given the input set

$$ I = \{a_1, \dots, a_{n+1}, b_1, \dots, b_n\}. $$

It is easy to see that the minimum time sequential algorithm is the obvious one defined by the recurrence (3.1). Hence we have

$$ (3.2) \qquad T_1(H_{2n+1}) = 2n. $$

Various parallel algorithms using $O(n)$ processors for the problem have appeared in many papers, including Brent [70], Kogge [72], Kuck and Maruyama [73], Stone [73], etc. In this paper, we are interested in algorithms using $k$ processors, where $k$ is a positive integer independent of $n$. Brent [74] had the first result along this line. He showed that for general arithmetic expression $E_n$ of $n$ variables and without division, if the input set is the set of all variables in $E_n$, then

$$ (3.3) \qquad T_k(E_n) \le \frac{2}{k}n + O(\log n). $$

Winograd [74] recently improved Brent's result. He showed

$$ (3.4) \qquad T_k(E_n) \le \frac{3}{2k}n + O(\log^2 n), $$

and conjectured that for $k > 1$,

$$ (3.5) \qquad T_k(E_n) \ge \frac{3}{2k}n + \text{lower order terms in } n. $$

The fundamental theorem of this paper is the following

#### Theorem 1

For any algorithm which evaluates $H_{2n+1}$ given the input set $I$, we have
$$ (3.6) \qquad w \ge 3n - \frac{t}{2}. $$

We defer the proof of this theorem until Section 4. We have the following two corollaries:

### Corollary 1

$$ (3.7) \qquad T_k(H_{2n+1}) \ge \frac{3}{k+\frac{1}{2}}n, \forall k, \forall n. $$

### Proof of Corollary 1

The proof follows from (3.6) and the fact that

$$ kt \ge w. $$

### Corollary 2

For any algorithm which evaluates $H_{2n+1}$ given the input set $I$, if $t \sim 2n$, then

$$ (3.8) \qquad w \ge 2n. $$

We now explain the significance of these corollaries. From Corollary 1 and (3.2), we obtain the main result of the paper:

$$ (3.9) \qquad \frac{S_k(H_{2n+1})}{k} \le \frac{2}{3}k + \frac{1}{3}, $$

i.e., the speed-up of the problem is at most $\frac{2}{3}k + \frac{1}{3}$ rather than $k$ by using a k-processor machine. Moreover, since $H_{2n+1}$ is a special instance of $E_{2n+1}$, by (3.7) we have

$$ T_k(E_n) \ge \frac{3}{2k+1}n - \frac{3}{2k+1}. $$

Therefore, we have shown a lower bound on $T_k(E_n)$, which is slightly smaller than that conjectured by Winograd (see (3.5)). Also, by (3.4) and (3.7),

$$ \frac{3}{k+\frac{1}{2}}n \le T_k(H_{2n+1}) \le \frac{3}{k}n + O(\log^2 n) $$

Hence the bounds in (3.4) and (3.7) are almost the best possible bounds, and so is the bound in (3.9).

Furthermore, one should observe that because of (3.2), the bound in (3.7) is sharp for $k = 1$.

We now turn to Corollary 2. By the corollary, any algorithm which takes time less than $2n$ must need more than $2n$ operations, which are required by the sequential algorithm. This means if a parallel algorithm is faster than the sequential algorithm, then it must require more work than the sequential algorithm does. This result plays a crucial role when we want to convert a parallel algorithm using unlimited number of processors into one using $k$ processors (see Lemma 2 in Brent [74] and Winograd [74]). The tradeoff between $t$ and $w$ has been observed in other problems (see, e.g., Hyafil and Kung [74]). It
becomes particularly significant for the pipeline computers such as CDC STAR-100, where both t and w are
important. (An excellent discussion on this matter can be found in Lambiotte and Voigt [74]). We view
**Theorem 1** as a start toward understanding the tradeoff between t and w in parallel computation.

By a technique similar to the one used in this paper, one can also deal with the continued expression,

$$
C_{2n+1} = a_{n+1} + b_n / (a_n + b_{n-1} / (a_{n-1} + \dots + b_3 / (a_3 + b_2 / (a_2 + b_1 / a_1)) \dots)),
$$

which has essentially the same form as the Horner expression. So far we have shown that $\tau_k(C_{2n+1})$
is bounded below essentially by $\frac{4}{k}$. The proof will not be given in this paper.

4. PROOF OF THEOREM 1

In this section we consider generalized Horner expressions:

$$
C_{2n+1} = ((\dots((A_1 B_1 + A_2) B_2 + A_3) B_3 + \dots + A_{n-1}) B_{n-1} + A_n) B_n + A_{n+1},
$$

where

$$
A_i \in L(a_i) = \{ \mu a_i + v | \mu, v \in \lambda \},
$$

$$
B_i \in L(b_i) = \{ \mu b_i + v | \mu, v \in \lambda \}.
$$

Let

$$
J = \bigcap_{1 \le i \le n} \{L(a_i) \cup L(b_i)\} \text{ if } \lambda.
$$

Instead of proving Theorem 1, we prove the following *stronger* theorem:

Theorem 1

For any algorithm which evaluates $G_{2n+1}$ given the input set $J$,

$$
w \geq 3n - \frac{t}{2}.
$$

We first establish three lemmas. The first lemma says that for evaluating $G_{2n+1}$ if no input node is used more than once and if all input nodes are essentially distinct, then the multiplication involving $a_1$ and $b_1$ is the only possible operation which can be performed at level $\ell_1$.

Lemma 1

In the directed graph of any algorithm for evaluating $G_{2n+1}$ given $J$, if the out-degree of each input node is exactly equal to one and if each $a_i$ or $b_i$ does not appear in more than one input node, then there is only one node at level $\ell_1$ and its value is in $L(a_1 b_1)$, where $L(a_1 b_1) = \{\mu a_1 b_1 + v | \mu, v \in \lambda\}$.

Proof of Lemma 1

Let $V$ be the value of a node at level $\ell_1$. Then $V$ is a rational function of $a_i, b_j$, of $a_i, a_j$ or of $b_i, b_j$. We shall only prove for the case that $V$ is a rational function of $a_i, b_j$, since the proofs for
the other cases are similar.

Because the out-degree of every input node is one and each of $a_i$ and $b_j$ does not appear in more than one input node, the value of the output node, $G_{2n+1}$, is a rational function of $V$, $a_h$ and $b_k$ for $h \neq i$ and $k \neq j$. By comparing the coefficients of $a_i$ and $b_j$ in $G_{2n+1}$ and in $R$, one can check that $V$ must be in $L(a_1b_1)$. This also proves that there is only one node at level $l_1$. ■

The following lemma is similar to Lemma 1 and hence the proof is omitted.

**Lemma 2**

If in addition to the assumption of Lemma 1, we assume that the out-degree of the only node at level $l_1$ is one, then there is only one node at level $l_2$.

One of the most important properties of generalized Horner expressions is their reproducing property, which is stated in the following

**Lemma 3**

If in $G_{2n+1}$, $A_i$ is replaced by $\alpha$ and $B_i$ by $\beta$ for some $1 \le i \le n$, with $\alpha, \beta \in \lambda$, the form of generalized expressions still remains; more precisely, $G_{2n+1}$ is reduced to $G_{2n-1}$.

**Proof of Theorem 1'**

Consider the directed graph $D$ of any algorithm for evaluating $G_{2n+1}$ given $J$. The proof of the theorem is based on the following algorithm, called algorithm A, on $D$. Algorithm A repeatedly performs the following steps:

a. Replace $a_i$ by $\alpha_i$, $b_i$ by $\beta_i$ for some $1 \le i \le n$, with $\alpha_i, \beta_i \in \lambda$.

b. Update input nodes and reconstruct the graph by deleting all redundant nodes and arcs, and moving updated input nodes to level $l_0$.

Algorithm A terminates when the graph is reduced to a single node. See Appendix for an illustration of how Algorithm A works on the graph of Example 2.1.

**Algorithm A**

1. Replace $a_{n+1}$ by $\alpha_{n+1}$ in the graph $D$, where $\alpha_{n+1} \in \lambda$ is so chosen that after the replacement the value of each node is well defined, i.e., no division by zero.

2. Set $P = \{1, 2, \dots, n\}$. ($P$ is the set of indexes of $a_i$ or $b_i$ which are in the current expression to be evaluated.)

3. Go to step 12.
4. Set $T \leftarrow P$, $N \leftarrow$ the set of input nodes in $D$, i.e., nodes at level $l_0$.

5. Choose the smallest integer in $T$ and denote it by $i$.

6. If $a_i$ or $b_i$ appears in more than one node in $N$ or appears in a node in $N$ whose out-degree > 1 (hence the condition of Lemma 1 is not satisfied), then go to step 10.

7. Set $T \leftarrow T - \{i\}$.

8. If $T \neq \emptyset$, return to step 5.

9. (The conditions of Lemma 1 are satisfied.) Choose the smallest integer in $P$ and denote it by $i$. (By Lemma 1, the multiplication involving $a_i$ and $b_i$ is the only operation that can be performed at level $l_1$ of the graph $D$.)

10. Set $P \leftarrow P - \{i\}$.

11. Replace $a_i$ by $\alpha_i$ and $b_i$ by $\beta_i$ in the graph $D$, where $\alpha_i, \beta_i \in \lambda$ are so chosen that after the replacements the value of each node is well defined.

12. Set $C \leftarrow \{\text{nodes whose values are in } J\}$.

13. Eliminate those nodes in $C$ whose successors are all in $C$, and arcs connected to them.

14. Move those nodes left in $C$ to level $l_0$. This gives us a reduced graph $D'$ which defines an algorithm for evaluating the generalized Horner expression in $a_i$ and $b_i$ where $i \in P$ (by Lemma 3).

15. If $P = \emptyset$, the algorithm terminates.

16. Set $D \leftarrow D'$ and return to step 4.

The following three facts can be easily verified.

a. In step 1 at least one nonscalar operation in $D$ is converted into scalar operations. ("$x$ op $y$" is defined to be a scalar operation if $op \in \{+, -, \times\}$ and at least one of $x$ and $y$ belongs to $\lambda$, or if $op = /$ and $y \in \lambda$.)

b. If the condition in step 6 is satisfied then at least three nonscalar operations in $D$ are converted into scalar operations in step 11.

c. If step 9 is executed, then the conditions of Lemma 1 are satisfied. There are two cases:

**Case 1.** The additional condition in Lemma 2 is satisfied. In this case, by Lemma 2 the depth of the reduced graph $D'$ in step 14 is less than that of $D$ by at least two. Furthermore, in step 11 at least two nonscalar operations are converted into scalar operations when $|P| > 1$ and one nonscalar operation into scalar operation when $|P|=1$.

**Case 2.** The additional condition in Lemma 2 is not satisfied. This implies that the out-degree of the only node at level $l_1$ is at least two. Hence in step 11 at least three nonscalar operations are converted into scalar operations when $|P| > 1$ and two
nonscalar operations into scalar operations when $|P| = 1$. Moreover, in this case the depth of $D'$ is less than that of $D$ by at least one.

Now let $u$ be the number of times that the condition in step 6 is satisfied and $v$ the number of times that step 9 is executed. Moreover, let $v_1(v_2)$ be the number of times that step 9 is executed and case 1 (case 2) is true, respectively. Then

$$v = v_1 + v_2.$$

Clearly,

$$n = u + v.$$

By (a), (b) and (c) the number of nonscalar operations which have been converted into scalar operations is at least $3u+2v_1+3v_2$. We have

$$w \geq 3u+2v_1+3v_2.$$

Hence

$$w \geq 3n - v_1.$$

By (c),

$$t \geq 2v_1 + v_2.$$

Therefore

$$w \geq 3n - \frac{t}{2} + \frac{v_2}{2} \geq 3n - \frac{t}{2}.$$

ACKNOWLEDGMENTS

The authors would like to thank Ron Rivest for helpful discussions and J. F. Traub for his comments.

REFERENCES

Brent, R. P. [70]. "On the Addition of Binary Numbers," *IEEE Trans. Comp.* C-19, 758-759.

Brent, R. P. [74]. "The Parallel Evaluation of General Arithmetic Expressions," *J. ACM*, 21, 201-206.

Hyafil, L. and H. T. Kung [74]. "Parallel Algorithms for Solving Triangular Linear Systems," contributed paper at Second Langley Conference on Scientific Computing, October, 1974.

Kogge, P. M. [72]. Parallel Algorithm for the Efficient Solution of Recurrence Problem, Tech. Report 43, Digital Systems Laboratory, Stanford University.

Kuck, D. J. and K. M. Maruyama [73]. The Parallel Evaluation of Arithmetic Expressions of Special Forms, report RC 4276, IBM Research Center, Yorktown Heights, New York.

Kung, H. T. [74]. "New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions," Proc. 6th Annual ACM Symposium on Theory of Computing, 323-333. To appear in *J. ACM*.

Lambiotte, J. J., Jr. and R. G. Voigt [74]. The Solution of Tridiagonal Linear Systems on the CDC STAR-100 Computer, report, ICASE, NASA Langley Research Center, Hampton, Virginia.

Stone, H. S. [73]. "An Efficient Parallel Algorithm for the Solution of a Tridiagonal System of Equations," *J. ACM* 20, 27-38.

Winograd, S. [74]. On the Parallel Evaluation of Certain Arithmetic Expressions, Report RC 4808, IBM Research Center, Yorktown Heights, New York.
● = input node

○ = node with scalar operation

⊗, ⊖ = node with nonscalar operation

<figure><img src="image_2.png" /></figure>

1. $a_4 - 1$

<figure><img src="image_3.png" /></figure>

2. $a_3 - 2, b_3 - 3$

<figure><img src="image_4.png" /></figure>
The graph is reduced to

<figure><img src="image_5.png" /></figure>

3. $a_2 \leftarrow 1, b_2 \leftarrow 2$

<figure><img src="image_6.png" /></figure>

The graph is reduced to

<figure><img src="image_7.png" /></figure>

4. $a_1 \rightarrow 3, b_1 \rightarrow 1$

<figure><img src="image_8.png" /></figure>

The graph is reduced to

3