The statistical nature of gate delays in current day technologies necessitates the use of measures, such as path criticality and node/edge criticality for timing optimization. Node criticalities are typically computed using the complementary path delay. An alternative approach to compute the criticality using the circuit delay has been recently proposed. In this paper, we discuss in detail, the use of circuit delay to compute node criticalities and show that the criticality thus found is not equal to the conventional measure found using complementary path delay. However, there is a monotonic relationship between them and the two measures can be used interchangeably. We derive new bounds for the global criticality and propose a pruning algorithm based on these bounds to improve the accuracy and speed of computation. The use of this pruning technique results in a significant speedup in criticality computations. We obtain an order of magnitude average speedup for ISCAS benchmarks. © 2014 IEEE.

Vinita Vasudevan

Department of Electrical Engineering

Electric network analysis

AS paths

Circuit delays

Gate delays

PATH DELAY

PRUNING ALGORITHMS

PRUNING TECHNIQUES

STATISTICAL TIMING

Timing optimization

Criticality (nuclear fission)

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Statistical Criticality Computation Using the Circuit Delay

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Due to process variations, every path in the circuit is associated with a probability of being critical and a measure of this probability is the criticality of the path. Identification of critical paths usually proceeds in two steps, namely, generation of a candidate path set followed by computation of path criticality. As criticality computation is expensive, the candidate path set is chosen using simpler metrics. However, these metrics are not directly related to path criticality and, often, the set also contains low criticality paths that do not need to be tested. In this article, we propose a hierarchical technique that directly gives all paths above a global criticality threshold. The circuit is divided into disjoint groups at various levels. We show that the criticality of a group at each level of hierarchy can be computed using criticality of the parent group and the local complementary delay within the group. Low criticality groups are pruned at every level, making the computation efficient. This recursive partitioning and group criticality computation is continued until the group criticality falls below a threshold. Beyond this, the path selection within the group is done using branch-and-bound algorithm with global criticality as the metric. This is possible, since our method for criticality computation is very efficient. Unlike other techniques, path selection and criticality computation are integrated together so that when the path selection is complete, path criticality is also obtained. The proposed algorithm is tested with ISCAS'85, ISCAS'89, and ITC'99 benchmark circuits and the results are verified using Monte Carlo simulation. The experimental results suggest that the proposed method gives better accuracy on average with around 90% reduction in run-time. © 2017 ACM.

ACM Transactions on Design Automation of Electronic Systems

A hierarchical technique for statistical path selection and criticality computation

In this article, we derive a simple and accurate expression for the change in timing yield due to a change in the gate delay distribution. It is based on analytical bounds that we have derived for the moments of the circuit and path delay. Based on this, we propose computationally efficient algorithms for (1) discrete gate sizing and (2) simultaneous gate sizing and threshold voltage (VT) assignment so that the circuit meets a timing yield specification under parameter variations. The use of this analytical yield gradient within a gradient-based timing yield optimization algorithm results in a significant improvement in the runtime as compared to the numerical method, while achieving the same final yield. It also allows us to explore a larger search space in each iteration more efficiently, which is required in the case of simultaneous resizing and VT assignment. We also propose heuristics for resizing/changing the VT of multiple gates in each iteration. This makes it possible to optimize the timing yield for large circuits. Results on ITC '99 benchmarks show that the proposed multinode resizing algorithm results in a significant improvement in the runtime with a marginal average area penalty and no cost to the final yield achieved. © 2016 ACM.

Efficient algorithms for discrete gate sizing and threshold voltage assignment based on an accurate analytical statistical yield gradient

Statistical timing yield optimization algorithms require computation of yield-gradient for gate resizing in every iteration. Numerical yield-gradients account for the effects of fan-in and fan-out gates, but are computationally expensive. In this paper, we formulate a more accurate analytical expression for the yield-gradient (termed effective yield-gradient) that includes these effects. Based on the statistical properties of the path delay variations, we derive a simplified expression for the effective yield gradient that is accurate and results in an improvement in the run-time. Using these simplified expressions, we also propose an algorithm for resizing multIPle gates in an iteration. Results on ITC99 and ISCAS85 benchmarks show that the proposed multi-node resizing algorithm results in 83% improvement in the runtime with an average area penalty of 3% and no cost to the final yield achieved. © 2015 ACM.

Proceedings - Design Automation Conference

An efficient algorithm for statistical timing yield optimization

Path Criticality Computation in Parameterized Statistical Timing Analysis Using a Novel Operator

Proceedings of the International Conference on Computer-Aided Design - ICCAD '12

On the computation of criticality in statistical timing analysis

Proceedings of the 49th Annual Design Automation Conference on - DAC '12

Reversible statisticalmax/minoperation

16th Asia and South Pacific Design Automation Conference (ASP-DAC 2011)

Path criticality computation in parameterized statistical timing analysis

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Information for authors

Statistical criticality computation using the circuit delay

Journal	Data powered by TypesetIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Publisher	Data powered by TypesetInstitute of Electrical and Electronics Engineers Inc.
ISSN	02780070
Open Access	No