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

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

Fingerprint Dive into the research topics of 'Wire retiming as fixpoint computation'. Together they form a unique fingerprint.

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: clin@ece.northwestern.edu). Digital Object Identifier 10.1109/TVLSI.2005.862726 Funding Information: Prof. Zhou served on the technical program committees of the ACM International Symposium on Physical Design and the IEEE International Conference on Computer-Aided Design. He is a recipient of the CAREER Award from the National Science Foundation in 2003.",

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: clin@ece.northwestern.edu). Digital Object Identifier 10.1109/TVLSI.2005.862726 Funding Information: Prof. Zhou served on the technical program committees of the ACM International Symposium on Physical Design and the IEEE International Conference on Computer-Aided Design. He is a recipient of the CAREER Award from the National Science Foundation in 2003.

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

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

SN - 1063-8210

IS - 12

ER -