A General Framework to Perform the MAX/MIN Operations in Parameterized Statistical Timing Analysis Using Information Theoretic Concepts
Nikolay Rubanov · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2011
As integrated circuit technologies are scaled down to the nanometer regime, process variations have increasing impact on circuit timing. To address this issue, parameterized statistical static timing analysis (SSTA) has been recently developed. In parameterized SSTA, process variations are represented as random variables (RVs) and timing quantities (delays and others) are expressed as functions of these variables. Most of the existing algorithms to compute theMAX/MINoperations in parameterized SSTA model spatial and path-based statistical dependencies of variation sources using the second-order statistical methods. Unfortunately, such methods have limited capabilities to determine statistical relations between RVs. This results in decreasing the accuracy of theMAX/MINalgorithms, especially when process parameters follow non-Gaussian probability density functions (PDFs) and/or affect timing quantities nonlinearly. In contrast, information theory (IT) provides powerful techniques that allow a natural PDF-based analysis of probabilistic relations between RVs. So, in this paper, we propose a new framework to perform theMAX/MINoperations based on IT concepts. The key ideas behind our framework are: 1) exploiting information entropy to measure unconditional equivalence between an actualMAX/MINoutput and its approximate parameterized representation, and 2) using mutual information to measure equivalence of actual and parameterizedMAX/MINoutputs from the viewpoint of their statistical relations to process variations. We construct a general IT-basedMAX/MINalgorithm that allows a number of particular realizations accounting for statistical properties of parameterized RVs. The experimental results validate the correctness and demonstrate a high accuracy of the new IT-based approach to compute theMAX/MIN.