Algorithms and Parallel Computing

11.1 INTRODUCTION

The techniques we have discussed so far for regular iterative algorithms (RIAs) are based on the availability of the dependence graph [80, 81]. At best, a dependence graph can handle algorithms that can be represented by computational domains of dimension 3 at most. In the case of attempting to implement a three-dimensional (3-D) filter on parallel hardware or using multithreading, the resulting dependence graph would be representable in a six-dimensional space. Such a dependence graph becomes very complex.

In this chapter, we study the RIA by studying each variable in the algorithm separately using concepts in computational geometry and matrix algebra. The variables we might encounter are of three types: input, output, and intermediate or input/output variables. An input variable is one that has its instances appearing only on the right-hand side (RHS) of the equations of the algorithm. An output variable is one that has its instances appearing only on the left-hand side (LHS) of the algorithm. An intermediate variable is one that has its instances appearing both on the LHS and on the RHS of the equations of the algorithm such that the variable has different index dependences on both sides of the iteration statements. We consider an intermediate variable as being both an input or output variable with different index dependencies for each instance. Using this artifact, we reduce our set of variables to input and output variables only.

The analysis in this chapter ...