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.