Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits

Sachin S. Sapatnekar, Rahul B. Deokar

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

Abstract

The introduction of clock skew at an edge-triggered flip-flop has an effect that is similar to the movement of the Hipflop across combinational logic module boundaries, and these are continuous and discrete optimizations with the same effect. While this fact has been recognized before, this paper, for the first time, utilizes this information to find an optimal retiming efficiently. The clock period is guaranteed to be at most one gate delay larger than the optimal clock period found using skew alone; note that since skew is a continuous optimization, it is possible that the optimal period may not be achievable. The method views the circuit hierarchically, first solving the clock skew problem at one level above the gate level, and then using local transformations at the gate level to perform retiming for the optimal clock period. The solution is thus divided into two phases. In Phase A, the clock skew optimization problem is solved with the objective of minimizing the clock period, while ensuring that the difference between the maximum and the minimum skew is minimized. Next, in Phase B, retiming is employed and some flip-flops are relocated across gates in an attempt to set the values of all skews to be as close to zero as possible.

Original languageEnglish (US)
Pages (from-to)1237-1248
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume15
Issue number10
DOIs
StatePublished - 1996

Bibliographical note

Funding Information:
Manuscript received August 11, 1994; revised March 13, 1995 and June 20, 1996. This work was supported in part by the National Scicnce Foundation Faculty Early Career Development Award under Contract MIP-9502556. This paper was recommended by Associate Editor F. Somenzi. The authors are with the Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 5001 1 USA. Publisher Item Identifier S 0278-0070(96)07467-2.

Fingerprint

Dive into the research topics of 'Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits'. Together they form a unique fingerprint.

Cite this