This paper considers the timing-constrained discrete Vt replacement problem (DVRP), for leakage minimization in digital circuits. The problem is NP-complete. Earlier techniques reported for the DVRP employed iterative greedy or sensitivity-driven heuristics, that required incremental timing analysis after every iteration. The key observation reported in this paper is a good correlation between the slack distribution among gates in a given iteration and the order of gate replacements in subsequent iterations. This paper exploits the above observation to propose FastReplace, an iterative algorithm that uses adaptive lazy timing analysis to solve the DVRP. The proposed FastReplace technique, when applied to ISCAS and ITC benchmark circuits, produced solutions 9.8×and 3.1×faster as compared to the greedy technique and a commercial multi-Vt synthesis tool respectively,without impacting the solution quality.
We consider the timing-constrained discrete Vt-assignment problem for leakage minimization in digital circuits. The problem is known to be NP-complete. Greedy or Sensitivity-driven heuristics are known to be very effective for iterative Vt-assignment, with incremental timing analysis performed between the iterations. These heuristics, while offering good leakage power savings, carry a huge run-time penalty with increase in circuit size. In iterative Vt-assignment, we observe that there is a good correlation between the slack distribution in a given iteration, and the order of gate replacements in subsequent iterations. This paper proposes an algorithm, which exploits this high correlation to speed up the Vt-assignment process. The proposed algorithm uses gate replacement windows, with lazy timing evaluation, to reduce the total number of incremental STA runs during the optimization. At the end of each iteration, the successive window size is dynamically scaled up/down based on the timing updates at the end of the current window. The proposed algorithm, when applied to ISCAS/ITC circuits, significantly reduced the run-time without impacting the solution quality.