Adaptive Branch and Bound Using SAT to Estimate False Crosstalk

Accurate crosstalk analysis has become a key issue in static timing analysis of modern deep-submicron 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. The problem of considering the logic correlations of the circuit to eliminate false crosstalk has been widely studied, but still lacks a very efficient solution also due to its NP-hard nature. In this paper, we propose a SAT solver based approach to efficiently solve the false crosstalk problem. We also propose a novel and very powerful bounding technique called adaptive bounding as well as an aggressor ordering technique called simple aggressor ordering for the branch and bound method running on top of the SAT solver. These techniques are proven to drastically increase the speed of false crosstalk analysis to an extent that nets with hundreds of aggressors can be handled. The results of this approach on the ISCAS89 benchmark circuits are provided.