Optimal wire retiming without binary search

Chuan Lin; Hai Zhou

doi:10.1109/TCAD.2005.858268

Optimal wire retiming without binary search

Chuan Lin^*, Hai Zhou

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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 language	English (US)
Article number	1673735
Pages (from-to)	1577-1588
Number of pages	12
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	25
Issue number	9
DOIs	https://doi.org/10.1109/TCAD.2005.858268
State	Published - Sep 2006

Funding

Manuscript received August 20, 2004; revised January 6, 2005, April 6, 2005, and August 10, 2005. This work was supported by the National Science Foundation under Grant CCR-0238484. This paper was recommended by Associate Editor S. Sapatnekar.

Keywords

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

Access to Document

10.1109/TCAD.2005.858268

Cite this

@article{e5cd5997fed9439fb67155717f319220,

title = "Optimal wire retiming without binary search",

abstract = "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.",

keywords = "Algorithms, Circuit modeling, Circuit optimization, Design methodology, Interconnects, Pipelining, Polynomial complexity, Retiming",

author = "Chuan Lin and Hai Zhou",

note = "Funding Information: Manuscript received August 20, 2004; revised January 6, 2005, April 6, 2005, and August 10, 2005. This work was supported by the National Science Foundation under Grant CCR-0238484. This paper was recommended by Associate Editor S. Sapatnekar.",

year = "2006",

month = sep,

doi = "10.1109/TCAD.2005.858268",

language = "English (US)",

volume = "25",

pages = "1577--1588",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "9",

}

TY - JOUR

T1 - Optimal wire retiming without binary search

AU - Lin, Chuan

AU - Zhou, Hai

N1 - Funding Information: Manuscript received August 20, 2004; revised January 6, 2005, April 6, 2005, and August 10, 2005. This work was supported by the National Science Foundation under Grant CCR-0238484. This paper was recommended by Associate Editor S. Sapatnekar.

PY - 2006/9

Y1 - 2006/9

N2 - 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.

AB - 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.

KW - Algorithms

KW - Circuit modeling

KW - Circuit optimization

KW - Design methodology

KW - Interconnects

KW - Pipelining

KW - Polynomial complexity

KW - Retiming

UR - http://www.scopus.com/inward/record.url?scp=33748125347&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748125347&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2005.858268

DO - 10.1109/TCAD.2005.858268

M3 - Article

AN - SCOPUS:33748125347

SN - 0278-0070

VL - 25

SP - 1577

EP - 1588

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 9

M1 - 1673735

ER -

Optimal wire retiming without binary search

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this