Incremental circuit simulation and timing analysis techniques

Most integrated circuit designs must be iterated in the design cycle for tens or even hundreds times to correct all of the violations and/or to optimize the performance. At the latter portion of the design cycles, only small changes are made and most of the circuit characteristics remain unchanged. However, normal CAD tools would still take the same amount of time to re-examine the slightly modified design. Incremental CAD algorithms are based on the idea that it usually takes much less time to update invalid information than to do a complete analysis if the worst case implication of a design change can be identified efficiently. In our research, we realize that if an algorithm can be carefully decomposed into several independent phases, then some phases may be either totally skipped or easily updated to reduce the execution time and to give the designers faster feedback. In addition, for some applications, the results generated in the previous analysis can provide a good initial solution for the new run.The focus of this research is to exploit all of these three properties to perform incremental circuit simulation and incremental timing analysis. A modified incremental-in-space algorithm is developed by using the event-driven techniques in iSPLICE3 to dynamically determine a practical worst-case boundary of the influence of a design change during the incremental simulation run. In addition, based on the RELAX program, two new schemes are developed to handle globally modified designs and to reduce the high overhead associated with incremental-in-time schemes by using the waveform relaxation and windowing techniques. Researches in timing analysis focus on the false path problem where only the longest paths down which signals can actually propagate are reported. We have developed two new efficient algorithms for detecting the statically sensitizable paths and the viable critical paths, using the binary decision diagrams (BDD).U of I OnlyETDs are only available to UIUC Users without author permissio