Improved algorithm for minimum-area retiming

Naresh Maheshwari, Sachin S. Sapatnekar

Research output: Contribution to journalConference articlepeer-review

17 Scopus citations


The concept of improving the timing behavior of a circuit by relocating flip-flops is called retiming and was first presented by Leiserson and Saxe. The ASTRA algorithm proposed an alternative view of retiming using the equivalence between retiming and clock skew optimization. This work defines the relationship between the Leiserson-Saxe and the ASTRA approaches and utilizes it to solve the problem of retiming for minimum area. The new algorithm, Minaret, uses the linear programming formulation of the Leiserson-Saxe approach. The underlying philosophy of the ASTRA approach is incorporated to reduce the number of variables and constraints in the linear program. This reduction in the size of the linear program makes Minaret space and time efficient, enabling minimum area retiming of circuits with over 56,000 gates in under 15 minutes.

Original languageEnglish (US)
Pages (from-to)2-7
Number of pages6
JournalProceedings - Design Automation Conference
StatePublished - 1997
EventProceedings of the 1997 34th Design Automation Conference - Anaheim, CA, USA
Duration: Jun 9 1997Jun 13 1997


Dive into the research topics of 'Improved algorithm for minimum-area retiming'. Together they form a unique fingerprint.

Cite this