Reduction of Crosstalk Pessimism with Consideration of Logic and Timing Correlations

Accurate estimation of crosstalk has become a key issue in Static Timing Analysis of modern deep-submicron (DSM) digital circuits. The inherent logic and timing properties of the circuit are often neglected in the crosstalk estimation process resulting in an overly pessimistic analysis. False Noise Analysis aims at estimating the worst realizable crosstalk that is logically and temporally valid. Although the false noise problem has been widely studied, due to its NP-hard nature, it still lacks a very efficient solution. In this thesis, this problem of false noise is studied in detail and three novel techniques which improve the speed and accuracy of this process are proposed. The contributions of this thesis can be classified into two sections - speed improvement techniques and conservative analysis techniques.Speed improvement techniques: The novel speed improvement techniques called Simple Aggressor Ordering (SAO) and Adaptive Bounding (AB) exploit problem specific knowledge to prune a large portion of the infeasible search space of the underlying branch and bound algorithm. The beneficence of these methods lies in the fact that they simultaneously improve the speed, solvability and accuracy (stemming from the ability to solve all the cases, which are otherwise infeasible).Conservative analysis techniques: One of the drawbacks of the state-of-the-art techniques to solve the false noise problem is that they are either non-conservative or inefficient. This issue is addressed by the novel Timing Arc Based Logic Analysis (TABLA) technique that uses dedicated solvers to solve the temporal and logical problems. TABLA uses timing arcs as basic elements to perform an efficienttemporal logic analysis employing the min-max timing model using dedicated solvers for logic and timing. The proposed techniques have been implemented and tested in an industrial environment on several industrial and benchmark circuits, and results are provided.