10.3 THE DEPENDENCE GRAPH OF AN ALGORITHM
Traditionally, a RIA is represented as a directed acyclic graph (DAG) as was discussed in Chapters 1 and 8. The graph is composed of a set of nodes representing the tasks to be performed by the algorithm, and the directed edges represent the data flowing between the tasks from the task producing the data to the task that uses the data. In this chapter, we start our analysis not from the DAG but by constructing a dependence graph in an integer space 
, where n denotes the number of indices of the algorithm. Once we develop a dependence graph, we will derive several DAGs based on our scheduling techniques as we shall discuss here and in Section 10.5 and in Chapter 11. Stated more explicitly, an RIA can be represented by one dependence graph. The same algorithm could result in several DAGs.
Definition 10.1
A dependence graph is a set of nodes and edges in the integer domain 
. A node is a point 
and represents the tasks to be performed at the given values of the indices. The edges show how the algorithm variables depend on the algorithm indices. The points lying on an edge indicate that the operations performed by nodes use the data carried by the edge.
Notice the definition of edges in the dependence graph. A dependence graph is not a DAG since the edges are not directed. Further, an edge in the dependence graph could be associated with an input, output, or input/output intermediate values depending on the variable.
Lemma 10.1
The dependence graph of an algorithm is unique to each algorithm since there is only one way to describe how the variables depend on the indices.
The advantage of this approach will become apparent in the following discussion and in Chapter 11 where we will be able to study the algorithm in terms of powerful linear algebra and computational geometry concepts. Table 10.1 compares the dependence graph defined above and the DAG defined in Chapter 1.
Table 10.1 Comparing the Dependence Graph and the Directed Acyclic Graph (DAG)
| Dependence graph | Directed acyclic graph (DAG) |
The graph is really a convex hull ( ) in the integer space  . | The graph is a 2-D drawing on a sheet of paper or on the computer screen. |
| Undirected edges. | Directed edges. |
| Edge represents how a variable depends on the algorithm indices. | The edge represents data flowing from the output of a task to the input of another task. |
| An edge covers many nodes and spans the entire computation domain . | An edge is confined between two tasks (nodes). |
| The node represents a task done by the algorithm. | The node represents a task done by the algorithm. |
The node is located at a specific coordinate point in  . | There is no significance as to where a node is located on the graph. |
| The execution sequence cannot be determined from inspecting the dependence graph. | The execution sequence can be determined by inspecting the DAG. The task producing a datum must be executed before the task consuming that datum. |