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 defined by the limits imposed on the index vector p. We define the computation domain as the set of points in the 3-D space that satisfies certain criteria [82]:

(11.3)

with i = 1, 2, 3 and j = 1, 2, 3.

The row vectors Ψ_i and ψ_i define the upper hull of [82–85]. Similarly, the row vectors Λ_j and λ_j define the lower hull of . These two hulls describe the surfaces defining . To give a tasty example, consider as an ice cream cone. In that case, the upper hull represents the chocolate coating on top. The lower hull represents the cone or wafer. The points of the computational domain correspond to the ice cream.

From Eq. 11.1, the upper hull of our matrix algorithm is described by the equations of several planes in the 3-D space:

(11.4)

(11.5)

(11.6)

The above three inequalities simply state that the upper bound on points in is described by the equations of planes defining the top surfaces of :

(11.7)

(11.8)

(11.9)

The first inequality describes a plane perpendicular to the i-axis and so on for the other two equations.

From Eq. 11.1, the lower hull of our matrix algorithm is described by the equations of several planes in the 3-D space:

(11.10)

(11.11)

(11.12)

The above three inequalities simply state that the lower bound on points in is described by the equations of planes defining the bottom surfaces of :

(11.13)

(11.14)

(11.15)

Figure 11.1 shows the computation domain for the matrix multiplication algorithm. is a convex hull, which is another way of saying it is a volume in the 3-D space that has upper and lower bounds on its index values.

Figure 11.1 The 3-D computation domain for the matrix multiplication algorithm.

Note that the limits imposed on the algorithm indices define the computation domain in a direct and simple manner. Earlier approaches used the domain vertices and “extremal rays” to define . However, in most cases, these quantities are simply not directly available.

In the design of multiprocessors or multithreaded applications, it is important to determine the regions where and when data will be fed or extracted. This is related to the study of the facets and vertices of as explained in the following two sections.