Retiming Folding And Register Minimization For Dsp Synthesis

This thesis introduces some formal techniques which can be used for synthesis of VLSI (very large scale integration) architectures for DSP (digital signal processing) algorithms. These techniques can be used to design architectures for single rate and single dimensional DSP, multirate and single-dimensional DSP, and single rate and multi-dimensional DSP. For single rate and single-dimensional DSP, we have developed a novel technique for exhaustively generating all retiming and scheduling solutions for the DSP algorithm. The significance of this contribution is twofold. First, it allows a circuit designer to explore a large space of possible high level implementations for the algorithm, which allows the designer to make a good decision about the high level architectural details of the design. Second, this work explicitly shows the important interaction between retiming and scheduling in high level synthesis. While retiming and scheduling have been treated as separate problems in the past, our work uses a mathematical framework to show that retiming is a special case of scheduling. Also for single rate and single-dimensional DSP, we have developed techniques for computing the minimum number of registers required to implement a statically scheduled DSP program. Closed form expressions are derived for computing the minimum number of registers assuming various memory models with or without retiming the scheduled DFG. This is an important problem because memory typically occupies a large portion of the area of a DSP implementation (often over half of the area), and minimizing this area leads to more efficient designs. For multirate and single-dimensional DSP, we have developed a multirate folding technique which can be used to synthesize single rate architectures from multirate DSP algorithms. Prior to the development of this formal technique, the design of single rate.