20.3 FORWARD SUBSTITUTION (DIRECT TECHNIQUE)

The general form for a system of linear equations was given in Eq. 20.1. Forward substitution technique converts the square matrix A into a lower triangular form:

(20.10)

Consider the 5 × 5 lower triangular linear system:

(20.11)

If all l_ii ≠ 0, then we can determine the unknowns according to the equations

(20.12)

where x₁ must be calculated before x₂ could be evaluated and so on. Thus, it appears that the calculations are sequential, with small opportunity for parallelization. However, the techniques we discussed earlier will help us derive parallel multithreaded and systolic architectures.

20.3.1 Forward Substitution Dependence Graph

The iterations in Eq. 20.12 use two indices i and j and we can use the results of Chapters 10 or 11 to study the parallelization of the forward substitution algorithm. Figure 20.1 is the dependence graph of the iterations in Eq. 20.12. Note that the variable x is an input/output variable and this explains why we have two sets of x, one set for the output instances of x and the other set is for the input instances of x.

Figure 20.1 The dependence graph of the forward substitution algorithm.

Input instance x_in(k) is a copy of the output instance x_out(k). This is shown by the bends in the lines that appear on the diagonal nodes.

20.3.2 Forward Substitution Scheduling Function and Directed Acyclic Graph (DAG)

The choice of the scheduling function is dictated by the need to maintain the proper sequence of evaluating x_i. We know that x_out(i) can be found only after x_out(i − 1) has been evaluated. We note that output instance x_out(i) is obtained at the diagonal node (i, i) and is used by all nodes whose coordinates are (i + k, i) where k > 0. Therefore, if the scheduling vector is s = [s₁ s₂], then we must have

(20.13)

(20.14)

and we can write the inequality

(20.15)

Since k > 0, we must have s₁ > 0 too. We can choose s₁ = 1 and we have our scheduling vector as

(20.16)

We can choose three possible scheduling vectors while satisfying inequality (Eq. 20.13):

(20.17)

(20.18)

(20.19)

The resulting DAGs for the three choices are shown in Fig. 20.2. The scheduling vector s₁ implies diagonal-based calculations since each iteration requires simultaneous access to the elements of a diagonal. The choice of s₁ will produce a DAG where output sample x_out(i) is obtained on the left edge of the diagram. However, this output sample must be fed back to node (i, i) for use by later calculations. Depending on the projection vector chosen, we might have to provide communication between the left nodes and the diagonal nodes. The work W at each time step would start at N, then decrease by one at each time step thereafter.

Figure 20.2 The DAG graphs of the forward substitution algorithm for the three possible scheduling functions.

The scheduling vector s₂ implies row-based calculations since each iteration requires simultaneous access to the elements of a row. The work W at each time step would start at 1, then increase by one at each time step thereafter.

The scheduling vector s₃ implies column-based calculations since each iteration requires simultaneous access to the elements of a column. The work W at each time step would start at 1 for the first two operations, then increase by two at the next two time steps. The maximum work is encountered halfway during the operation, and then work starts to decrease by 2 after each two time steps thereafter.

We can use nonlinear scheduling to control the total workload at each iteration. However, the work done at each time step will not be uniform.

20.3.3 Forward Substitution Projection Function

Three projection directions are possible:

(20.20)

(20.21)

(20.22)

The simplest projection directions to use would be d₂ and d₃.

Let us consider the case when d₂ is used. The reduced DAG () is shown in Fig. 20.3. We can use nonlinear projection to control the workload of each thread or each processing element (PE) in the systolic array.

Figure 20.3 The graphs of the forward substitution algorithm for the three possible scheduling functions.