An efficient incremental algorithm for min-area retiming

Jia Wang*, Hai Zhou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

As one of the most effective sequential optimization techniques, retiming is a structural transformation that relocates flip-flops in a circuit without changing its functionality. The min-area retiming problem seeks a solution with the minimum flip-flop area (or number) under a given clock period. Even though having polynomial runtime, the best existing algorithms for this problem still need to first construct a dense path graph and then find a min-cost network flow on it, thus incur huge storage and time expenses for large circuits. Recently, provable incremental algorithms have been discovered for min-period retiming, and heuristic incremental algorithms have been proposed for min-area retiming. However, given the complexity of the problem, min-area retiming is still resisting an efficient provable incremental algorithm. In this paper, we fill the gap by presenting an efficient algorithm to solve the min-area retiming problem incrementally and optimally. Contrary to existing approaches, no dense path graph is constructed; only the active timing constraints are dynamically generated in the algorithm. Experimental results show that the total runtime of our algorithm for all the benchmarks is at least 60 × faster than the best existing approach.

Original languageEnglish (US)
Title of host publicationProceedings of the 45th Design Automation Conference, DAC
Pages528-533
Number of pages6
DOIs
StatePublished - Sep 17 2008
Event45th Design Automation Conference, DAC - Anaheim, CA, United States
Duration: Jun 8 2008Jun 13 2008

Other

Other45th Design Automation Conference, DAC
CountryUnited States
CityAnaheim, CA
Period6/8/086/13/08

Keywords

  • Retiming

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'An efficient incremental algorithm for min-area retiming'. Together they form a unique fingerprint.

Cite this