DocumentCode :
1570466
Title :
iRetILP: An efficient incremental algorithm for min-period retiming under general delay model
Author :
Das, Daebasish ; Wang, Jia ; Zhou, Hai
Author_Institution :
Place & Route Group, Mentor Graphics, San Jose, CA, USA
fYear :
2010
Firstpage :
61
Lastpage :
67
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 100× faster than the previous algorithm for small circuits and is highly scalable to large circuits in term of memory consumption and running time.
Keywords :
VLSI; delays; flip-flops; integer programming; linear programming; constant delay model; dense path graph; flip-flops; general delay model; iRetILP; incremental algorithm; integer linear programming; min-period retiming; minimal clock period; retiming optimization; sequential transformation; ultra deep submicron VLSI designs; Clocks; Delay effects; Delay estimation; Design optimization; Flip-flops; Integer linear programming; Integrated circuit interconnections; Propagation delay; Registers; Timing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Design Automation Conference (ASP-DAC), 2010 15th Asia and South Pacific
Conference_Location :
Taipei
Print_ISBN :
978-1-4244-5765-6
Electronic_ISBN :
978-1-4244-5767-0
Type :
conf
DOI :
10.1109/ASPDAC.2010.5419917
Filename :
5419917
Link To Document :
بازگشت