Wire retiming as fixpoint computation

Chuan Lin; Hai Zhou

doi:10.1109/TVLSI.2005.862726

Wire retiming as fixpoint computation

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

In system-on-chips (SOCs), a nonnegligible part of operation time is spent on global wires with long delays. Retiming-that is moving flip-flops in a circuit without changing its functionality-can be explored to pipeline long interconnect wires in SOC designs. The problem of retiming over a netlist of macro-blocks, where the internal structures may not be changed and flip-flops may not be inserted on some wire segments is called the wire retiming problem. In this paper, we formulate the constraints of the wire retiming problem as a flxpoint computation and use an iterative algorithm to solve it. Experimental results show that this approach is multiple orders more efficient than the previous one.

Original language	English (US)
Pages (from-to)	1340-1348
Number of pages	9
Journal	IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume	13
Issue number	12
DOIs	https://doi.org/10.1109/TVLSI.2005.862726
State	Published - Dec 2005

Funding

Manuscript received August 12, 2004; revised May 30, 2005. This work was supported by the National Science Foundation under Grant CCR-0238484. The authors are with the Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/TVLSI.2005.862726

Keywords

Algorithms
Circuit modeling
Circuit optimization
Fixpoint
Interconnects
Retiming

ASJC Scopus subject areas

Software
Hardware and Architecture
Electrical and Electronic Engineering

Access to Document

10.1109/TVLSI.2005.862726

Cite this

@article{d8bdb1196bdd4b55bf20e98412b4e5c3,

title = "Wire retiming as fixpoint computation",

abstract = "In system-on-chips (SOCs), a nonnegligible part of operation time is spent on global wires with long delays. Retiming-that is moving flip-flops in a circuit without changing its functionality-can be explored to pipeline long interconnect wires in SOC designs. The problem of retiming over a netlist of macro-blocks, where the internal structures may not be changed and flip-flops may not be inserted on some wire segments is called the wire retiming problem. In this paper, we formulate the constraints of the wire retiming problem as a flxpoint computation and use an iterative algorithm to solve it. Experimental results show that this approach is multiple orders more efficient than the previous one.",

keywords = "Algorithms, Circuit modeling, Circuit optimization, Fixpoint, Interconnects, Retiming",

author = "Chuan Lin and Hai Zhou",

note = "Funding Information: Manuscript received August 12, 2004; revised May 30, 2005. This work was supported by the National Science Foundation under Grant CCR-0238484. The authors are with the Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/TVLSI.2005.862726",

year = "2005",

month = dec,

doi = "10.1109/TVLSI.2005.862726",

language = "English (US)",

volume = "13",

pages = "1340--1348",

journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",

issn = "1063-8210",

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

number = "12",

}

TY - JOUR

T1 - Wire retiming as fixpoint computation

AU - Lin, Chuan

AU - Zhou, Hai

N1 - Funding Information: Manuscript received August 12, 2004; revised May 30, 2005. This work was supported by the National Science Foundation under Grant CCR-0238484. The authors are with the Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/TVLSI.2005.862726

PY - 2005/12

Y1 - 2005/12

N2 - In system-on-chips (SOCs), a nonnegligible part of operation time is spent on global wires with long delays. Retiming-that is moving flip-flops in a circuit without changing its functionality-can be explored to pipeline long interconnect wires in SOC designs. The problem of retiming over a netlist of macro-blocks, where the internal structures may not be changed and flip-flops may not be inserted on some wire segments is called the wire retiming problem. In this paper, we formulate the constraints of the wire retiming problem as a flxpoint computation and use an iterative algorithm to solve it. Experimental results show that this approach is multiple orders more efficient than the previous one.

AB - In system-on-chips (SOCs), a nonnegligible part of operation time is spent on global wires with long delays. Retiming-that is moving flip-flops in a circuit without changing its functionality-can be explored to pipeline long interconnect wires in SOC designs. The problem of retiming over a netlist of macro-blocks, where the internal structures may not be changed and flip-flops may not be inserted on some wire segments is called the wire retiming problem. In this paper, we formulate the constraints of the wire retiming problem as a flxpoint computation and use an iterative algorithm to solve it. Experimental results show that this approach is multiple orders more efficient than the previous one.

KW - Algorithms

KW - Circuit modeling

KW - Circuit optimization

KW - Fixpoint

KW - Interconnects

KW - Retiming

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

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

U2 - 10.1109/TVLSI.2005.862726

DO - 10.1109/TVLSI.2005.862726

M3 - Article

AN - SCOPUS:31644437939

SN - 1063-8210

VL - 13

SP - 1340

EP - 1348

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IS - 12

ER -

Wire retiming as fixpoint computation

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this