Algorithms and Parallel Computing

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 ...