| Title | Simultaneous Slack Budgeting and Retiming for Synchronous Circuits Optimization |
| Author | *Shenghua Liu, Yuchun Ma, Xian-Long Hong (Tsinghua University, China), Yu Wang (Tsinghua Univ., China) |
| Page | pp. 49 - 54 |
| Keyword | Retiming, Slack budgeting, gate-level synthesis, Maximum Independent Set |
| Abstract | With the challenges of growing functionality and scaling chip size, the possible performance improvements should be considered in the earlier IC design stages, which gives more freedom to the later optimization. Potential slack as an effective metric of possible performance improvements is considered in this work which, as far as we known, is the first work that maximizes the potential slack by retiming for synchronous sequential circuit. A simultaneous slack budgeting and incremental retiming algorithm is proposed for maximizing potential slack. The overall slack budget is optimized by relocating the FFs iteratively with the MIS-based slack estimation. Compared with the potential slack of a well-known min-period retiming, our algorithm improves potential slack averagely 19.6% without degrading the circuit performance in reasonable runtime. Furthermore, at the expense of a small amount of timing performance, 0.52% and 2.08%, the potential slack is increased averagely by 19.89% and 28.16% separately, which give a hint of the tradeoff between the timing performance and the slack budget. |
| Slides |
| Title | iRetILP: An Efficient Incremental Algorithm for Min-period Retiming under General Delay Model |
| Author | Debasish Das (Northwestern University, U.S.A.), Jia Wang (Illinois Institute of Technology, U.S.A.), *Hai Zhou (Northwestern University, U.S.A.) |
| Page | pp. 61 - 67 |
| Keyword | integer linear programming, algorithm design, timing optimization |
| 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 works 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. |
| Slides |