Algorithms and Parallel Computing

11.5 THE DEPENDENCE MATRICES OF THE ALGORITHM VARIABLES

Previous works on parallel algorithms and parallel processing attempted to study data dependencies by studying how the output variables depend on the input variables. We do not follow this approach here. Instead, we study how each variable depends on the indices of the algorithm.

Assume a variable v in the algorithm described by Eq. 11.1 depends on m out of the n indices describing the algorithm. The index dependence of the variable v could be written as a function of its indices in the affine form

(11.20)

where A is the dependence matrix, which is an integer m × n matrix (m ≤ n), and a is an integer m-vector. We call A the dependence matrix and a the dependence vector. The dependence matrix relates the variable to the domain indices and does not describe the dependence of the output variable on the input variables.

Typically, indexed variables have a = 0, where 0 is an m-vector whose components are all zeros.

Assume we have a specific instance of a variable v given by v(c), where c is a constant vector. From the definition of the dependence matrix in Eq. 11.20, we can write

(11.21)

The above is a system of m linear equations in n unknowns. When m < n, we have many solutions for the unknown index values. When n = m, we ...