Static Rate-Optimal Scheduling of Iterative Data-Flow Programs via Optimum Unfolding

This paper addresses rate-optimal compile-time multiprocessor scheduling of iterative data-flow programs suitable for real-time signal processing applications. Recursions or loops in these programs lead to an inherent lower bound on the achievable iteration period, referred to as the iteration bound. A multiprocessor schedule is rate-optimal if the iteration period equals the iteration bound. In general, it may not be possible to schedule a specified iterative data-flow program rate-optimally. Retiming transformation may improve the iteration period of a schedule, but cannot guarantee the schedule to be rate-optimal. Systematic unfolding of iterative data-flow programs is proposed, and properties of unfolded data-flow programs are studied. Unfolding increases the number of tasks in a program, unravels the hidden concurrency in iterative data-flow programs, and can reduce the iteration period. We introduce a special class of iterative data-flow programs, referred to as perfect-rate programs. Each loop in these programs has a single register (a register is also referred to as a delay in signal processing literature). Perfect-rate programs have the important property that they can always be scheduled rate-optimally (requiring no retiming or unfolding transformation). We show that unfolding any program by an optimum unfolding factor transforms any arbitrary program to an equivalent perfect-rate program, which can then be scheduled rate-optimally. This optimum unfolding factor for any arbitrary program is the least common multiple of the number of registers (or delays) in all loops, and is independent of the node execution times. An upper bound on the number of processors for rate-optimal scheduling is also given.