Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-432-93

Authors:

Date:

July 1993

Pages:

26

Download Formats:

Given a behavioral description of a DSP algorithm represented by a

data-flow graph, we show how to obtain a rate-optimal static schedule

with the minimum unfolding factor under two models, integral grid

model and fractional grid model, and two kinds of implementations for

each model, pipelined implementation and non-pipelined implementation.

We present a simple and unified approach to deal with the four

possible combinations. A unified polynomial-time scheduling algorithm

is presented, which works on the original data-flow graphs without

really unfolding. The values of the minimum rate-optimal unfolding

factors and the general properties for all the four combinations are

proved.