False path detection program

(1) Field of the Invention

The present invention relates to a false path detection program, and more particularly, to a false path detection program used for the timing analysis and verification of a digital circuit.

(2) Description of the Related Art

When designing semiconductor devices such as LSI circuits, CAD (Computer Aided Design) is used. Semiconductor circuits designed by CAD often include false paths that are not used in their functions.

CAD has the function of false path detection and timing analysis. With this function, where the maximum delay time from the input to the output of a certain circuit involves a delay time attributable to a false path, for example, the maximum delay time can be shortened so that the circuit can operate in a time shorter than the maximum delay time.

The following three methods are known as conventional methods for false path detection and timing analysis: The first method is to determine whether each of paths from the input to the output of a circuit is a false path or not (see, e.g., Unexamined Japanese Patent Publication No. H08-180098 (paragraph nos. [0014]-[0031]; FIGS. 2-11), and H.-C. Chen and D. H.-C. Du, Path sensitization in critical path problem, IEEE Transactions on Computer-Aided Design of Integrated Circuits, 12(2): 196-207, February 1993). There has also been proposed a method of using higher-level operation description information in determining whether each path is a false path or not (see, e.g., Unexamined Japanese Patent Publication No. 2002-342403 (paragraph nos. [0019]-[0032]; FIGS. 1-3)). The second method is to obtain the shortest possible delay time while decreasing the value of delay time by degrees from a certain upper limit value (see, e.g., S. Devadas, K. Keutzer, and S. Malik, Computation of floating mode delay in combinational circuits: Theory and algorithms, IEEE Transactions on Computer-Aided Design of Integrated Circuits, 12(12): 1913-1923, December 1993). In this method, the shortest possible delay time is obtained while ignoring a delay time attributable to a false path. The third method is a method (called dynamic timing analysis) in which delay times of input vectors (several input signals) are calculated by simulation (see, e.g., D. Brand and V. S. Iyengar, Timing analysis using functional analysis, IEEE Transactions on Computer, 37(10): 1309-1314, October 1988). There has also been proposed a method based on the third method and improved in efficiency (see, e.g., Unexamined Japanese Patent Publication No. 2001-67383 (paragraph nos. [0053]-[0069]; FIG. 1)). As seen from these publications, circuit design using CAD requires false path analysis.

However, in cases where the conventional false path analysis techniques are applied to large-scale, complex circuit design, considerable time is required for the analysis. In the first method in which the analysis is performed path by path, in extreme cases the number of paths exponentially increases with scale of circuit, requiring much time for the false path analysis. In the second method in which the value of delay time is decreased by degrees from a certain upper limit value, the number of times the false path analysis needs to be performed increases if the set range in which the delay time is decreased is narrow. In the third method in which input vectors are simulated, for n inputs, the false path analysis needs to be performed 2 n times, requiring impractically long computation time.

In the timing analysis, only false paths with critical timing or timing error may be detected to reduce the processing time needed for the false path analysis. In recent years, however, circuits with higher performance are demanded, and when such circuits are designed, there exist innumerable false paths with critical timing or timing error, making the detection of such false paths impractical.

Also, since innumerable false paths need to be automatically detected, a problem arises in that tools utilizing the false path information require increased processing time.

The present invention was created in view of the above circumstances, and an object thereof is to provide a false path detection program which directly detects passing points of signal lines constituting false paths, thereby shortening the processing time necessary for the false path detection and also permitting compact description of false path information.

To achieve the object, there is provided a false path detection program for detecting false paths of a designed circuit. The false path detection program causes a computer to function as storing means for receiving circuit information about the circuit and storing the circuit information in a storage device, signal value generating means for generating an impossible signal value with respect to a signal line in the circuit, signal propagation inspecting means for assigning the generated signal value to an input of a gate connected to the signal line and examining whether signal is propagated through the other input of the gate only when accompanied by the signal value, passing point acquiring means for acquiring a passing point of the other signal line connected to the other input of the gate if signal is propagated, and false path specifying means for specifying a false path by the passing point.

The above and other objects, features and advantages of the present invention will become apparent from the following description when taken in conjunction with the accompanying drawings which illustrate preferred embodiments of the present invention by way of example.

FIG. 1 is a diagram illustrating the principles of the present invention;

FIG. 2 is a block diagram showing a hardware configuration of a computer according to a first embodiment;

FIG. 3 is a functional block diagram of the computer according to the first embodiment;

FIG. 4 is a diagram showing an example of circuit which is subjected to false path detection;

FIG. 5 is a diagram showing an exemplary data structure created by a constant signal line detection process;

FIG. 6 is a diagram showing an exemplary data structure created by a paired signal line detection process;

FIG. 7 is a diagram showing an exemplary data structure created by an implication signal line detection process;

FIG. 8 is a diagram showing an exemplary data structure created by a set implication signal line detection process;

FIG. 9 is part of a flowchart showing a flow of process illustrated in the functional block diagram of FIG. 3 ;

FIG. 10 is the remaining part of the flowchart showing the flow of process illustrated in the functional block diagram of FIG. 3 ; and

FIG. 11 is a functional block diagram of a computer according to a second embodiment.

The principles of the present invention will be hereinafter described in detail with reference to the drawings.

FIG. 1 illustrates the principles of the present invention.

As shown in FIG. 1 , a computer 1 includes storing means 1 a , signal value generating means 1 b , signal propagation inspecting means 1 c , passing point acquiring means 1 d , false path specifying means 1 e , and a storage device 1 f.

The storing means 1 a receives circuit information about a circuit designed by a designer, and stores the circuit information in the storage device 1 f . The signal value generating means 1 b generates an impossible signal value with respect to a signal line in the designed circuit. The signal propagation inspecting means 1 c assigns the signal value generated by the signal value generating means 1 b to an input of a gate connected to the signal line with respect to which the signal value has been generated, and then examines whether signal is propagated through the other input of the gate only when accompanied by the signal value. If signal is propagated through the other input of the gate when accompanied by the generated signal value, the passing point acquiring means 1 d acquires a passing point of the other signal line connected to the other input of the gate. The false path specifying means 1 e specifies a false path by the passing point acquired by the passing point acquiring means 1 d.

Thus, instead of detecting each path, the passing point of signal lines constituting a false path is directly detected, whereby the processing time necessary for the false path detection can be shortened. Also, the detected false path is specified by the passing point, thus permitting compact description of the false path.

A first embodiment of the present invention will be now described in detail with reference to the drawings. First, the hardware configuration of a computer for executing a false path detection program according to the present invention will be described.

FIG. 2 is a block diagram showing the hardware configuration of a computer according to the first embodiment.

The computer 10 is in its entirety under the control of a CPU (Central Processing Unit) 10 a . To the CPU 10 a are connected, via a bus 10 g , a RAM (Random Access Memory) 10 b , a hard disk drive (HDD) 10 c , a graphics processor 10 d , an input interface 10 e , and a communication interface 10 f.

The RAM 10 b temporarily stores at least part of OS (Operating System) programs and application programs executed by the CPU 10 a , the application programs including a CAD program and a false path detection program. Also, the RAM 10 b stores various other data necessary for the processing by the CPU 10 a . The HDD 10 c stores the OS and application programs as well as various data.

The graphics processor 10 d is connected with a monitor 10 h . In accordance with instructions from the CPU 10 a , the graphics processor 10 d causes the monitor 10 h to display image on a display screen thereof. The input interface 10 e is connected with a keyboard 10 i and a mouse 10 j , and supplies signals from the keyboard 10 i and the mouse 10 j to the CPU 10 a via the bus 10 g . The communication interface 10 f permits the computer 10 to communicate with other computers, not shown, connected via a network.

The false path detection program is executed by the computer having the hardware configuration described above.

The following describes functions accomplished by the computer 10 when the false path detection program is executed.

FIG. 3 is a functional block diagram of the computer according to the first embodiment.

The computer 10 has functional blocks shown in FIG. 3 , which are performed when the false path detection program is executed. Specifically, the computer 10 includes a circuit input section 11 , a constant signal line detection section 12 , a paired signal line detection section 13 , an implication relation detection section 14 , a set implication relation detection section 15 , a combination generation section 16 , a passing point acquisition section 17 , and a false path output section 18 .

The circuit input section 11 receives circuit information from the designer. The circuit information is information about a circuit designed by the designer and includes, for example, signal lines, circuit elements, identifiers assigned to the input/output terminals of the circuit elements, and relationships of signal line-circuit element connections. The circuit input section 11 stores the received circuit information in, for example, the RAM 10 b or the HDD 10 c shown in FIG. 2 .

Based on the circuit information received from the designer, the constant signal line detection section 12 detects a signal line (constant signal line) to which is input a constant signal (signal which remains only in a constant state). The constant signal is specified by the designer in the case where the designer wishes to perform timing analysis in a certain mode of the circuit, for example.

The paired signal line detection section 13 detects a pair of signal lines (equivalent signal lines) whose signal values are always equal to each other within the circuit, or a pair of signal lines (exclusive signal lines) whose signal values are always different from each other. For example, fan-out signal lines are equivalent signal lines. Also, where an inverter is inserted in a signal line, the input and output sides of the signal line with respect to the inverter are exclusive signal lines.

The implication relation detection section 14 detects signal lines which are in an implication relation. For example, where signal lines satisfy an implication relation such that if the value of one signal line s is a, then the value of the other signal line t is always b (s=a→t=b), such signal lines are detected.

The set implication relation detection section 15 detects a signal line which is in an implication relation with a signal line set having size k (k is a natural number equal to or greater than “2”). For example, where there exists a set implication relation such that if the values of a set of signal lines (s 1 , s 2 , . . . , sk) are (a 1 , a 2 , . . . , ak), then the value of a different signal line t is always b ((s 1 , s 2 , . . . , sk)=(a 1 , a 2 , . . . , ak)→t=b), the signal line t is detected.

The constant signal line detection section 12 , the paired signal line detection section 13 , the implication relation detection section 14 and the set implication relation detection section 15 operate in accordance with instructions input by the designer. It is therefore possible to operate only the constant signal line detection section 12 and the paired signal line detection section 13 , for example.

The combination generation section 16 generates impossible combinations of signal values with respect to the signal lines detected by the constant signal line detection section 12 , paired signal line detection section 13 , implication relation detection section 14 and set implication relation detection section 15 . Then, the combination generation section 16 outputs the generated signal line value to the detected signal line to apply the generated value to a gate connected to the signal line.

If, with the impossible signal line value input to the signal line connected to the gate, signal is propagated through the other signal line of the gate only when accompanied by the impossible signal line value, the passing point acquisition section 17 acquires a passing point of the other signal line. The passing point of the acquired signal line is represented, for example, by an identifier assigned to the signal line or by the terminal of the gate. The passing point acquisition section 17 then determines whether a path (signal line) passing through the acquired passing point (or connecting between the passing points if the number of acquired passing points is “2” or more) exists or not. The number of passing points to be acquired may be input by the designer so that the passing point acquisition section 17 may acquire passing points not exceeding the specified number.

The expression “signal is propagated” means that the signal is not blocked by the gate. For example, “signal is propagated” if the output of an AND gate, with “1” input to one terminal thereof, varies depending on the input to the other terminal. Signal is “blocked” in a situation where, for example, “0” is input to one terminal of an AND gate and thus the AND gate always outputs a constant value “0” regardless of the input to the other terminal.

If it is judged by the passing point acquisition section 17 that a path exists, the false path output section 18 outputs the passing point as a false path (passing point of false path). The output false path is stored in the RAM 10 b or the HDD 10 c shown in FIG. 2 or is displayed on the monitor 10 h , for example. Also, the output path is directly used in the timing analysis. The false path output section 18 is capable of outputting as many false paths as specified by the designer's input operation. In this case, the false path output section 18 outputs false paths in ascending order of the number of passing points.

For a constant signal line detected by the constant signal line detection section 12 , the combination generation section 16 generates an impossible value of the constant signal line, that is, a NOT signal which is negation of the constant signal. The combination generation section 16 then inputs the generated impossible value to a gate connected to the constant signal line. If signal is propagated through the other signal line of the gate only when accompanied by the impossible signal line value, the passing point acquisition section 17 acquires a passing point of the other signal line. Then, the passing point acquisition section 17 determines whether a path passing through the acquired passing point exists or not. If it is judged by the passing point acquisition section 17 that a path passing through the passing point exists, the false path output section 18 outputs the passing point as a false path.

Also, for equivalent signal lines or exclusive signal lines detected by the paired signal line detection section 13 , the combination generation section 16 generates an impossible combination of signal values of such signal lines. The combination generation section 16 then assigns the generated impossible signal line values to respective inputs of gates connected to the equivalent or exclusive signal lines. If signal is propagated through the other signal lines of the gates which are input with the impossible signal line values, the passing point acquisition section 17 acquires passing points of the other signal lines. Then, the passing point acquisition section 17 determines whether a path connecting between the acquired passing points exists or not. If it is judged by the passing point acquisition section 17 that a path connecting between the passing points exists, the false path output section 18 outputs the passing points as a false path.

For implication-related signal lines detected by the implication relation detection section 14 , the combination generation section 16 generates an impossible combination of signal values of such signal lines. The combination generation section 16 then outputs the generated impossible signal line values to gates connected to the implication-related signal lines. If signal is propagated through the other signal lines of the gates only when accompanied by the generated impossible signal line values, the passing point acquisition section 17 acquires passing points of the other signal lines. Then, the passing point acquisition section 17 determines whether a path connecting between the acquired passing points exists or not. If it is judged by the passing point acquisition section 17 that a path connecting between the passing points exists, the false path output section 18 outputs the passing points as a false path.

Also, for implication-related signal lines detected by the set implication relation detection section 15 , the combination generation section 16 generates an impossible combination of signal values of such signal lines. The combination generation section 16 then outputs the generated impossible signal line values to gates connected to the implication-related signal lines. If signal is propagated through the other signal lines of the gates which are input with the generated impossible signal line values, the passing point acquisition section 17 acquires passing points of the other signal lines. Then, the passing point acquisition section 17 determines whether a path connecting between the acquired passing points exists or not. If it is judged by the passing point acquisition section 17 that a path connecting between the passing points exists, the false path output section 18 outputs the passing points as a false path.

An exemplary circuit of which the false paths are detected will be now described.

FIG. 4 shows an example of circuit which is subjected to the false path detection.

An inverter Z 1 has a signal input terminal t 1 and a signal output terminal t 2 . The terminal t 1 is connected with a signal line L 14 and is input with a signal s 2 . The inverter Z 1 inverts the signal input to the terminal t 1 and outputs the inverted signal from the terminal t 2 .

An AND gate Z 2 has signal input terminals t 3 and t 4 and a signal output terminal t 5 . The terminal t 3 is connected to the terminal t 2 of the inverter Z 1 by a signal line L 2 . The AND gate Z 2 computes a logical product of the signals input to the terminals t 3 and t 4 , and outputs the result from the terminal t 5 .

A signal line L 3 is input with a signal s 3 and connected to signal lines L 4 and L 5 . The signal line L 4 is connected to the terminal t 4 of the AND gate Z 2 .

An OR gate Z 3 has signal input terminals t 6 and t 7 and a signal output terminal t 8 . The terminal t 6 is connected with the signal line L 1 and thus is input with the signal s 1 . The terminal t 7 is connected to the terminal t 5 of the AND gate Z 2 by a signal line L 6 . The terminal t 8 is connected with a signal line L 7 which is connected to signal lines L 8 and L 9 . The OR gate Z 3 computes a logical sum of the signals input to the terminals t 6 and t 7 , and outputs the result to the terminal t 8 . The signal appearing at the terminal t 8 is output to the signal line L 8 as a signal o 1 .

An OR gate Z 4 has signal input terminals t 9 and t 10 and a signal output terminal t 11 . The terminal t 9 is connected with the signal line L 9 which is connected to the signal lines L 7 and L 8 . The terminal t 10 is connected with the signal line L 5 which is connected to the signal lines L 3 and L 4 . The terminal t 11 is connected to a signal line L 10 . The OR gate Z 4 computes a logical sum of the signals input to the terminals t 9 and t 10 , and outputs the result from the terminal t 11 .

A multiplexer Z 5 has signal input terminals t 12 to t 14 and a signal output terminal t 15 . The terminal t 12 is connected with the signal line L 10 . The terminal t 13 is connected with a signal line L 11 to which a signal s 4 is input, and the terminal t 14 is connected with a signal line L 12 to which a signal s 5 is input. The terminal t 15 is connected to a signal line L 13 . The multiplexer Z 5 outputs one of the signals input to the terminals t 12 and t 13 , selected in accordance with the signal s 5 input to the terminal t 14 , to the terminal t 15 . Specifically, when the signal S 5 is “1,” the multiplexer Z 5 outputs the signal input to the terminal t 13 to the terminal t 15 , and when the signal s 5 is “0,” the multiplexer Z 5 outputs the signal input to the terminal t 12 to the terminal t 15 . The signal appearing at the terminal t 15 is output to the signal line L 13 as a signal o 2 .

The designer inputs circuit information about the circuit designed as shown in FIG. 4 , for example, signals input to the circuit, types of elements constituting the circuit, input/output terminals of the elements and signal lines connecting the elements, to the computer 10 . Based on the input circuit information, the computer 10 detects false paths of the circuit shown in FIG. 4 .

Examples of data structures created when the computer 10 executes respective processes will be now described.

FIG. 5 illustrates an exemplary data structure created by a constant signal line detection process.

As shown in FIG. 5 , constant signal line data 21 has columns named “CONSTANT SIGNAL LINE,” “CONSTANT SIGNAL” and “PASSING POINT OF NODE THROUGH WHICH SIGNAL IS PROPAGATED ONLY WHEN ACCOMPANIED BY IMPOSSIBLE SIGNAL LINE VALUE.” The constant signal line data 21 is created in the storage device such as the RAM 10 b or the HDD 10 c shown in FIG. 2 .

Under the column “CONSTANT SIGNAL LINE” is stored the identifier of a signal line (e.g., name or number assigned to the signal line) whose signal line value is constant in the circuit which is subjected to the false path detection. Under the column “CONSTANT SIGNAL” is stored the signal value of the constant signal line. Under the column “PASSING POINT OF NODE THROUGH WHICH . . . ” is stored the passing point of a node through which signal is propagated.

The constant signal line and the constant signal are input by the designer and are stored under the columns “CONSTANT SIGNAL LINE” and “CONSTANT SIGNAL,” respectively, by the circuit input section 11 . The passing point of a node through which signal is propagated is calculated by the constant signal line detection section 12 , the combination generation section 16 and the passing point acquisition section 17 , and is stored under the column “PASSING POINT OF NODE THROUGH WHICH . . . .”

It is assumed, for example, that in the circuit of FIG. 4 , the signal line L 12 is a constant signal line and that the constant signal thereof is “0.” In this case, the constant signal line detection section 12 detects the signal line L 12 as a constant signal line, and the combination generation section 16 generates an impossible value of the signal line L 12 , that is, a NOT signal “1” which is negation of the constant signal “0.” Then, the combination generation section 16 inputs the generated NOT signal “1” to the multiplexer Z 5 connected to the signal line L 12 . The passing point acquisition section 17 detects, as the passing point of a node through which signal is propagated, the terminal t 13 of the multiplexer Z 5 through which signal is propagated when the NOT signal is input, and stores the detected terminal under the column “PASSING POINT OF NODE THROUGH WHICH . . . ” of the constant signal line data 21 .

It is not necessary that all of the constant signal line data 21 be stored in the storage device. After one row is processed and a false path corresponding thereto is output, the content of the row may be deleted, whereby the storage area can be saved.

FIG. 6 illustrates an exemplary data structure created by a paired signal line detection process.

As shown in FIG. 6 , paired signal line data 22 has a column named “PAIRED SIGNAL LINES” which is subdivided into “NODE 1,” “NODE 2” and “PHASE DIFFERENCE,” a column named “PASSING POINTS OF NODE PAIR THROUGH WHICH SIGNAL IS PROPAGATED ONLY WHEN ACCOMPANIED BY IMPOSSIBLE SIGNAL LINE VALUE,” and a column named “EXISTENCE OF PATH PASSING THROUGH NODE PAIR THROUGH WHICH SIGNAL IS PROPAGATED ONLY WHEN ACCOMPANIED BY IMPOSSIBLE SIGNAL LINE VALUE.” The paired signal line data 22 is created in the storage device such as the RAM 10 b or the HDD 10 c shown in FIG. 2 .

Under “NODE 1” and “NODE 2” of the column “PAIRED SIGNAL LINES” are stored the identifiers of signal lines (equivalent signal lines) whose signal values are equal to each other, as well as the identifiers of signal lines (exclusive signal lines) whose signal values are different from each other. Under “PHASE DIFFERENCE” is stored a phase difference between the signals propagated through the signal lines, wherein “0” indicates a phase difference of “0” and “1” indicates a phase difference of π. Under the column “PASSING POINTS OF NODE PAIR THROUGH WHICH . . . ” are stored passing points of nodes through which signal is propagated. Under the column “EXISTENCE OF PATH PASSING THROUGH NODE PAIR THROUGH WHICH . . . ” is stored information which indicates, by “0” or “1,” whether or not a path exists between the passing points of the node pair through which signal is propagated. “0” indicates that no path exists, and “1” indicates that a path exists.

In the example of FIG. 4 , the paired signal line detection section 13 detects the signal lines L 4 and L 5 , the signals lines L 8 and L 9 and the signal lines L 8 and L 13 , each pair as equivalent signal lines, and also detects the signal lines L 2 and L 14 as exclusive signal lines. The detected signal lines are stored, along with the phase difference between the signal values, under the column “PAIRED SIGNAL LINES” of the paired signal line data 22 . The combination generation section 16 generates an impossible combination of signal line values with respect to each pair of equivalent signal lines and exclusive signal lines. For the signal lines L 4 and L 5 , for example, “1” and “0” are generated, respectively. If, with the generated signal line values input to the respective gates, signal is propagated through the other signal lines of the gates, the passing point acquisition section 17 acquires passing points of the other signal lines. For example, the value of the signal line L 4 is “1,” and accordingly, signal on the signal line L 2 is propagated. Also, the value of the signal line L 5 is “0,” and therefore, signal on the signal line L 9 is propagated. Consequently, the terminals t 3 and t 9 are acquired as the passing points of the node pair through which signal is propagated. If there exists a path passing through the passing points of the signal propagating node pair, the passing point acquisition section 17 stores “1” under the column “EXISTENCE OF PATH PASSING THROUGH NODE PAIR THROUGH WHICH . . . .”

It is not necessary that all of the paired signal line data 22 be stored in the storage device. After one row is processed and a false path corresponding thereto is output, the content of the row may be deleted, whereby the storage area can be saved.

FIG. 7 illustrates an exemplary data structure created by an implication signal line detection process.

As shown in FIG. 7 , implication signal line data 23 has a column named “ANTECEDENT OF IMPLICATION” which is subdivided into “NODE” and “VALUE,” a column named “CONSEQUENT OF IMPLICATION” which is subdivided into “NODE” and “VALUE,” a column named “PASSING POINT OF NODE PAIR THROUGH WHICH SIGNAL IS PROPAGATED ONLY WHEN ACCOMPANIED BY IMPOSSIBLE SIGNAL LINE VALUE,” and a column named “EXISTENCE OF PATH PASSING THROUGH NODE PAIR THROUGH WHICH SIGNAL IS PROPAGATED ONLY WHEN ACCOMPANIED BY IMPOSSIBLE SIGNAL LINE VALUE.” The implication signal line data 23 is created in the storage device such as the RAM 10 b or the HDD 10 c shown in FIG. 2 .

Under “NODE” of the column “ANTECEDENT OF IMPLICATION” is stored the identifier of a signal line as an antecedent of implication, and under “VALUE” of the column “ANTECEDENT OF IMPLICATION” is stored the signal value of the signal line as the antecedent of implication. Under “NODE” of the column “CONSEQUENT OF IMPLICATION” is stored the identifier of a signal line as a consequent of implication, and under “VALUE” of the column “CONSEQUENT OF IMPLICATION” is stored the signal value that the signal line as the consequent of implication assumes under the condition of the implication antecedent. Under the column “PASSING POINT OF NODE PAIR THROUGH WHICH . . . ” is stored the passing point of a node through which signal is propagated. Under the column “EXISTENCE OF PATH PASSING THROUGH NODE PAIR THROUGH WHICH . . . ” is stored information which indicates, by “0” or “1,” whether or not a path exists between the passing points of the node pair through which signal is propagated. “0” indicates that no path exists, and “1” indicates that a path exists.

For example, in the circuit of FIG. 4 , the implication relation detection section 14 detects the implication relation that if the value of the signal line L 2 is “0,” then the value of the signal line L 6 is “0,” the detected relation being stored under the columns “ANTECEDENT OF IMPLICATION” and “CONSEQUENT OF IMPLICATION” of the implication signal line data 23 . The combination generation section 16 generates an impossible combination of signal line values “0” and “1” with respect to the signal lines L 2 and L 6 , respectively. The passing point acquisition section 17 acquires the terminal t 6 through which signal is propagated when accompanied by the generated impossible signal values, and stores the identifier of the terminal under the column “PASSING POINT OF NODE PAIR THROUGH WHICH . . . .” Since there is no path between the terminals t 4 and t 6 , the passing point acquisition section 17 judges that a path connecting the node pair through which signal is propagated does not exist and thus stores “0” under the column “EXISTENCE OF PATH PASSING THROUGH NODE PAIR THROUGH WHICH . . . ” of the implication signal line data 23 .

It is not necessary that all of the implication signal line data 23 be stored in the storage device. After one row is processed and a false path corresponding thereto is output, the content of the row may be deleted, whereby the storage area can be saved.

FIG. 8 illustrates an exemplary data structure created by a set implication signal line detection process.

As shown in FIG. 8 , set implication signal line data 24 has a column named “ANTECEDENT OF IMPLICATION,” a column named “CONSEQUENT OF IMPLICATION” which is subdivided into “NODE” and “VALUE,” a column named “NODE SET THROUGH WHICH SIGNAL IS PROPAGATED ONLY WHEN ACCOMPANIED BY IMPOSSIBLE SIGNAL LINE VALUE,” and a column named “EXISTENCE OF PATH PASSING THROUGH NODE SET THROUGH WHICH SIGNAL IS PROPAGATED ONLY WHEN ACCOMPANIED BY IMPOSSIBLE SIGNAL LINE VALUE.” The set implication signal line data 24 is created in the storage device such as the RAM 10 b or the HDD 10 c shown in FIG. 2 .

Under the column “ANTECEDENT OF IMPLICATION” are stored the identifiers of signal lines as an antecedent of set implication. Under “NODE” of the column “CONSEQUENT OF IMPLICATION” is stored the identifier of a signal line as a consequent of implication, and under “VALUE” of the column “CONSEQUENT OF IMPLICATION” is stored the signal value that the signal line as the consequent of implication assumes under the condition of the implication antecedent. Under the column “NODE SET THROUGH WHICH . . . ” is stored the passing points of nodes through which signal is propagated. Under the column “EXISTENCE OF PATH PASSING THROUGH NODE SET THROUGH WHICH . . . ” is stored information which indicates, by “0” or “1,” whether or not a path exists between the passing points through which signal is propagated. “0” indicates that no path exists, and “1” indicates that a path exists.

In the example of FIG. 4 , the set implication relation detection section 15 detects an implication relation that holds between a signal line set with size k and a certain signal line, the detected implication relation being stored under the columns “ANTECEDENT OF IMPLICATION” and “CONSEQUENT OF IMPLICATION” of the set implication signal line data 24 . The combination generation section 16 generates an impossible combination of signal line values with respect to the detected implication relation. If, with the generated signal line values input to gates, signal is propagated through the other signal lines of the gates, the passing point acquisition section 17 acquires passing points of the other signal lines and stores the identifiers of the acquired passing points under the column “NODE SET THROUGH WHICH . . . ” of the set implication signal line data 24 . Then, if there is a path between the passing points of the node set through which signal is propagated, the passing point acquisition section 17 stores “1” under the column “EXISTENCE OF PATH PASSING THROUGH NODE SET THROUGH WHICH . . . ” of the set implication signal line data 24 .

It is not necessary that all of the set implication signal line data 24 be stored in the storage device. After one row is processed and a false path corresponding thereto is output, the content of the row may be deleted, whereby the storage area can be saved.

In the following, operations of the sections shown in the functional block diagram of FIG. 3 will be described.

A flowchart of FIGS. 9 and 10 illustrates a flow of process shown in the functional block diagram of FIG. 3 .

First, the flowchart will be outlined. It is assumed that the exemplary circuit shown in FIG. 4 is a target of false path detection. In Step S 1 , circuit information on the circuit as a target of false path detection and a maximum value kmax of k in k-to-1 implication relation, used in Step S 12 , are input. Input of kmax may be omitted.

In Steps S 2 to S 4 , false path detection is performed with respect to combinations of signal line values having the smallest number of elements, that is, 1, among impossible combinations of signal line values. Namely, false paths are detected with respect to constant signal lines. With the impossible signal line value applied to a gate connected to the signal line, a false path is specified and output by means of the passing point of the other signal line connected to the gate.

In Steps S 5 to S 10 , false path detection is performed with respect to combinations of signal line values having the second smallest number of elements, that is, 2, among impossible combinations of signal line values. Namely, false paths are detected with respect to pairs of signal lines. Such pairs of signal lines fall under three types of relation, that is, equivalence relation, exclusion relation which is negation of equivalence relation, and implication relation. For the equivalence and exclusion relations, false path detection is performed in Steps S 5 to S 7 , and for the implication relation, false path detection is performed in Steps S 8 to S 10 .

In Steps S 11 to S 16 , false path detection is performed with respect to combinations of signal line values having three or more elements among impossible combinations of signal line values. Namely, false path detection is performed with respect to set implication relations. In this case, with the number of elements increased one by one, false path detection is performed with respect to k (k≧2)-to-1 implication relations.

The flowchart will be now described in detail. The process shown in the functional block diagram of FIG. 3 is carried out by executing the following steps.

In Step S 1 , the circuit input section 11 accepts the circuit information and kmax input by the designer. It is assumed that in the input circuit information, the signal s 5 input to the signal line L 12 shown in FIG. 4 is previously fixed at the constant “0.”

In Step S 2 , the constant signal line detection section 12 determines whether or not there exists an undetected constant signal line in the circuit of FIG. 4 . If there is an undetected constant signal line, the flow proceeds to Step S 3 ; if there is no undetected constant signal line, the flow proceeds to Step S 5 .

In Step S 3 , the combination generation section 16 generates an impossible signal value of the constant signal line detected by the constant signal line detection section 12 , and outputs the generated signal value to a gate connected to the constant signal line. If, with the generated signal value output to the gate, signal is propagated through the other signal line of the gate, the passing point acquisition section 17 acquires a passing point of the other signal line. Then, the passing point acquisition section 17 determines whether a path passing through the passing point exists or not.

For example, the circuit information input in Step S 1 indicates that the signal line L 12 in FIG. 4 is a constant signal line with the constant “0.” Accordingly, the constant signal line detection section 12 detects the signal line L 12 as a constant signal line. The combination generation section 16 generates “1,” which is negation of the constant “0,” as an impossible signal line value of the signal line L 12 , and outputs the generated value to the terminal t 14 of the multiplexer Z 5 . At this time, signal on a different signal line L 11 connected to the multiplexer Z 5 is propagated. Accordingly, the passing point acquisition section 17 acquires, as a passing point, the terminal t 13 connected with the signal line L 11 . The path passing through the terminal t 13 is a logical false path. In the case where conventional false path detection is additionally performed taking account of delay, the delay relationship between the terminals t 13 and t 14 is examined to determine whether the path is really a false path or not.

If it is judged by the passing point acquisition section 17 that a path passing through the passing point exists, the false path output section 18 outputs the passing point as a set of false paths, in Step S 4 . In the above example, the false path set is expressed as {t 13 } by using the terminal t 13 which is the passing point of the signal line L 11 . The number of false path-specifying passing points output in Step S 4 invariably takes a minimum value of “1.” The constant signal line detection section 12 detects, in addition to the constant signal lines specified as explained above, constant signal lines which are identified with a specified constant value propagated, and constant signal lines which always assume the constant “0” because of the operation of the circuit.

In Step S 5 , the paired signal line detection section 13 detects a pair of equivalent/exclusive signal lines. If such a pair is detected, the flow proceeds to Step S 6 ; if no such pair is detected, the flow proceeds to Step S 8 .

In Step S 6 , the combination generation section 16 generates an impossible combination of signal line values with respect to the detected pair of equivalent/exclusive signal lines. Then, the combination generation section 16 outputs the generated impossible combination of signal line values to gates connected to the equivalent/exclusive signal line pair. If, with the impossible signal line values output to the gates, signal is propagated through the other signal lines of the gates, the passing point acquisition section 17 acquires passing points of the other signal lines. Then, the passing point acquisition section 17 determines whether or not a path exists between the acquired passing points.

In the circuit of FIG. 4 , for example, the signal lines L 4 and L 5 , which are fan-outs of the signal line L 3 , constitute an equivalent signal line pair. Where a constant value is propagated through the signal line L 3 , the impossible combination of signal line values for this equivalence relation is the combination: signal on the signal line L 4 ≠signal on the signal line L 5 . A gate which is connected to the signal line L 4 as an input thereof is the AND gate Z 2 , and a gate which is connected to the signal line L 5 as an input thereof is the OR gate Z 4 . The non-controlling value of the AND gate Z 2 is “0” and the non-controlling value of the OR gate Z 4 is “1.” Thus, “1” and “0” are set, respectively, as impossible signal values of the signal lines L 4 and L 5 through which signal is input to the terminals t 4 and t 10 of the AND gate Z 2 and the OR gate Z 4 , respectively, and the other terminal t 3 than the terminal t 4 of the AND gate Z 2 and the other terminal t 9 than the terminal t 10 of the OR gate. Z 4 are acquired as passing points. A path, if exists between the terminals t 3 and t 9 , is a logical false path. Examining whether a path exists between the output terminal t 2 of the inverter Z 1 and the input terminal t 9 of the OR gate Z 4 reveals that there exists a path constituted by the signal lines L 2 , L 6 , L 7 and L 9 .

If it is judged by the passing point acquisition section 17 that a path connecting between the passing points exists, the false path output section 18 outputs the passing points as a set of false paths, in Step S 7 . In the above example, the false path set is expressed as {t 3 , t 9 } by using the terminals t 3 and t 9 which are the passing points of the signal lines L 2 and L 9 . Thus, the path set passing through the passing points {t 3 , t 9 } is a logical false path. In the case where additional false path analysis is performed taking account of delay, the delay relationship between the terminals t 3 and t 4 and between the terminals t 9 and t 10 is examined to determine whether the path is really a false path or not. The number of false path-specifying passing points output in Step S 7 invariably takes a value of “2.”

In Step S 8 , the implication relation detection section 14 detects signal lines which are in an implication relation. If such signal lines are detected, the flow proceeds to Step S 9 ; if no such signal lines are detected, the flow proceeds to Step S 11 .

In Step S 9 , the combination generation section 16 generates an impossible combination of signal line values with respect to the detected implication-related signal lines. Then, the combination generation section 16 outputs the generated impossible signal line values to gates connected to the implication-related signal lines. If signal is propagated through the other signal lines connected to the gates, the passing point acquisition section 17 acquires passing points of the other signal lines. Then, the passing point acquisition section 17 determines whether a path connecting between the acquired passing points exists or not.

In the circuit of FIG. 4 , for example, there is an implication relation that if the signal line L 2 =0, then the signal line L 6 =0. In this implication relation, an impossible combination of the signal line values is (L 2 , L 6 )=(0, 1), and the passing point of a signal line through which signal is propagated is the terminal t 6 . No path exists between the input terminal t 4 of the AND gate Z 2 , which is a passing point of the signal line paired with the signal line L 2 , and the input terminal t 6 of the OR gate Z 3 , which is a passing point of the signal line paired with the signal line L 6 .

If it is judged by the passing point acquisition section 17 that a path connecting between the passing points exists, the false path output section 18 outputs the passing points as a set of false paths, in Step S 10 . In the above example, since there is no path between the passing points, no false path set is output.

In Step S 11 , the set implication relation detection section 15 substitutes “2” for the variable k. The value substituted for the variable k can be changed by the user.

In Step S 12 , the set implication relation detection section 15 determines whether either of the following two conditions is fulfilled or not, that is, the condition that the variable k is smaller than or equal to kmax and the condition that the variable k is smaller than or equal to a maximum number of gate stages. If the variable k is smaller than or equal to kmax or the maximum number of gate stages, the flow proceeds to Step S 13 ; if the variable k is greater than kmax and the maximum number of gate stages, the process is ended.

In Step S 13 , the set implication relation detection section 15 determines whether or not there exist undetected signal lines which are in k-to-1 implication relation. If there is no undetected implication relation, the flow proceeds to Step S 14 ; if there exists an undetected implication relation, the flow proceeds to Step S 15 . Where k=2, for example, the relation in the circuit of FIG. 4 that if L 1 =1 and L 12 =0, then L 13 =1 is detected as k-to-1 implication relation. Then, in Steps S 15 and S 16 similar to Steps S 9 and S 10 explained above, a false path associated with the implication relation is detected and output.

In Step S 14 , the set implication relation detection section 15 adds “1” to the variable k.

In Step S 15 , the combination generation section 16 generates an impossible combination of signal line values with respect to the detected implication-related signal lines. Then, the combination generation section 16 assigns the generated impossible signal line values to inputs of gates connected to the implication-related signal lines. If signal is propagated through the other signal lines connected to the gates only when the generated values are input, passing points of the other signal lines are acquired. The passing point acquisition section 17 then determines whether a path connecting between the acquired passing points exists or not.

If it is judged by the passing point acquisition section 17 that a path connecting between the passing points exists, the false path output section 18 outputs the passing points as a set of false paths, in Step S 16 .

In the flowchart shown in FIGS. 9 and 10 , only Steps S 2 to S 4 , only Steps S 5 to S 7 , only Steps SB to S 10 , or only Steps S 11 to S 16 can be executed, though not illustrated as such. Also, Steps S 2 to S 4 , Steps S 5 to S 7 , Steps S 8 to S 10 , and Steps S 11 to S 16 can be selectively executed in accordance with instructions from the designer. Further, it is possible to output as many false paths as specified by the designer's input operation.

Thus, impossible combinations of signal line values in the circuit are generated by the constant signal line detection section 12 , the paired signal line detection section 13 , the implication relation detection section 14 and the set implication relation detection section 15 . Since a plurality of paths can be simultaneously detected without regard to delay values, it is possible to prevent explosion of computation time from being caused due to the counting of paths or delay values.

Also, false paths are specified by the passing points of signal lines, and this makes it possible to describe false paths compactly.

In the case where false path analysis is performed while counting up input vectors, it is necessary that the analysis be performed on each of 2 n (n: natural number) input vectors. If the analysis is performed with respect to a smaller number of input vectors only, circuit delay is underestimated because the analysis performed does not cover the circuit operation in full. According to the present invention, by increasing/decreasing the number of impossible combinations of signal values or the number of elements in such combinations, it is possible to flexibly vary the detection capability without entailing underestimation of circuit delay.

Also, the constant signal line detection section 12 , the paired signal line detection section 13 , the implication relation detection section 14 and the set implication relation detection section 15 are activated in this order so that impossible combinations of signal line values in the circuit may be generated in ascending order of the number of elements in such combinations. Accordingly, false paths can be detected and output in ascending order of the number of false path-specifying passing points. The number of passing points can exert an exponential influence on the processing speed of a timing optimization system or timing analysis system that utilizes false paths. According to the invention, false paths can be generated in a manner convenient for such systems utilizing false paths. Further, by externally specifying the number of false paths to be generated, it is possible to generate most convenient sets of false paths not exceeding the specified number.

A second embodiment of the present invention will be now described in detail with reference to the drawings. A computer according to the second embodiment can also be used for compressing the description amount of false paths specified by passing points. The computer accepts false paths described by passing points, and performs a process similar to that shown in the flowchart of FIGS. 9 and 10 , with respect only to the signal lines associated with the passing points. Then, the computer outputs a false path description which is smaller in description amount than the input false path description.

FIG. 11 is a functional block diagram of the computer according to the second embodiment.

As shown in FIG. 11 , the computer 30 has a false path set input section 31 , a false path signal line value generation section 32 , a false path generation section 33 , and a false path specification section 34 .

The false path set input section 31 accepts, from the designer, a false path description specified by passing points.

Only with respect to signal lines which the false paths specified by passing points pass through, the false path signal line value generation section 32 generates impossible combinations of signal line values in ascending order of the number of elements in such combinations.

The false path generation section 33 generates false paths corresponding to the impossible combinations of signal line values.

The false path specification section 34 outputs the false paths which are each specified by the number of passing points equal to the number of elements in the combination of signal line values.

In the second embodiment, the computer 30 is input with a false path description specified by passing points, instead of the circuit information. Namely, in Step S 1 of the flowchart shown in FIGS. 9 and 10 , a false path description specified by passing points is input. Then, a process similar to that of the first embodiment is performed with respect to signal lines associated with the input false path. Let it be assumed, for example, that in the circuit of FIG. 4 , a false path is specified by the passing points {t 1 , t 2 , t 3 , t 5 , t 7 , t 8 , t 9 , t 11 , t 12 , t 15 }. The false path is input to the computer 30 , whereupon false path detection is performed only within the signal lines and a false path description {t 3 , t 9 }, which is a compressed description of passing points, is output.

In this manner, signal lines associated with a false path are specified by passing points, and false path detection is performed with respect to the signal lines. Consequently, the input false path description is output in compressed form, making it possible to more specifically locate false paths in the circuit.

According to the false path detection program of the present invention, impossible signal values are generated with respect to signal lines in the designed circuit, and the passing points of signal lines constituting false paths are directly detected, whereby the processing time necessary for the false path detection can be shortened. Also, false paths are specified by passing points, and this makes it possible to describe false paths compactly.

The foregoing is considered as illustrative only of the principles of the present invention. Further, since numerous modifications and changes will readily occur to those skilled in the art, it is not desired to limit the invention to the exact construction and applications shown and described, and accordingly, all suitable modifications and equivalents may be regarded as falling within the scope of the invention in the appended claims and their equivalents.