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/single-dimensional DSP, multirate/single-dimensional DSP, and single-rate/multi-dimensional DSP.;Also for single-rate/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/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 architectures for multi-rate DSP algorithms was performed using ad hoc design techniques.;For single-rate/multi-dimensional DSP, we have developed two techniques for retiming two-dimensional data-flow graphs. These techniques are designed to minimize the memory requirements under a given clock period constraint. These techniques can result in retimed circuits which use less than 50% of the memory required by previously used techniques.;For single-rate/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 two-fold. 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.