10.4 DERIVING THE DEPENDENCE GRAPH FOR AN ALGORITHM

We use Eq. 10.1 to study the dependence of the algorithm variables. Variable y is an output variable, and variables x and a are input variables. We note that the algorithm gives rise to a 2-D graph since we have two indices, i and j. Since the dimensionality of is low, it is best to visualize using a dependence graph since this is easier for humans to analyze. We refer to any point in as a vector p

(10.2)

For given values of the indices, the vector corresponds to a point in the space.The graph covers the points p(i, j) ∈ where the range of the indices defines the boundaries of as

(10.3)

Note that extends to ∞ in the i direction, which defines an extremal ray.

10.4.1 Defining the Algorithm Variables in

We study in this section how to define the dependence of a variable in . Figure 10.1 shows the dependence graph of the 1-D FIR filter for the case N = 4. Let us consider the input variable a in Eq. 10.1. A specific instance of that variable such as a(2), for example, implies that we have set the index j equal to 2. We can formally write this substitution as

(10.4)

Figure 10.1 Dependence graph for the 1-D FIR filter for the case N = 4.

The above equation is a straight line equation in where a(2) is represented by a horizontal line. Figure 10.1 shows the dependence graph of the three variables y, a, and x. The horizontal straight line actually defines a set of points in e_a ∈ , where all the points use the same instant of a to do their operations. Equation 10.4 can be written in matrix form as Ap = 2 where A is the dependence matrix of variable e_a and p is any point. For our 2-D case, A becomes a row vector given by [0 1]. We call e_a the subdomain of variable a. This subdomain e_a is described by the basis vector

(10.5)

Chapter 11 will explain why this vector is a basis vector of the dependence matrix for a variable. We will need later to define the nullvector b associated with the basis vector of a variable. Variable a has the associated nullvector

(10.6)

The two vectors e_a and b_a satisfy the equation:

(10.7)

A specific value for variable x(3) can similarly be described by the straight line equation

(10.8)

The associated nullvector e_x is

(10.9)

This is represented by the diagonal lines in Fig. 10.1. The associated basis vector b_x is given by

(10.10)

For output y(5), the index dependence is given by the equation

(10.11)

and the nullvector e_y is given by

(10.12)

The basis vector b_y encompasses all the points in that produce results to be used to calculate a specific instance of y. The associated basis vector is given by

(10.13)

A node in represents the operations to be performed by each iteration. In our example, only one operation is to be performed by an iteration:

(10.14)

Since the addition operation is associative, we could have written the above iterative step as

(10.15)

Having derived the dependence graph for the given algorithm, we now need to synchronize the operation of each node. We need to know how to assign time values to each node dictating when the operation in each node is to be performed. This is called node scheduling. We also need to assign each node to a unique hardware processor or thread in a multicore, multithreaded implementation. This is called node projection.