Optimal wire retiming without binary search

Chuan Lin*, Hai Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


The problem of retiming over a netlist of macroblocks to achieve minimal clock period, where block internal structures may not be changed and flip-flops may not be inserted on some wire segments, is called the optimal wire retiming problem. This paper presents a new algorithm that solves the optimal wire retiming problem with polynomial-time worst case complexity. Since the new algorithm avoids binary search and is essentially incremental, it has the potential of being combined with other optimization techniques. Experimental results show that the new algorithm is very efficient in practice.

Original languageEnglish (US)
Article number1673735
Pages (from-to)1577-1588
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
StatePublished - Sep 2006


  • Algorithms
  • Circuit modeling
  • Circuit optimization
  • Design methodology
  • Interconnects
  • Pipelining
  • Polynomial complexity
  • Retiming

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Optimal wire retiming without binary search'. Together they form a unique fingerprint.

Cite this