bjornl@tds.kth.se (Bj|rn Lisper) (11/09/89)
In article <8911071854.AA06869@jupiter.cis.ohio-state.edu> nevin@CIS.OHIO-STATE.EDU (Nicholas Nevin) writes: %I have a problem concerning directed acyclic graphs (DAG's) as used to %represent the dependencies in parallel algorithms. .... %For many algorithms the corresponding DAG's have a very 'regular' structure %e.g. FFT DAG , triangular solver DAG, diamond DAG, binary tree DAG etc. %The problem is to come up with some formal %criteria whereby we can recognise such 'regular' DAG's. .... % Does anyone know of any such criteria %and of any general results about graphs that fit such criteria? Roughly speaking, the DAG (or the algorithm whose dependencies it describes) should be possible to describe by a short formula (or program), relative to the number of nodes. Then the DAG must by necessity have a regular structure because it is described with a small amount of information. A good example is the recurrence below that describes matrix multiplication by forward summation: 1 <= i,j <= n: c(i,j,0) := 0 1 <= i,j,k <= n: c(i,j,k) := c(i,j,k-1)+a(i,k)*b(k,j) This is a small formula, but if n is large it specifies a very large data dependence graph. Consequently, the graph is very regular. The small formula above can specify a big DAG because it is parameterized. A parameterized part of it can "generate" many nodes in the DAG, one node for each argument tuple. For parameterized formulas is is often convenient to represent each node in the generated DAG by the argument tuple generating it. In the example above, each assignment of c(i,j,k) can thus be represented by the integer vector (i j k), a so-called index vector. With this representation, the dependencies can be represented by a so-called data dependence vector: in the example, note that for all steps except (i j 0), (i j k) needs c(i,j,k-1) produced by (i j k-1). The data dependence vector (i j k) - (i j k-1) = (0 0 1) captures the dependence structure of the graph. The DAG of the computation can thus be described by the following: 0 <= i,j,k <= n: (i j k) (nodes) (0 0 1) (dependencies, i.e. arcs) Indeed a compact description. Other types of computations have other suitable indexings. FFT type recurrences over 2^n data points, for instance, are conveniently expressed by recursion equations over n binary indices and an integer recursion index that ranges from 0 to n-1. The resulting DAG will be of the usual butterfly type. Binary tree type computations are conveniently expressed with recurrences over binary strings: the root in the DAG is then the empty string and each node s has the sons s0 and s1, respectively. I've been doing some work considering scheduling methods for regular DAGS as above. When the DAG has a simple representation, as regular DAGs have, simple scheduling functions will generate regular schedules. This can be used to derive systolic arrays for algorithms with suitable structure, like the matrix multiplication recurrence in the example above. Bjorn Lisper