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 language | English (US) |
---|---|
Title of host publication | 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010 |
Pages | 61-67 |
Number of pages | 7 |
DOIs | |
State | Published - Apr 28 2010 |
Event | 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010 - Taipei, Taiwan, Province of China Duration: Jan 18 2010 → Jan 21 2010 |
Other
Other | 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010 |
---|---|
Country/Territory | Taiwan, Province of China |
City | Taipei |
Period | 1/18/10 → 1/21/10 |
ASJC Scopus subject areas
- Computer Science Applications
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering