Algorithms and Parallel Computing

12.3 THE IIR FILTER DEPENDENCE GRAPH

We use Eq. 12.1 to study the index dependencies of the algorithm variables. Variable y is an input/output or intermediate variable, and variables x, a, and b are all input variables. An input/output variable is one that is present on the right-hand side (RHS) and left-hand side (LHS) of the algorithm equations with different index dependencies for each side.

We note that the algorithm gives rise to a two-dimensional (2-D) computation domain 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 visualize and analyze.

We organize our indices in the form of a vector:

(12.2)

for given values of the indices, the vector corresponds to a point in the ² space.

12.3.1 The 2-D Dependence Graph

The dimension of a dependence graph is two, which is the number of indices in the algorithm. The graph covers the points p(i, j) ∈ , where the range of the indices ...