Time-constrained loop scheduling with minimal resources

Abstract

Many 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 paper, we develop new results regarding the construction of such graphs. We develop scheduling algorithms for such graphs, and then discuss a way to reduce the hardware requirements of such schedules. In the process, we state and prove a tight upper bound on the minimum number of processors required to execute the static schedule produced by our algorithms. We also construct an unfolding algorithm for split-node graphs and combine it with our scheduling methods to achieve rate-optimality in all cases. Finally, we demonstrate our methods on a specific example.