A novel framework for multi-rate scheduling in DSP applications

The authors present a novel framework for multi-rate scheduling of signal processing programs represented by regular stream flow graphs (RSFGs). The nodes of an RSFG may execute at different rates to avoid unbounded storage requirement under repetitive computation. A distinct feature of the scheduling framework, called the multi-rate software pipelining, is to allow maximum overlapping of operations from successive iterations subject only to precedence constraints caused by data dependencies. A novel framework based on linear programming techniques has been proposed to schedule RSFGs. The scheduling problem is formulated as a mathematical problem by capturing data dependencies between two actors as a precedence relation between the firing of these actors. The precedence relationships are represented in the form of a precedence graph. An efficient polynomial-time solution is obtained by observing that the computation rate of the optimal schedule is the minimum cost-to-time ratio cycle (MCTRC) in the precedence graph