Accurate delay analysis with distributed RC delay can be computationally expensive, and can contribute the majority of the total runtime for gate sizers. Recent works have shown that Lagrangian relaxation (LR)-based gate sizers have produced designs with the lowest power on average. But they are also very slow due to a large number of expensive timing updates spread across several tens of iterations. In this paper, we develop an LR-based discrete gate sizer for fast timing and power reduction. Our gate sizer is multithreaded and is equipped with parallelization enabling techniques, namely mutual exclusion edge (MEE) assignment and directed acyclic graph (DAG)-based netlist traversal (DNT). MEEs are dummy edges assigned to improve load sharing among different threads. DNT facilitates simultaneous resizing of gates belonging to different topological levels. Our Lagrange multiplier update strategy enables rapid convergence of our timing and power recovery algorithms. To reduce the runtime of timing updates, we propose a simple and fast-to-compute effective capacitance model. We further propose mechanisms to calibrate timing models to improve their accuracy. By calibrating the internal timing models only twice, our proposed gate sizing flow facilitates extremely fast design optimization. We benchmark our gate sizer using the ISPD 2012 and 2013 gate sizing contest benchmark suites. Compared to the state-of-the-art gate sizer, our proposed gate sizer is on average 15× faster and the optimized designs have 2.5% higher leakage power. Since we tradeoff timing accuracy for larger runtime speedup, our optimized designs have small timing violations.

In recent years, an increasing number of papers have focused on the cell selection problem. However, previous papers fail to consider the actual problems of performing cell selection in the after placement and CTS optimization stages of industrial designs. This paper discusses the obstacles found when applying state-of-the-art Lagrangian relaxation-based cell selection in a real industrial flow. Solutions to such obstacles are presented, filling the gap in previous literature.

Timing-constrained power-driven gate sizing has aroused lot of research interest after the recent two discrete gate sizing contests organized by International Symposium on Physical Design. Since then, there are plenty of research papers published and new algorithms are proposed based on the ISPD 2013 contest formulation. However, almost all (new and old) papers in the literature ignore the details of how power-driven gate sizing fits in industrial physical synthesis flows, which limits their practical usage. This paper aims at filling this knowledge gap. We explain our approach to integrate a state-of-the-art Lagrangian Relaxation-based gate sizing into our actual physical synthesis framework, and explain the challenges and issues we observed from the point of view of VLSI design flows.

This paper presents a fast and effective approach to gate-version selection and threshold voltage, Vth, assignment. In the proposed flow, first, a solution without slew and load violation is generated. Then, a Lagrangian Relaxation (LR) method is used to reduce leakage power and achieve timing closure while keeping the circuit no or few violations. If the set of gate-versions given by LR produces a circuit with negative slack, a timing recovery method is applied to find near zero positive slack. The solution without negative slack is finally introduced to a power reduction step. For the ISPD 2012 Contest benchmarks, the leakage power of our solutions is, on average, 9.53% smaller than and 12.45% smaller than . The sizing produced using our approach achieved the first place in the ISPD 2013 Discrete Gate Sizing Contest with, on average, 8.78% better power results than the second place tool. With new timing calculation applied, this flow can provide, on average, an extra 9.62% power reduction compared to the best Contest results. This flow is also the first gate sizing method to report violation-free solutions for all benchmarks of the ISPD 2013 Contest.

This paper presents a flow composed by a set of heuristic algorithms to address the discrete gate sizing and Vt assignment problem for leakage power minimization while satisfying delay, load and slew constraints. The proposed flow combines the Fanout-of-4 empirical rule, the Logical Effort concept, a Simulated Annealing (SA) as the main engine, as well as a new set of specific optimization strategies to solve this difficult problem as formulated in the 2012 ISPD Gate Sizing Contest. The main contribution of this work is to show how a sequence of Simulated Annealing runs, starting from a solution given by Logical Effort, Fanout of-4 rule, and employing a set of new techniques can be used together to solve gate sizing problems of up to a million gates. New methods are presented to solve violations during the Annealing and a dynamic cost function is presented that helps SA to achieve different conflicting tasks during the optimization. The entire flow was able to achieve the second and first ranks in the ISPD 2012 Contest. A set of different experiments is presented to support design decisions and highlight the quality of the achieved results.

This work presents methods to identify and treat circuit areas that have high overflow and interconnect demand, during global routing step. In that way, two cost pre-allocation techniques are presented: the first is applied during the pre-routing congestion estimation step of the global routing flow; the second technique will act during the iterative routing phase, where the the congestion is updated on each routing round and the congestion hot spots can be identified. Since the congestion hot spots are identified, a cost calibration step is executed using the proposed congestion look-ahead techniques. The focus of these algorithms is to speed up the convergence of the global routing solution while trying to reduce the side effects in wire length. Our experiments shows a speed up of up to 1.357x with 1.39% of maximum increase in wirelength when compared to the reference implementation for the ISPD 2008 benchmarks.

Despite the existence of several other alternatives for estimating delay of interconnects, the Elmore Delay Model still has been used for comparison of routing algorithms. The criterion used to establish Elmore's model as a confident metric for this purpose is the so-called Fidelity Property. In this work we investigate the Fidelity Property using nowadays interconnect parameters, in four routing scopes. For the first time the Fidelity is evaluated in actual algorithms comparison, one of the main utilities it was established for. What is found is that the original methodology used to evaluate this property hides a significant standard deviation. This standard deviation strongly impacts the capacity of Elmore's model to provide good certainty of choosing the best routing solutions among several ones. Additionally, the experiments of algorithms comparison show that different routing alternatives are appropriated for different routing scopes, with respect to metal layers, driver strengths and routing areas.