Title :
Risk aversion min-period retiming under process variations
Author :
Wang, Jia ; Zhou, Hai
Author_Institution :
Electr. & Comput. Eng., Illinois Inst. of Technol., Chicago, IL
Abstract :
Advances in statistical timing analysis (SSTA) achieve great success in computing arrival times under variations by extending sum and maximum operations to random variables. It remains a challenge problem to apply such results in order to address the variability in circuit optimizations. In this paper, we study the statistical retiming problem, where retiming is a powerful sequential transformation that relocates flip-flops in a circuit without changing its functionality. We formulate the risk aversion min-period retiming problem under process variations based on conventional two-stage stochastic program with fixed recourse and a risk aversion objective of the clock period. We prove that the proposed problem is an integer convex program, show that the subgradient of the objective function can be derived from the combinational paths with the maximum path delay, and present a heuristic incremental algorithm to solve the proposed problem. Our approach can handle arbitrary gate delay model under process variations through sampling from a black-box and the effectiveness is confirmed by the experimental results. Further more, we point out how the current state-of-the-art SSTA techniques could be improved for future optimization algorithms when analytical models are available.
Keywords :
circuit optimisation; convex programming; flip-chip devices; integer programming; statistical analysis; timing; arbitrary gate delay model; black-box; circuit optimizations; flip-flops; heuristic incremental algorithm; integer convex program; objective function subgradient; process variations; risk aversion min-period retiming problem; sequential transformation; statistical timing analysis; two-stage stochastic program; Analytical models; Circuit optimization; Clocks; Delay effects; Flip-flops; Heuristic algorithms; Random variables; Sampling methods; Stochastic processes; Timing;
Conference_Titel :
Design Automation Conference, 2009. ASP-DAC 2009. Asia and South Pacific
Conference_Location :
Yokohama
Print_ISBN :
978-1-4244-2748-2
Electronic_ISBN :
978-1-4244-2749-9
DOI :
10.1109/ASPDAC.2009.4796526