Title: Joint Minimization of Code and Data for Multirate Synchronous
Dataflow Programs
Students: Praveen K. Murthy and
Dr. Shuvra S. Bhattacharyya (Hitachi America, Ltd.)
Advisor: Edward A. Lee
Sponsors: ARPA and the US Air Force (under the RASSP program, contract
F33615-93-C-1317) and Hitachi
In this project, we are developing formal techniques for the problem of
minimizing the memory required for buffering along arcs of a synchronous
dataflow (SDF) graph given the constraint that a minimum code-size, static
uniprocessor schedule is desired. A schedule that minimizes the code size
is called a single-appearance schedule. Synchronous dataflow describes
systems that operate on uniformly sampled (and resampled) data.
For the class of well-ordered SDF graphs (graphs that have a Hamiltonian
path), our problem is similar to the problem of most efficiently multiplying
a chain of matrices [2], for which a dynamic programming solution exists
that has quadratic-time complexity. In [1], we show that this technique can
be adapted to our memory-minimization problem for well-ordered graphs to
yield an algorithm that finds an optimal solution with time complexity O(n^3),
where n denotes the number of nodes of the SDF graph. We have also developed
an O(n^2) heuristic which usually performs quite well [1].
An acyclic SDF graph can have an exponential number of topological sorts,
and each of these sorts induces a single appearance schedule. While the
dynamic programming algorithm can also be used to determine a buffer-optimal
schedule for any such single appearance schedule induced by a particular
topological sort for the acyclic graph, efficiently finding the topological
sort that minimizes buffering memory appears to be a difficult problem.
Instead, we have evaluated several heuristics to solve this problem.
A heuristic [3] based on minimum legal cuts into bounded sets has given the
best performance so far and outperforms more obvious greedy strategies for
the problem. A legal cut of an acyclic digraph is a cut in which all of the
arcs crossing the cut go in the same direction. A minimum legal cut is a
legal cut that minimizes the weight of the arcs crossing the partition. The
cut results in bounded sets if the size of the two node sets on either side
of the partition are bounded. The scheduling heuristic finds these cuts
(where the weights on the arcs represent the amount of data that is
transferred in one complete cycle of the schedule) and recursively schedules
the nodes on the left side of the cut before the nodes on the right side of
the cut.
Further work in this area includes the investigation of systematic techniques
to trade-off code size and data memory by constructing non-single appearance
schedules.
[1] P. K. Murthy, S. S. Bhattacharyya, and E. A. Lee, "Minimizing Memory
Requirements for Chain-Structured Synchronous Dataflow Programs",
Proc. of the Int. Conf. of Acoustics, Speech, and Signal Processing,
Adelaide, Australia, April 1994.
[2] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest,
{Introduction to Algorithms}, New York: McGraw-Hill, 1990.
[3] P. K. Murthy, S. S. Bhattacharyya, and E. A. Lee, "Joint Minimization
of Code and Data for Synchronous Dataflow Programs," in preparation.