Minimizing Memory Requirements in Rate-Optimal Schedules

In this paper we address the problem of minimizing buffer storage requirement in constructing rate-optimal compile-time schedules for multi-rate dataflow graphs. We demonstrate that this problem, called the Minimum Buffer Rate-Optimal (MBRO) scheduling problem, can be formulated as a unified linear programming problem. A novel feature of our method is that it tries to minimize the memory requirement while simultaneously maximizing the computation rate. We have constructed an experimental testbed which implements our scheduling algorithm as well as (i) the widely used periodic admissible parallel schedules proposed by Lee and Messerschmitt [12], (ii) the optimal scheduling buffer allocation (OSBA) algorithm of Ning and Gao [15], and (iii) the multi-rate software pipelining (MRSP) algorithm [7]. The experimental results have demonstrated a significant improvement in buffer requirements for the MBRO schedules compared to the schedules generated by the other three methods. Compared to bloc..