| Researchers: | Praveen K. Murthy (UCB) and Dr. Shuvra S. Bhattacharyya (Hitachi America, Ltd.) |
|---|---|
| Advisor: | Edward A. Lee |
| Sponsors: | ARPA(RASSP) F33615-93-C-1317, Hitachi, and the Ptolemy Project |
A dynamic programming algorithm [1] has already been developed that solves the problem of minimizing code size by optimally organizing loops for an arbitrary (not necessarily single appearance) schedule. Thus, for example, a schedule that has been constructed for minimum buffer memory can be post-optimized to improve the code size, while preserving the buffer optimality. When this algorithm is applied to a single appearance schedule for a delayless graph, the resulting schedule has the minimum data-buffering cost from among all schedules with the same lexical ordering of the nodes. For graphs that contain delays, the algorithm may sometimes modify the lexical ordering, and the resulting schedule is guaranteed to have data-buffering cost of all schedules with the initial lexical ordering. For the class of well-ordered SDF graphs (graphs that have a Hamiltonian path), the schedules constructed by this algorithm are always optimal since there is only one valid lexical ordering for any single appearance schedule.
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 hard problem. Instead, we have developed two heuristics for this problem.
These two methods appear to be complementary, in that for graphs in which one fails to find a good schedule, the other finds one. For a class of SDF graphs, we have shown that the APGAN method constructs optimal schedules. While this class of graphs forms a rather small subset of all possible SDF graphs, practical SDF graphs are often from this class. For example, the SDF abstractions of several filterbank systems do fall into this class and can thus be scheduled optimally. A short summary of this work can be found in [4].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.