Optimal wire retiming without binary search

Chuan Lin*, Hai Zhou

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations


The problem of retiming over a netlist of macro-blocks to achieve the minimal clock period, where the 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. To the best of our knowledge, there is no polynomial-time approach to solve it and the existence of such an approach is still an open question. In this paper, we present a brand 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 number6B.3
Pages (from-to)452-458
Number of pages7
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
StatePublished - Dec 1 2004
EventICCAD-2004 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers - San Jose, CA, United States
Duration: Nov 7 2004Nov 11 2004

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

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

Cite this