Gate Matching Algorithm for Early False Path Detection in Statistical Static Timing Analysis

In recent years, technology scaling has been most prevalent as it offers many advantages like improved chip performance, device density, decrease in cost etc. Due to this aggressive scaling of process technology, designs have reached sub nano-meter size. In Nano scales, the process variations have more influence which has left Static Timing Analysis (STA) inadequate for analyzing these designs. So, Statistical Static Timing Analysis (SSTA), which is more accurate and faster compared to traditional Static Timing Analysis is widely used. SSTA without false path detection is found to be still pessimistic, estimating delays higher than the actual and consume more time as it considers many false paths during analysis. The paper proposes a novel algorithm that aims at reducing the overestimation of delays and execution time required for the analysis by early detection of false paths in the circuit and eliminating them from further analysis process. The algorithm was coded using the python language and the experiments were carried out on a set of dedicated combinational circuits using a 4 GB RAM, i5 processor. The Execution time, to identify the true longest path after eliminating higher delay false paths using the proposed algorithm is observed to be in the range of 1 second to 7.02 seconds.