Algorithms and Parallel Computing

11.3 THE 3-D DEPENDENCE GRAPH AND COMPUTATION DOMAIN

As we mentioned above, this chapter starts by studying a multidimensional computation domain rather than a dependence graph. We shift our focus from graphs, nodes, and edges to convex hulls in ³ as will be explained below.

The recursive algorithm in Eq. 11.1 is an equation involving the indexed variables v_i(p), where i = 1, 2, 3 to account for one output variable, M₁, and two input variables, M₂ and M₃, in Eq. 11.1. The boundaries of the ³ space describing our algorithm are defined by the restrictions imposed on the values of the indices as will be discussed in the following subsection. The collection of points within imposed boundaries defines the computation domain . The dimension of is n = 3, which is the number of indices in the algorithm.

11.3.1 3-D Domain Boundaries

The 3-D computation domain extends in the index space over a volume ...