Concurrent Clock and Data (CCD) optimization is a well-adopted approach in modern commercial tools that resolves timing violations using a mixture of clock skewing and delay fixing strategies. However, existing CCD algorithms are flawed. Particularly, they fail to prioritize violating endpoints for different optimization strategies correctly, leading to flow-wise globally sub-optimal results. In this paper, we overcome this issue by presenting RL-CCD, a Reinforcement Learning (RL) agent that selects endpoints for useful skew prioritization using the proposed EP-GNN, an endpoint-oriented Graph Neural Network (GNN) model, and a Transformer-based self-supervised attention mechanism. Experimental results on 19 industrial designs in 5 − 12nm technologies demonstrate that RL-CCD achieves up to 64% Total Negative Slack (TNS) reduction and 66.5% number of violating endpoints (NVE) improvement over the native implementation of a commercial tool.

Slowdown in process scaling is putting increasing pressure on EDA tools to bridge the power, performance and area (PPA) entitlement gap of Moore's Law. State-of-the-art designs are pushing the PPA envelope to the limit, accompanied by increasing design size and complexity, and shrinking time-to-market constraints. Al/ML techniques provide a promising direction to address many of the modeling and convergence challenges seen in physical design flows. Further, the promise of intelligent design tools capable of exploring the solution space efficiently brings game-changing possibilities to next-generation design methodologies. In this talk we will discuss various challenges and opportunities in delivering best-in-class PPA closure with AI/ML augmented digital implementation tools. We will also talk about some aspects of large-scale industrial adoption of such a system and the AI capabilities needed to power these tools to minimize the need for an expert user, or endless tool iterations.

Gate sizing for timing optimization is performed extensively throughout electronic design automation (EDA) flows. However, increasing design sizes and time-to-market pressure force EDA tools to maintain pseudo-linear complexity, thereby limiting the global exploration done by the underlying sizing algorithms. Furthermore, high-performance low-power designs are pushing the envelope on power, performance and area (PPA), creating a need for last mile PPA closure using more powerful algorithms. Reinforcement learning (RL) is a disruptive paradigm that achieves high-quality optimization results beyond traditional algorithms. In this paper, we formulate gate sizing as an RL process, and propose RL-Sizer, an autonomous gate sizing agent, which performs timing optimization in an unsupervised manner. In the experiments, we demonstrate that RL-Sizer can improve the native sizing algorithms of an industry-leading EDA tool, Synopsys IC-Compiler II (ICC2), on 6 commercial designs in advanced process nodes (5 – 16nm). RL-Sizer delivers significantly better total negative slack (TNS) and number of violating endpoints (NVEs) on 4 designs with negligible power overhead, while achieving parity on athe others.

Modern designs are increasingly reliant on physical design (PD) tools to derive full technology scaling benefits of Moore's Law. Designers often perform power, performance, and area (PPA) exploration through parallel PD runs with different tool configurations. Efficient exploration of PPA is mission-critical for chip designers who are working with stringent time-to-market constraints and finite compute resources. Therefore, a framework that can accurately predict a “doomed run” (i.e., will not meet the PPA targets) at early phases of the PD flow can provide a significant productivity boost by enabling early termination of such runs. Multiple QoR metrics can be leveraged to classify successful or doomed PD runs. In this paper, we specifically focus on the aspect of timing, where our goal is to identify the PD runs that cannot achieve end-of-flow timing results by predicting the post-route total negative slack (TNS) values in early PD phases. To achieve our goal, we develop an end-to-end machine learning (ML) framework that performs TNS prediction by modeling PD implementation as a sequential flow. Particularly, our framework leverages graph neural networks (GNNs) to encode netlist graphs extracted from various PD phases, and utilize long short-term memory (LSTM) networks to perform sequential modeling based on the GNN-encoded features. Experimental results on seven industrial designs with 5:2 train/test split ratio demonstrate that our framework predicts post-route TNS values in high fidelity within 5.2% normalized root mean squared error (NRMSE) in early design stages (e.g., placement, CTS) on the two validation designs that are unseen during training.

Relentless pursuit of high-frequency low-power designs at advanced nodes necessitate achieving signoff-quality timing and power during digital implementation to minimize any over-design. With growing design sizes (1--10M instances), full flow runtime is an equally important metric and commercial implementation tools use graph-based timing analysis (GBA) to gain runtime over path-based timing analysis (PBA), at the cost of pessimism in timing. Last mile timing and power closure is then achieved through expensive PBA-driven engineering change order (ECO) loops in signoff stage. In this work, we explore "on-the-fly'' machine learning (ML) models to predict PBA timing based on GBA features, to drive digital implementation flow. Our ML model reduces the GBA vs. PBA pessimism with minimal runtime overhead, resulting in improved area/power without compromising on signoff timing closure. Experimental results obtained by integrating our technique in a commercial digital implementation tool show improvement of up to 0.92% in area, 11.7% and 1.16% in power in leakage- and total power-centric designs, respectively. Our method has a runtime overhead of $\sim$3% across a suite of 5--16nm industrial designs.

In modern designs, the delay of a net can vary significantly depending on its routing. This large estimation error during the pre-routing stage can often mislead the optimization of the netlist. We extend state-of-the-art interconnect-driven physical synthesis by introducing a new paradigm (namely, persistence) that relies on guaranteed net routes for the most sensitive nets while performing circuit optimization in the pre-route stage. We implemented our proposed approach in a cutting-edge industrial physical synthesis flow; this involved the automatic identification and routing of critical nets that were likely to be mispredicted, the automatic update of their routes during the subsequent pre-routing stage optimizations, and the guaranteed retention of their routes across the routing stage. Our approach achieves significant performance improvements on a suite of real-world 65nm designs, while ensuring that the impact on their routability remains negligible. Furthermore, our experimental results scale very well with design size.

Process variations cause design performance to become unpredictable in deep submicrometer technologies. Several statistical techniques (timing analysis, gate sizing, and buffer insertion) have been proposed to counter these variations during the optimization phase of the design flow to get a better timing yield. Another interesting approach to improve the timing yield is postsilicon-tunable (PST) clock tree. In this paper, we propose such an integrated framework that performs simultaneous statistical gate sizing in the presence of PST clock-tree buffers for minimizing binning yield loss (YL) and tunability costs by determining the ranges of delay tuning to be provided at each buffer. The simultaneous gate sizing and PST-buffer range determination problem is proved to be a convex-stochastic programming formulation under longest path-delay constraints and, hence, solved optimally. We further extend the formulation into a heuristic to additionally consider shortest path-delay constraints. We make experimental comparisons using nominal gate sizing followed by PST-buffer management using the work of Tsai as a base case. We take the solution obtained from this approach and perform the following: 1) sensitivity-based statistical gate sizing while retaining the PST clock tree and 2) simultaneous gate sizing and PST-buffer range determination as proposed in this paper. On an average, the base-case approach gave 23% timing YL, the sensitivity approach gave 15% YL, whereas our proposed algorithm gave only 4% YL.

Increasing effects of fabrication variability have inspired a growing interest in statistical techniques for design optimization. In this work, we propose a Monte-Carlo driven stochastic optimization framework that does not rely on the distribution of the varying parameters (unlike most other existing techniques). Stochastic techniques like Successive Sample Mean Optimization (SSMO) and Stochastic Decomposition present a strong framework for solving linear programming formulations in which the parameters behave as random variables. We consider Binning-Yield Loss (BYL) as the optimization objective and show that we can get a provably optimal solution under a convex BYL function. We apply this framework for the MTCMOS sizing problem [21] using SSMO and Stochastic Decomposition techniques. The experimental results show that the solution obtained from stochastic decomposition based framework had 0% yield-loss, while the deterministic solution [21] had a 48% yield-loss.

We have developed a new statistical timing analysis approach that does not impose any assumptions on the nature of manufacturing variability and takes into account an arbitrary model of spatial correlation as well as all types of functional correlations (e.g. reconvergence-based correlations). The starting point for statistical timing analysis is small scale Monte Carlo (MC) simulation. In order to speed-up the MC simulation process we use stratified balanced sampling and postprocessing of the simulation data using non-parametric kernel estimation. The MC simulation and the statistical analysis procedure are interleaved with the calculation of the critical paths. In order to speed up simulation, we identify and simulate only gates relevant for calculation of the clock cycle time. The application of statistical techniques enable not only accurate statistical timing analysis, but also stability and scalability analysis. The approach is evaluated using MCNC benchmarks and yields more than six orders of magnitude speed improvement compared with the standard MC simulation.

Process variations cause design performance to become unpredictable in deep sub-micron technologies. Several statistical techniques (timing analysis, gate-sizing) have been proposed to counter these variations during design optimization. Another interesting approach to improve timing yield is post-silicon tunable (PST) clock-tree. In this work, we propose an integrated framework that performs simultaneous statistical gate-sizing in presence of PST clock-tree buffers for minimizing binning-yield loss (BYL) and tunability costs by determining the ranges of tuning to be provided at each buffer. The simultaneous gate-sizing and PST bu er range deter- mination problem is proved to be a convex stochastic programming formulation under longest path delay constraints and hence solved optimally. We further extend the formulation into a heuristic to additionally consider shortest path delay constraints. We make experimental comparisons using nominal gate sizing followed by PST bu er management using [12] as a base-case. We take the solution obtained from this approach and perform 1) Sensitivity-based statistical gate-sizing while retaining the PST clock tree 2) Simultaneous gate sizing and PST buffer range determination as proposed in this work. On an average, the BYL obtained from our approach is 98% lower than the base-case ([12]) and 95% lower than the sensitivity-based algorithm. On an average the base-case approach [12] gave 22% timing yield loss (YL), the sensitivity approach gave 19% YL, where as our proposed algorithm gave only 3% YL. The total PST tuning buffer range that is allocated through the proposed algorithm is comparable to that obtained from [12]. The proposed algorithm had a 2.2x runtime speedup compared to the sensitivity-based algorithm.

Multithreshold CMOS (MTCMOS) technology has become a popular technique for standby power reduction. Sleep transistor insertion in circuits is an effective application of MTCMOS technology for reducing leakage power. In this paper, we present a fine-grained approach where each gate in the circuit is provided with an independent sleep transistor. Key advantages of this approach include better circuit slack utilization and improvements in ground-bounce-related signal integrity (which is a major disadvantage in clustering-based approaches). To this end, we propose an optimal polynomial-time fine-grained sleep transistor sizing algorithm. We also prove the selective sleep transistor placement problem as NP-complete and propose an effective heuristic. Finally, in order to reduce the sleep transistor area penalty, we propose a placement-area-constrained sleep transistor sizing formulation. Our experiments show that, on average, the sleep transistor placement and optimal sizing algorithms gave 50.9% and 46.5% savings in leakage power as compared with the conventional fixed-delay penalty algorithms for 5% and 7% circuit slowdown, respectively. Moreover, the postplacement area penalty was less than 5%, which is comparable to clustering schemes.

The impact of parameter variations on timing due to process variations has become significant in recent years. In this paper, we present a statistical timing analysis (STA) framework with quadratic gate delay models that also captures spatial correlations. Our technique does not make any assumption about the distribution of the parameter variations, gate delays, and arrival times. We propose a Taylor-series expansion-based quadratic representation of gate delays and arrival times which are able to effectively capture the nonlinear dependencies that arise due to increasing parameter variations. In order to reduce the computational complexity introduced due to quadratic modeling during STA, we also propose an efficient linear modeling driven quadratic STA scheme. We ran two sets of experiments assuming the global parameters to have uniform and Gaussian distributions, respectively. On an average, the quadratic STA scheme had 20.5times speedup in runtime as compared to Monte Carlo simulations with an rms error of 0.00135 units between the two timing cummulative density functions (CDFs). The linear modeling driven quadratic STA scheme had 51.5times speedup in runtime as compared to Monte Carlo simulations with an rms error of 0.0015 units between the two CDFs. Our proposed technique is generic and can be applied to arbitrary variations in the underlying parameters under any spatial correlation model

Very large-scale integration design optimization requires comparison of different solutions to evaluate superiority of one over the other. Typically, a solution is superior if it has a better associated timing and cost. In the presence of fabrication variability, the timing and cost of a solution become random variables with spatial and functional correlations. Therefore, the evaluation of solutions shall be performed probabilistically to determine the probability that a solution has better cost and timing. In this paper, the authors propose/evaluate three methods for fast and accurate computation of this probability: 1) regular Monte Carlo (MC) simulation (as a basis of comparison); 2) joint probability density function (jpdf) approximation using moment matching; and 3) bound-based conditional-MC simulation. They integrated these methods in a variability-driven leakage optimization framework using dual threshold voltages. Their results show that jpdf approximation is efficient; however, it results in suboptimal solutions due to lower accuracy approximating jpdf

In this paper, the classic wire-length estimation problem is addressed and a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing is proposed. These types of models are highly instrumental in formalizing a complete and consistent probabilistic approach to design automation and design closure where, along with optimizing the pertinent cost function, the associated prediction error is also considered. The wire-length prediction model was developed using a combination of parametric and nonparametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics after placement will have a particular length. The model is validated using the learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound, and therefore realistic, instances of designs. The net models were applied to the probabilistic buffer-insertion problem and substantial improvement was obtained in net delay after routing (~ 20%) when compared to a traditional bounding box (BBOX)-based buffer-insertion strategy

The impact of parameter variations on timing due to process and environmental variations has become significant in recent years. With each new technology node this variability is becoming more prominent. In this work, we present a general Statistical Timing Analysis (STA) framework that captures spatial correlations between gate delays. Our technique does not make any assumption about the distributions of the parameter variations, gate delay and arrival times. We propose a Taylor-series expansion based polynomial representation of gate delays and arrival times which is able to effectively capture the non-linear dependencies that arise due to increasing parameter variations. In order to reduce the computational complexity introduced due to polynomial modeling during STA, we propose an efficient linear-modeling driven polynomial STA scheme. On an average the degree-2 polynomial scheme had a 7.3x speedup as compared to Monte Carlo with 0.049 units of rms error w.r.t Monte Carlo. Our technique is generic and can be applied to arbitrary variations in the underlying parameters.

This paper presents a novel approach for leakage optimization through simultaneous V/sub t/ selection and assignment. V/sub t/ selection implies deciding the right value for V/sub t/ and assignment implies deciding which gates should be assigned a particular threshold voltage. We also include the effect of variability in threshold voltage on delay and leakage due to fabrication process variations in our formulations and present a scheme that lets the designer control the leakage and delay variability in his design. The proposed algorithm is a general mathematical formulation that has been shown to trivially extend to multiple threshold voltages.

Power-grid networks are very important aspects of large scale integrated systems. In the modern deep sub-micron era these networks are prone to many sources of noise hence making the voltage supply uctuate. This Vdd-Ground noise can have detrimental effect on design quality. This paper presents a unique strategy of achieving noise immunity through voltage scheduling in Data Flow Graphs (DFGs). A dynamic programming based approach is applied to obtain noise immunity by imposing a grid on the voltage axis. We also present a unique way of including resource binding information into the algorithm. Experimental results indicated that considerable amount of Vdd-noise immunity is achieved for the selected benchmarks.

Given a directed acyclic graph and different possible implementations for each node, the implementation selection problem (ISP) selects the appropriate implementation for each node such that a given global design objective is optimized, ISP is a generic formulation that is explicitly or implicitly solved in several design automation problems like leakage optimization using dual V/sub th/, gate sizing, etc. An implementation of a node results in an associated delay and perhaps cost for the node. In the presence of different sources of uncertainty and fabrication variability, fixed estimates of delays and costs of a node are extremely erroneous. We investigate a probabilistic approach to solve ISP by considering probability density functions for delays and costs of a node. We propose a dynamic-programming based approach in a probabilistic sense and introduce effective pruning criteria when dealing with probability distributions for identifying co-optimal solution at each stage. A case study of leakage optimization using dual V/sub th/ is presented where we show the effectiveness of a probabilistic approach considering V/sub th/ variability over a traditional deterministic one.

We propose a technique for optimizing the runtime in statistical timing analysis. Given a global acceptable error budget at the primary output which signifies the difference in the area of the accurate and approximate timing CDFs, we propose a formulation of budgeting this global error across all nodes in the circuit. This node error budget is used to simplify the computation of arrival time CDFs at each node using approximations. This simplification reduces the runtime of statistical timing analysis. We investigate two ways of exploiting this node error budget, firstly through piecewise linear approximation (see ibid., A. Devgan and C. Kashyap, 2003) and secondly though hierarchical quadratic approximation. Experimental results on ISCAS/MCNC benchmarks show that our approach is at most 3 times faster than accurate statistical timing analysis and had a very small error. We also found quadratic piecewise approximation to be more accurate than linear approximation but at lesser gains in runtime.

Leakage power is increasingly gaining importance with technology scaling. Multi-threshold CMOS (MTCMOS) technology has become a popular technique for standby power reduction. Sleep transistor insertion in circuits is an effective application of MTCMOS technology for reducing leakage power. In This work we present a fine grained approach where each gate in the circuit is provided an independent sleep transistor. Key advantages of this approach include better circuit slack utilization and improvements in signal integrity (which is a major disadvantage in clustering based approaches). To this end, we propose an optimal polynomial time fine grained sleep transistor sizing algorithm. We also prove the selective sleep transistor placement problem as NP-complete and propose an effective heuristic. Finally, in order to reduce the sleep transistor area penalty (which might get high since clustering is not performed), we propose a placement area constrained sleep transistor sizing formulation. Our experiments show that on an average the sleep transistor placement and optimal sizing algorithm gave 69.7% and 59.0% savings in leakage power as compared to the conventional fixed delay penalty algorithms for 5 and 7% circuit slowdown respectively. Moreover the post placement area penalty was less than 5% which is comparable to clustering schemes according to Mohab Anis et al. (2003).

We address the classic wire-length estimation problem and propose a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing. The wire-length prediction model was developed using a combination of parametric and non-parametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics obtained after placement will have a particular length. The model is validated using both learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound and therefore realistic instances of designs. We applied the net models to the probabilistic buffer insertion problem and obtained substantial improvement in net delay after routing.

Leakage power minimization has become an important issue with technology scaling. Variable threshold voltage schemes have become popular for standby power reduction. In this work we look at another emerging aspect of this potent problem which is leakage power reduction in active mode of operation. In gate level circuits, a large number of gates are not switching in active mode at any given point in time but nevertheless are consuming leakage power. We propose a fine-grained Forward Body Biasing (FBB) Scheme for active mode leakage power reduction in gate level circuits without any delay penalty. Our results show that our optimal polynomial time FBB allocation scheme results in 70.2% reduction in leakage currents. We also present a novel placement-driven FBB allocation algorithm that effectively reduces the area penalty using the post-placement area slack and results in 39.7%, 64.7% and 67.1% reduction in leakage currents for 0%, 4% and 8% area slack respectively.

In this paper, we propose a novel, empirical, and parameterizable model for estimating the probability distribution of wire length for each net in a placed netlist. The model is simple and fast to compute. We did extensive experimentation with state-of-the-art commercial (Cadence) and academic (Parquet and Labyrinth) tools and validated our model. Our distribution model was around three times more accurate than assuming half-perimeter bounding box as the fixed net-length estimate. Since the model is parameterizable it can be easily tailored for different routing tools and benchmarks. This model would be very useful in defining a full fledged probabilistic design automation methodology in which various design metrics are optimized from a probabilistic point of view. We also discuss the application of our model in a novel probabilistic approach to the buffer insertion problem.