iRetILP: An efficient incremental algorithm for min-period retiming under general delay model

Debasish Das*, Jia Wang, Hai Zhou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Retiming is one of the most powerful sequential transformations that relocates flip-flops in a circuit without changing its functionality. The min-period retiming problem seeks a solution with the minimal clock period. Since most min-period retiming algorithms assume a simple constant delay model that does not take into account many prominent electrical effects in ultra deep sub micron vlsi designs, a general delay model was proposed to improve the accuracy of the retiming optimization. Due to the complexity of the general delay model, the formulation of min-period retiming under such model is based on integer linear programming (ILP). However, because the previous ILP formulation was derived on a dense path graph, it incurred huge storage and running time overhead for the ILP solvers and the application was limited to small circuits. In this paper, we present the iRetILP algorithm to solve the min-period retiming problem efficiently under the general delay model by formulating and solving the ILP problems incrementally. Experimental results show that iRetILP is on average 100x faster than the previous algorithm for small circuits and is highly scalable to large circuits in term of memory consumption and running time.

Original languageEnglish (US)
Title of host publication2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010
Pages61-67
Number of pages7
DOIs
StatePublished - Apr 28 2010
Event2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010 - Taipei, Taiwan, Province of China
Duration: Jan 18 2010Jan 21 2010

Other

Other2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010
Country/TerritoryTaiwan, Province of China
CityTaipei
Period1/18/101/21/10

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'iRetILP: An efficient incremental algorithm for min-period retiming under general delay model'. Together they form a unique fingerprint.

Cite this