TIMED BOOLEAN CALCULUS AND ITS APPLICATIONS IN TIMING ANALYSIS

In this paper, we introduce a formalism, called Timed Boolean Calculus (TBC), and its applications to solving the false path problem in timi ng analysis. TBC is an extension of conventional Boolean Algebra with a delay operator to facilitate modeling the timing behavior of logic c ircuits. By performing algebraic manipulations on timed Boolean expres sions, the actual maximal delays of logic circuits can be obtained. Th e delay information can then be used by a path reporting algorithm to detect the long false paths, thereby identifying the paths which need be optimized to meet timing constraints. We have developed a timing an alysis tool based on TBC and tested on ISCAS benchmarks. Experimental results are shown to justify the effectiveness and efficiency of the p roposed TBC and algorithms.