Minimizing memory requirements in rate-optimal schedules

Abstract

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, con be formulated as a unified linear programming problem. A novel feature of the 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: the widely used periodic admissible parallel schedules proposed by R.A. Lee and D.A. Messerschmitt (1987); the optimal scheduling buffer allocation (OSBA) algorithm of Q. Ning and G.R. Gao (1993); and the multi-rate software pipelining (MRSP) algorithm (R. Govinderajan and G.R. Gao, 1993). 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 block schedules, MBRO schedules perform better in terms of both computation rate and buffer requirements. The average observed improvement in buffer storage is 26% with respect to the MRSP algorithm, 17% with respect to block schedules and 5% with respect to the OSBA formulation.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>