TY - GEN
T1 - iRetILP
T2 - 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010
AU - Das, Debasish
AU - Wang, Jia
AU - Zhou, Hai
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77951221324&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951221324&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2010.5419917
DO - 10.1109/ASPDAC.2010.5419917
M3 - Conference contribution
AN - SCOPUS:77951221324
SN - 9781424457656
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 61
EP - 67
BT - 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010
Y2 - 18 January 2010 through 21 January 2010
ER -