Incorporating Circuit Level Information into the Retiming Process

Tolga Soyata

October 4, 1999

Abstract

The advances in CMOS technology over the past decades have created the need for the design of extremely complex Very Large Scale Integration (VLSI) Integrated Circuits (IC)s. The simultaneous progress in Computer-Aided Design (CAD) tools enable large design teams to work independently on sophisticated VLSI projects. The pipelining process is widely utilized in VLSI ICs as a performance enhancement tool. Efficient automated pipelining algorithms have been developed to permit the application of pipelining to large integrated circuits. The emerging technique of retiming, on the other hand, has not found its way into the VLSI circuit design process due to complex and non-practical algorithms. Therefore, algorithms and/or methodologies to help achieve retiming with simpler and practical algorithms can significantly improve the acceptance of retiming techniques in standard VLSI design methodologies.

A retiming methodology is presented in this dissertation to model low-level circuit characteristics in VLSI ICs. This objective is achieved by modeling low level circuit parameters using the Register Electrical Characteristic (REC) model. The path delays in a VLSI IC are defined from register-to-register based on this REC model. The REC model forms the core of the retiming algorithms introduced in this dissertation. The REC model, for the first time, permits incorporating low-level circuit issues into the retiming process, thereby yielding significantly more accurate retiming results than the existing retiming algorithms currently described in the literature. Path monotonicity constraints have been developed to permit the application of standard Linear Programming (LP) based techniques to the general retiming process. These monotonicity constraints permit circuits to be retimed with low-level characteristics with significantly less CPU time complexity.

Although the application of retiming to practical circuits has not as yet become common place, the research described in this dissertation is a significant improvement in making retiming into a practical and useful design methodology. The relationship between clock scheduling and retiming is also discussed in this dissertation where it is shown that the two processes are inextricable intertwined. The results of applying retiming to benchmark circuits have demonstrated performance improvements of up to 50%. When clock scheduling techniques are combined with retiming techniques while including low-level circuit characteristics, retiming can significantly improve the design efficiency and performance of the next generation VLSI circuits.

Return to Eby Friedman's WWW home page