A new efficient retiming algorithm derived by formal manipulation

Hai Zhou

doi:10.1145/1297666.1297673

A new efficient retiming algorithm derived by formal manipulation

Hai Zhou^*

^*Corresponding author for this work

Electrical and Computer Engineering

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

5 Scopus citations

Abstract

A new efficient algorithm is derived for the minimal period retiming by formal manipulation. Contrary to all previous algorithms, which used fixed period feasibility checking to binary-search a candidate range, the derived algorithm checks the optimality of a feasible period directly. It is much simpler and more efficient than previous algorithms. Experimental results showed that it is even faster than ASTRA, an efficient heuristic algorithm. Since the derived algorithm is incremental by nature, it also opens the opportunity to be combined with other optimization techniques.

Original language	English (US)
Article number	7
Journal	ACM Transactions on Design Automation of Electronic Systems
Volume	13
Issue number	1
DOIs	https://doi.org/10.1145/1297666.1297673
State	Published - Jan 1 2008

Keywords

Algorithm derivation
Clockperiod minimization
Retiming

ASJC Scopus subject areas

Computer Science Applications
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1145/1297666.1297673

Cite this

@article{039f53fff2e64f0d86eedaa0b3aff66e,

title = "A new efficient retiming algorithm derived by formal manipulation",

abstract = "A new efficient algorithm is derived for the minimal period retiming by formal manipulation. Contrary to all previous algorithms, which used fixed period feasibility checking to binary-search a candidate range, the derived algorithm checks the optimality of a feasible period directly. It is much simpler and more efficient than previous algorithms. Experimental results showed that it is even faster than ASTRA, an efficient heuristic algorithm. Since the derived algorithm is incremental by nature, it also opens the opportunity to be combined with other optimization techniques.",

keywords = "Algorithm derivation, Clockperiod minimization, Retiming",

author = "Hai Zhou",

year = "2008",

month = jan,

day = "1",

doi = "10.1145/1297666.1297673",

language = "English (US)",

volume = "13",

journal = "ACM Transactions on Design Automation of Electronic Systems",

issn = "1084-4309",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - A new efficient retiming algorithm derived by formal manipulation

AU - Zhou, Hai

PY - 2008/1/1

Y1 - 2008/1/1

N2 - A new efficient algorithm is derived for the minimal period retiming by formal manipulation. Contrary to all previous algorithms, which used fixed period feasibility checking to binary-search a candidate range, the derived algorithm checks the optimality of a feasible period directly. It is much simpler and more efficient than previous algorithms. Experimental results showed that it is even faster than ASTRA, an efficient heuristic algorithm. Since the derived algorithm is incremental by nature, it also opens the opportunity to be combined with other optimization techniques.

AB - A new efficient algorithm is derived for the minimal period retiming by formal manipulation. Contrary to all previous algorithms, which used fixed period feasibility checking to binary-search a candidate range, the derived algorithm checks the optimality of a feasible period directly. It is much simpler and more efficient than previous algorithms. Experimental results showed that it is even faster than ASTRA, an efficient heuristic algorithm. Since the derived algorithm is incremental by nature, it also opens the opportunity to be combined with other optimization techniques.

KW - Algorithm derivation

KW - Clockperiod minimization

KW - Retiming

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

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

U2 - 10.1145/1297666.1297673

DO - 10.1145/1297666.1297673

M3 - Article

AN - SCOPUS:40049087121

SN - 1084-4309

VL - 13

JO - ACM Transactions on Design Automation of Electronic Systems

JF - ACM Transactions on Design Automation of Electronic Systems

IS - 1

M1 - 7

ER -

A new efficient retiming algorithm derived by formal manipulation

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this