Static Scheduling of Split-Node Data-Flow Graphs

T.W. O'Neil and E.H.-M. Sha (USA)


Parallel and Distributed Compilers, Task Scheduling.


Many computation-intensive or recursive applications commonly found in digital signal processing and image processing applications can be represented by data-flow graphs (DFGs). In our previous work, we proposed a new technique, extended retiming, which can be combined with minimal unfolding to transform a DFG into one which is rate-optimal. The result, however, is a DFG with split nodes, a concise representation for pipelined schedules. This model and the extraction of the pipelined schedule it represents have heretofore not been explored. In this pa per, we construct scheduling algorithms for such graphs and demonstrate our methods on specific examples.

Important Links:

Go Back