This paper presents an approach to dynamically generating representative external driving cell and external wire parasitic assertions for the ports of sub-blocks of a hierarchical design. The assertions are based on a technology lookup table and use attributes of the port and the hierarchical wire connected to the port as keys. A concept of reverse timing calculation at the input of the driving cell is described that facilitates the approach to drive efficient timing optimization of boundary paths of design sub-blocks. Experimental results in an industrial timing environment demonstrate significantly improved timing optimization accuracy when compared to prior work.

Traditional statistical static timing analysis (SSTA) using available single-input switching (SIS) based gate delay libraries either ignore timing impact from multiple-input switching (MIS) or use single-corner (deterministic) models for MIS consideration. This paper presents a method for modeling the impact of MIS on statistical timing accurately using concepts of convolution and chain ruling. Experimental results in a commercial SSTA framework demonstrate negligible run-time overheads of modeling MIS while accurately exposing timing slack optimism in an SIS based flow of up to 17 pico-seconds on designs mapped to a 14 nanometer technology library. Prediction of timing critical paths due to MIS show excellent correlation to silicon hardware. Comparisons with prior work illustrate the accuracy improvements of the presented work.

Given ever-increasing circuit complexities, recent trends are driving the requirement for distributed timing analysis (DTA) in electronic design automation (EDA) tools. However, DTA has received little research attention so far and remains a critical problem. In this paper, we introduce a DTA framework for large designs. Our framework supports (1) general design partitions in distributed file systems, (2) non-blocking IO with event-driven loop for effective communication and computation overlap, and (3) an efficient messaging interface between application and network layers. The effectiveness and scalability of our framework has been evaluated on large hierarchical industry designs over a cluster with hundreds of machines.

Path tracing is a key requirement in providing various functionalities in a Static Timing Analysis (STA) tool. With growing design sizes and advancements in STA techniques like statistical timing analysis, path tracing techniques need to be more efficient and accurate. Naïve extensions of path tracing techniques for statistical timing analysis are found to be inefficient and inaccurate. In this paper, we present a novel Statistical Path Tracing (SPT) approach and illustrate its application in Common Path Pessimism Removal (CPPR). We demonstrate that SPT is more efficient and accurate when compared to a Deterministic Path Tracing (DPT) approach.

This paper considers the practical nuances of using current source gate models in an industrial statistical timing analysis environment. Specifically, the memory overhead of a naive implementation combining statistical and current source models to obtain and store gate output waveforms is found to be impractical for large microprocessor designs. A study is performed to observe variational gate output waveforms, and a technique is presented to store the waveforms in a memory efficient manner with minimal accuracy impact. The presented technique is validated over a set of 14 nanometer designs, and has enabled the usage of current source models in our industrial statistical timing analysis flow. Results demonstrate slack accuracy improvements of up to 17 picoseconds with a 1.15X run-time overhead and 1.1 gigabytes per million-gates memory overhead in comparison to an existing flow.

Timing macro-modeling captures the timing characteristics of a circuit in a compact form for use in a hierarchical timing environment. At the same time, statistical timing provides coverage of the impact from variability sources with the goal of enabling higher chip yield. This paper presents an efficient and accurate method for generation and use of statistical timing macro-models. Results in a commercial timing analysis framework with non-separable statistical timing models demonstrate average performance improvements of 10× when using the model with less than 0.3 picosecond average and 5.5 picosecond maximum accuracy loss, respectively.

To protect against modeling limitations in considering design and electrical complexities, as well as variability, early and late signal propagation times in static timing analysis are often made pessimistic by addition of extra guard bands. However, these forced early-late splits introduce excessive and undesired pessimism. To this end, common path pessimism removal (CPPR) eliminates guaranteed redundant pessimism during timing analysis. This session aims to highlight the importance of CPPR during timing analysis, as well as explore novel methods for fast CPPR from the top performers of the TAU 2014 timing contest.

To margin against modeling limitations in considering design and electrical complexities (e.g., crosstalk coupling, voltage drops) as well as variability (e.g., manufacturing process, environmental), "early" and "late" signal propagation delays in static timing analysis are often made pessimistic by addition of extra guard bands. While these forced "early-late splits" provide desired margins, the splits applied across the entire design introduce excessive and undesired pessimism. To this end, "common path pessimism removal (CPPR)" eliminates the redundant pessimism during timing analysis.

Statistical static timing analysis (SSTA) involves computation of maximum (max) and minimum (min) of Gaussian random variables. Typically, the max or min of a set of Gaussians is performed iteratively in a pair-wise fashion, wherein the result of each pair-wise max or min operation is approximated to a Gaussian by matching moments of the true result obtained using Clark's approach [1]. The approximation error in the final result is thus a function of the order in which the pair-wise operations are performed.

Timing analysis is a key component of any integrated circuit (IC) chip design-closure flow, and is employed at various stages of the flow including pre/post-route timing optimization and timing signoff. While accurate timing analysis is important, the run-time of the analysis is equally critical with growing chip design sizes and complexity (for example, increasing number of clocks domains, voltage islands, etc.). In addition, the increasing significance of variability in the chip manufacturing process as well as environmental variability necessitates use of variation aware techniques (e.g. statistical, multi-corner) for chip timing analysis which significantly impacts the analysis run-time.

The increasing significance of variability in modern sub-micron manufacturing process has led to the development and use of statistical techniques for chip timing analysis and optimization. Statistical timing involves fundamental operations like statistical-add, sub, max and min to propagate timing information (modeled as random variables with known probability distributions) through a timing graph model of a chip design. Although incremental timing during optimization updates timing information of only certain parts of the timing-graph, lack of established reversible statistical max or min techniques forces more-than-required computations.

Statistical static timing analysis (SSTA) is ideal for random variations but is not suitable for environmental variations like Vdd and temperature. SSTA uses statistical approximation, according to which circuit timing is predicted accurately only for highly probable combinations of variational parameters. SSTA is not able to handle accurately deterministic sources of variation like supply voltage. This paper presents a novel technique for modeling nonseparable deterministic and statistical variations in single timing run.

In this paper, we consider the problem of identifying a feasible set of aggressor nets that would induce maximum crosstalk noise or delay pushout on a coupled victim net, under given logical constraints. We present a novel mathematical formulation of this problem and propose a Lagrangian relaxation-based approach for solving it efficiently and optimally. Experimental results show that the proposed approach is run-time efficient by a factor of up to 800 times in comparison to an exhaustive search approach and reduces timing pessimism by up to 36%. We also formulate and solve this problem while considering the noise susceptibility of the victim's receiving gate.

In this paper, a timing-dependent dynamic power estimation framework that considers the impact of coupling in combinational circuits is proposed. Relative switching activities and delays of coupled interconnects significantly affect dynamic power dissipation in parasitic coupling capacitances (coupling power). To enable capturing the switching and timing dependence, detailed switching distributions and timing information are essential in accurate estimation of dynamic power consumption. An approach to efficiently represent and propagate switching and timing distributions through circuits is developed. Based on propagated switching and timing distributions, power consumption in coupling capacitances is accurately calculated. Experimental results using ISCAS'85 benchmarks demonstrate that ignoring timing dependence of coupling power consumption can cause up to 25% error in dynamic power estimation (corresponding to 59% error in coupling power estimation).

This paper introduces an accurate and efficient electrical analysis of logic gates modeled as Multiple Voltage Threshold Models (MVTM) loaded by the associated interconnect. MVTMs formalize a class of gate models which include the existing industry standards, such as CCS and ECSM driver models as special cases. The analysis technique relies on primary MVTM characterization data and does not require explicit instantiation of controlled current source models. Therefore, the method is more accurate, efficient, and general than traditional transient analysis. The theoretical results are validated by detailed simulations and use within full chip timing analysis.

In this paper, we consider the problem of selecting a set of aggressor nets that maximize crosstalk induced noise or delay pushout on a coupled victim net, under given logical constraints. We formulate the problem mathematically, and propose efficient Lagrangian Relaxation and network flow based approaches that guarantee an optimal solution. We also formulate and solve this problem while considering the noise susceptibility of the victimpsilas receiving gate. Experimental results show that the proposed approaches are run-time efficient by factors of up to 800times in comparison to an exhaustive search approach, and reduce timing pessimism by up to 36%.

The modern era of embedded system design is geared toward the design of low-power systems. One way to reduce power in an application-specified integrated circuit (ASIC) implementation is to reduce the bit-width precision of its computation units. This paper describes algorithms to optimize the bit widths of fixed-point variables for low power in a SystemC-based ASIC design environment. We propose an optimal bit-width allocation algorithm for two variables and a greedy heuristic that works for any number of variables. The algorithms are used in the automation of converting floating-point SystemC programs into ASIC synthesizable SystemC programs. Expected inputs are profiled to estimate errors in the finite precision conversions. Experimental results for the tradeoffs between quantization error, power consumption, and hardware resources used are reported on a set of four SystemC benchmarks that are mapped onto a 0.18-mum ASIC cell library from Artisan Components. We demonstrate that it is possible to reduce the power consumption by 50% on the average by allowing roundoff errors to increase from 0.5% to 1%

This paper quantifies the approximation error when results obtained by Clark (1961) are employed to compute the maximum (max) of Gaussian random variables, which is a fundamental operation in statistical timing. We show that a finite lookup table can be used to store these errors. Based on the error computations, approaches to different orderings for pairwise max operations on a set of Gaussians are proposed. Experimental results show accuracy improvements in the computation of the max of multiple Gaussians, in comparison to the traditional approach. In addition, we present an approach to compute the tightness probabilities of Gaussian random variables with dynamic runtime-accuracy tradeoff options. We replace required numerical computations for their estimations by closed form expressions based on Taylor series expansion that involve table lookup and a few fundamental arithmetic operations. Experimental results demonstrate an average speedup of 2 using our approach for computing the maximum of two Gaussians, in comparison to the traditional approach, without any accuracy penalty.

The modern era of embedded system design is geared towards design of low-power systems. One way to reduce power in an ASIC implementation is to reduce the bit-width precision of its computation units. This paper describes algorithms to optimize the bit-widths of fixed point variables for low power in a SystemC design environment. We propose an algorithm for optimal bit width precision for two variables and a greedy heuristic which works for any number of variables. The algorithms are used in the automation of converting floating point SystemC programs into ASIC synthesizable SystemC programs. Expected inputs are profiled to estimate errors in the finite precision conversions. Experimental results on the trade-offs between quantization error, power consumption and hardware resources used are reported on a set of four SystemC benchmarks that are mapped onto 0.18 micron ASIC cell library from Artisan Components. We demonstrate that it is possible to reduce the power consumption by 50% on average by allowing round-off errors to increase from 0.5% to 1%. 1

In this paper, we propose a timing dependent dynamic power estimation framework that considers the impact of coupling and glitches. We show that relative switching activities and times of coupled nets significantly affect dynamic power consumption, and neither should be ignored during power estimation. To capture the timing dependence, an approach to efficient representation and propagation of switching-window distributions through a circuit, considering coupling induced delay variations, is developed. Based on the propagated switchingwindow distributions, power consumption in charging or discharging coupling capacitances is calculated, and accounted for in the total power. Experimental results for the ISCAS'85 benchmarks demonstrate that ignoring the impact of timing dependent coupling on power can cause up to 59% error in coupling power estimation (up to 25% error in total power estimation).

One of the major issues faced by the semiconductor industry today is that of reducing chip yields. As the process technologies have scaled to smaller feature sizes, chip yields have dropped to around 50% or less. This figure is expected to decrease even further in future technologies. To attack this growing problem, we develop four yield-aware micro architecture schemes for data caches. The first one is called yield-aware power-down (YAPD). YAPD turns off cache ways that cause delay violation and/or have excessive leakage. We also modify this approach to achieve better yields. This new method is called horizontal YAPD (H-YAPD), which turns off horizontal regions of the cache instead of ways. A third approach targets delay violation in data caches. Particularly, we develop a variable-latency cache architecture (VACA). VACA allows different load accesses to be completed with varying latencies. This is enabled by augmenting the functional units with special buffers that allow the dependants of a load operation to stall for a cycle if the load operation is delayed. As a result, if some accesses take longer than the predefined number of cycles, the execution can still be performed correctly, albeit with some performance degradation. A fourth scheme we devise is called the hybrid mechanism, which combines the YAPD and the VACA. As a result of these schemes, chips that may be tossed away due to parametric yield loss can be saved. Experimental results demonstrate that the yield losses can be reduced by 68.1% and 72.4% with YAPD and H-YAPD schemes and by 33.3% and 81.1% with VACA and Hybrid mechanisms, respectively, improving the overall yield to as much as 97.0%

This paper presents a gate-sizing algorithm for coupling-noise reduction, which optimizes the area or power consumption (represented as a weighted sum of gate sizes) of a circuit while ensuring that its timing constraints are met. A problem for gate-size optimization under coupling-noise and timing constraints is formulated, and is broken down into two subproblems of gate-size optimization under noise and timing constraints, respectively. The subproblem of gate-size optimization under noise constraints is solved as a fixpoint computation problem on a complete lattice. The proposed algorithm to solve this problem is guaranteed to yield the optimal solution, provided it exists. The subproblem for circuit optimization under timing constraints is considered as a geometrical programming problem. The solutions to the two problems are finally combined to solve the original problem in a Lagrangian relaxation (LR) framework. Experimental results demonstrating the effectiveness of the algorithms are reported for the International Symposium on Circuits and Systems (ISCAS) benchmarks and larger circuits. The obtained results are compared to the approach where successive iterations of gate sizing are performed for timing and for noise reduction independently. This alternative design approach is driven by the algorithms used to solving the mentioned subproblems, respectively.

As technology scales to smaller dimensions, increasing process variations and coupling induced delay variations make timing verification extremely challenging. In this paper, the authors establish a theoretical framework for statistical timing analysis with coupling. They prove the convergence of their proposed iterative approach and discuss implementation issues under the assumption of a Gaussian distribution for the parameters of variation. A statistical timer based on their proposed approach is developed and experimental results are presented for the International Symposium on Circuits and Systems benchmarks. They juxtapose their timer with a single pass, noniterative statistical timer that does not consider the mutual dependence of coupling with timing, and another statistical timer that handles coupling deterministically. Monte Carlo simulations reveal a distinct gain (up to 24%) in accuracy by their approach in comparison to the others mentioned

In this paper, we propose a statistical gate sizing approach to maximize the timing yield of a given circuit, under area constraints. Our approach involves statistical gate delay modeling, statistical static timing analysis, and gate sizing. Experiments performed in an industrial framework on combinational International Symposium on Circuits and Systems (ISCAS'85) and Microelectronics Center of North Carolina (MCNC) benchmarks show absolute timing yield gains of 30% on the average, over deterministic timing optimization for at most 10% area penalty. It is further shown that circuits optimized using our metric have larger timing yields than the same optimized using a worst case metric, for iso-area solutions. Finally, we present an insight into statistical properties of gate delays for a commercial 0.13-mum technology library which intuitively provides one reason why statistical timing driven optimization does better than deterministic timing driven optimization

This paper presents a post-route gate-sizing algorithm for coupling-noise reduction that constrains the yield loss under process variations. Algorithms for coupling-noise reduction which do not consider uncertainty in the manufacturing process can make a circuit susceptible to failure. Using probabilistic models, the coupling-noise reduction problem is solved as a fixpoint computation problem on a lattice. A novel gate-sizing algorithm with low area overhead is proposed for coupling-noise reduction under uncertainty. Experimental results are reported for the ISCAS benchmarks and larger circuits with comparisons to traditional approaches.

Variability in the chip design process has been relatively increasing with technology scaling to smaller dimensions. Using worst case analysis for circuit optimization severely over-constrains the system and results in solutions with excessive penalties. Statistical timing analysis and optimization have consequently emerged as a refinement of the traditional static timing approach for circuit design optimization. In this paper, we propose a statistical gate sizing methodology for timing yield improvement. We build statistical models for gate delays from library characterizations at multiple process corners and operating conditions. Statistical timing analysis is performed, which drives gate sizing for timing yield optimization. Experimental results are reported for the ISCAS and MCNC benchmarks. In addition, we provide insight into statistical properties of gate delays for a given technology library which intuitively explains when and why statistical optimization improves over static timing optimization.

As technology scales to smaller dimensions, increasing process variations, coupling induced delay variations and multiple input switching effects make timing verification extremely challenging. In this paper, we establish a theoretical framework for statistical timing analysis with coupling and multiple input switching. We prove the convergence of our proposed iterative approach and discuss implementation issues under the assumption of a Gaussian distribution for the parameters of variation. A statistical timer based on our proposed approach is developed and experimental results are presented for the IS-CAS benchmarks. We juxtapose our timer with a single pass, non iterative statistical timer that does not consider the mutual dependence of coupling with timing and another statistical timer that handles coupling deterministically. Monte Carlo simulations reveal a distinct gain (up to 24%) in accuracy by our approach in comparison to the others mentioned.

Most practical FPGA designs of digital signal processing applications are limited to fixed-point arithmetic owing to the cost and complexity of floating-point hardware. While mapping DSP applications onto FPGAs, a DSP algorithm designer, who often develops his applications in MATLAB, must determine the dynamic range and desired precision of input, intermediate and output signals in a design implementation to ensure that the algorithm fidelity criteria are met. The first step in a flow to map MATLAB applications into hardware is the conversion of the floating-point MATLAB algorithm into a fixed-point version using quantizers from the Filter Design and Analysis (FDA) Toolbox for MATLAB. We describe an approach to automate the conversion of floating-point MATLAB programs into fixed-point, for mapping to FPGAs by profiling the expected inputs to estimate errors. Our algorithm attempts to minimize the hardware resources while constraining the quantization error within a specified limit.

This work presents a post-route, timing-constrained gate-sizing algorithm for crosstalk reduction. Gate-sizing has emerged as a practical and feasible method to reduce crosstalk in deep sub-micron VLSI circuits. It is however critical to ensure that the timing constraints of the circuit are not violated after sizing. We present an iterative gate-sizing algorithm for crosstalk reduction based on Lagrangian relaxation that optimizes area and power while ensuring that the given timing constraints are met. Experimental results demonstrating the effectiveness of the algorithm are reported for the ISCAS benchmarks and other large circuits with comparisons to an alternative design methodology.

Coupling-noise reduction has emerged as a critical design problem with VLSI feature sizes shrinking rapidly and with the use of more aggressive and less noise-immune circuits. Since coupling-noise on a net depends on driving gate-sizes of the net itself and all nets coupled to it, gate-sizing emerges as an effective approach to coupling-noise reduction. It is an attractive approach since re-routing is not required. In this paper, we propose an iterative gate-sizing algorithm to determine optimal gate-sizes for coupling-noise reduction. We consider gate-sizing as a fixpoint computation on a complete lattice and the beauty of the iterative gate-sizing algorithm lies in its ability to guarantee the optimal solution, provided it exists. The effectiveness of the algorithm is validated experimentally by simulations on multiple large circuits.