Clock gating analyzing apparatus, clock gating analyzing method, and computer product

This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2007-032540, filed on Feb. 13, 2007, the entire contents of which are incorporated herein by reference.

1. Field of the Invention

The present invention relates to a technology for analyzing clock gating in large-scale integrated (LSI) semiconductor circuits.

2. Description of the Related Art

Clock gating (function) is a common technique for reducing power consumption of LSI circuits and involves terminating, as close as possible to the source, clock signals for an inactive portion of an LSI circuit to reduce power consumption resulting from the propagation of unnecessary clock signals. Conventionally, since clock gating was manually inserted in large blocks, designers could completely comprehend the operation of the clock gating function. Conventional clock gating verification includes timing verification of clock system signals, i.e., verifying whether the arrival timing of a control signal of individual clock gates falls within a range of normal operation, (see, for example, Japanese Patent Application Laid-Open Publication Nos. 8-202569 and 11-259554), and timing verification of data system signals with consideration of the clock gate function (see, for example, M. Kawarabayashi, et al., “A Verification Technique for Gated Clock”, Proceedings of the Design Automation Conference, pp. 123-127, 1993).

With regard to clock gating verification other than by timing verification, tools have been disclosed to the extent of extracting and depicting a partial circuit related to the clock gating (see, for example, Japanese Patent Application Laid-Open Publication No. 10-283381).

However, demand for further reductions in the power consumption of LSI circuits has increased and clock gating has been inserted in smaller blocks or automatically. The number of inserted clock gates has increased considerably, and overall comprehension of the relationships between individual clock gates has become nearly impossible for designers.

Under such circumstances, verification oversights of the clock gate function itself has become problematic. Specifically, if a clock is not terminated at a point where the clock must be terminated or if a clock is terminated at a point where the clock must not be terminated, this emerges as a function bug and, therefore, poor design due to the verification oversight becomes a problem. If a clock is not terminated at a point where the clock should be terminated, even when no function bug emerges, it is problematic in that electric power is wastefully consumed. Recently, strict limitations are placed on power consumption and a slight increase in consumption often becomes problematic as the target electric power is exceeded.

It is an object of the present invention to at least solve the above problems in the conventional technologies.

A computer-readable recording medium according to one aspect of the present invention stores therein a clock gating analyzing program that causes a computer to execute detecting a plurality of clock gates that supply a clock or terminate the clock to a plurality of sequential circuit elements in a target circuit; calculating, for each of the clock gates, a clock gate function indicating activation of a local clock output from a local clock detected at the detecting; generating a conversion table by a substitution of a plurality of combinations of output values from the sequential circuit elements into each of the clock gate functions to calculate a plurality of combinations of clock gate function values, each combination of clock gate function values being a clock gating state that indicates an activation state of each of the local clocks collectively, wherein the conversion table indicates a conversion of the combination of output values to the clock gating state; and outputting a clock-gating-all-state group covering all the clock gating states possible in the target circuit based on the conversion table.

A clock gating analyzing according to another aspect of the present invention includes a detecting unit that detects a plurality of clock gates that supply a clock or terminate the clock to a plurality of sequential circuit elements in a target circuit; a clock-gate-function-calculating unit that calculates, for each of the clock gates, a clock gate function indicating activation of a local clock output from a local clock detected by the detecting unit; a conversion table generating unit that generates a conversion table by a substitution of a plurality of combinations of output values from the sequential circuit elements into each of the clock gate functions to calculate a plurality of combinations of clock gate function values, each combination of clock gate function values being a clock gating state that indicates an activation state of each of the local clocks collectively, wherein the conversion table indicates a conversion of the combination of output values to the clock gating state; and a clock-gating-all-state-group outputting unit that outputs a clock-gating-all-state group covering all the clock gating states possible in the target circuit based on the conversion table.

A clock gating analyzing method according to yet another aspect of the present invention includes detecting a plurality of clock gates that supply a clock or terminate the clock to a plurality of sequential circuit elements in a target circuit; calculating, for each of the clock gates, a clock gate function indicating activation of a local clock output from a local clock detected at the detecting; generating a conversion table by a substitution of a plurality of combinations of output values from the sequential circuit elements into each of the clock gate functions to calculate a plurality of combinations of clock gate function values, each combination of clock gate function values being a clock gating state that indicates an activation state of each of the local clocks collectively, wherein the conversion table indicates a conversion of the combination of output values to the clock gating state; and outputting a clock-gating-all-state group covering all the clock gating states possible in the target circuit based on the conversion table.

The other objects, features, and advantages of the present invention are specifically set forth in or will become apparent from the following detailed description of the invention when read in conjunction with the accompanying drawings.

FIG. 1 is a block diagram of a clock gating analyzing apparatus according to an embodiment of the present invention;

FIG. 2 is a circuit diagram of an example of a circuit to be analyzed by the clock gating analyzing apparatus;

FIG. 3 is a schematic of a clock gating state of the circuit shown in FIG. 2 ;

FIG. 4 is a functional diagram of a first configuration of the clock gating analyzing apparatus;

FIG. 5 is a schematic of a conversion table for the circuit shown in FIG. 2 ;

FIG. 6 is a flowchart of a first clock gating analyzing process of the clock gating analyzing apparatus;

FIG. 7 is a functional diagram of a second configuration of the clock gating analyzing apparatus;

FIG. 8 is a block diagram of a detailed functional configuration of an input pattern generating unit;

FIG. 9 is a schematic of a state table related to the circuit 200 shown in FIG. 2 ;

FIG. 10 is a schematic of a circuit state transition graph;

FIG. 11 is a schematic of a first search example of the state table;

FIG. 12 is a schematic of an example of state transition branch detection from a search result shown in FIG. 11 ;

FIG. 13 is a schematic of a second search example of the state table;

FIG. 14 is a schematic of an example of the state transition branch detection from the search result shown in FIG. 13 ;

FIG. 15 is a flowchart of a second clock gating analyzing process;

FIG. 16 is a flowchart of the process of generating an input pattern that increases the state coverage rate RS shown at step S 1505 ;

FIG. 17 is a flowchart of a procedure of an input pattern search process shown at step S 1606 ;

FIG. 18 is a functional diagram of a third configuration of the clock gating analyzing apparatus;

FIG. 19 is a schematic of the CG state transition graph;

FIG. 20 is a detailed functional diagram of a configuration of another input pattern generating unit;

FIG. 21 is a schematic of a first search example of the state table;

FIG. 22 is a schematic of a first detection example from the circuit state transition graph;

FIG. 23 is a flowchart of a third clock gating analyzing process of the clock gating analyzing apparatus;

FIG. 24 is a flowchart of a process of generating an input pattern that increases the state transition branch coverage rate RE at step S 2309 ;

FIG. 25 is a flowchart of an input pattern search process shown at step S 2404 ;

FIG. 26 is a functional diagram of a fourth configuration of the clock gating analyzing apparatus;

FIG. 27 is a flowchart of a fourth clock gating analyzing process of the clock gating analyzing apparatus;

FIG. 28 is a functional diagram of a fifth configuration of the clock gating analyzing apparatus;

FIG. 29 is a schematic of an example of generation of the error-state candidate;

FIG. 30 is a flowchart of a fifth clock gating analyzing process of the clock gating analyzing apparatus; and

FIG. 31 is a flowchart of a process for narrowing down error-state candidates.

Referring to the accompanying drawings, exemplary embodiments according to the present invention are explained in detail below.

FIG. 1 is a block diagram of a clock gating analyzing apparatus according to the embodiment of the present invention. A clock gating analyzing apparatus 100 includes a computer main body 110 , input devices 120 , and output devices 130 , and can be connected to a network 140 such as a local area network (LAN), a wide area network (WAN) and the internet through a router or modem not shown.

The computer main body 110 includes a CPU, a memory, and an interface. The CPU is responsible for overall control of the clock gating analyzing apparatus 100 . The memory includes read-only memory (ROM), a random access memory (RAM), a hard disk (HD), and a flash memory. The memory is used as a work area of the CPU.

The memory has various programs stored thereon, which are loaded in accordance with instructions from the CPU. On the HD and the optical disc 111 , data read/write is controlled by disc drives. The optical disc 111 and the flash memory are removable from the computer main body 110 . The interface controls input from the input devices 120 , output to the output devices 130 , and transmission/reception to/from the network 140 .

The input devices 120 include, for example, a keyboard 121 , a mouse 122 , and a scanner 123 . The keyboard 121 includes keys for inputting characters, numerical characters, various instructions, etc., to input data. Alternatively, a touch panel may be used. The mouse 122 moves a cursor, selects an area, and/or moves and resizes a window. The scanner 123 optically reads an image. The read image is captured as image data and stored in the memory in the computer main body 110 . The scanner 123 may have an optical character recognition (OCR) function.

The output devices 130 include a display 131 , a printer 132 , a speaker 133 , etc. The display 131 displays a cursor, icons or tool boxes as well as data such as documents, images, and function information. The printer 132 prints image data and document data. The speaker 133 outputs sound such as sound effects and read-out sound.

FIG. 2 is a circuit diagram of an example of a circuit to be analyzed by the clock gating analyzing apparatus 100 . A circuit 200 , a subject of analysis is represented by design data such as a netlist after logic synthesis. The circuit 200 is provided with a clock gate CGi (i=1, 2, . . . ). The clock gate CGi is a circuit that controls output of the clock output to a sequential circuit element (e.g., a flip-flop circuit, hereinafter, “FF”) and is configured by a logic gate such as an AND circuit.

More specifically, the output terminal of the clock gate CGi is connected to the clock terminal of the FF, and one input terminal receives a clock and the other input terminal receives a control signal to terminate the clock by the clock gating or to output the clock to the clock terminal of the sequential circuit element that is an output destination (whether direct or indirect). A clock clk output from the clock gate CGi to the destination sequential circuit element in this way is referred to as a local clock LCi.

The FFs receiving the same local clock LCi from the clock terminals are referred to as an “FF group Ai of the local clock LCi”. For example, an FF group A 1 of a local clock LC 1 includes an FF 2 and an FF 3 ; an FF group A 2 of a local clock LC 2 includes an FF 4 and an FF 5 ; and an FF group A 3 of a local clock LC 3 includes an FF 6 and an FF 7 .

Since an FF 1 receives no local clock LCi, the FF 1 does not belong to any FF group Ai. In FIG. 2 , reference numerals x 1 to x 3 are input values to the FF 1 , the FF 4 , and the FF 5 , respectively, and reference numerals y 1 to y 7 are output values from the FF 1 to FF 7 , respectively.

FIG. 3 is a schematic of the clock gating state of the circuit 200 shown in FIG. 2 . The clock gating state indicates a change in the state of a group of the clock gate CGi at the same time-point. The clock gating state collectively represents each state of the local clocks LCi in a group. The clock gating state includes active and inactive; in the active state, the local clock LCi is output to the FFs of the FF group Ai; and in the inactive state, the output of the local clock LCi is fixed to an inactive value (e.g., 0 in the case of a positive edge trigger FF and 1 in the case of a negative edge trigger FF).

FIG. 4 is a functional diagram of a first configuration of the clock gating analyzing apparatus 100 . The clock gating analyzing apparatus 100 is configured to generate a group (hereinafter, a “CG all-state group”) of the clock gating states (hereinafter, “CG states”) of the circuit 200 .

The clock gating analyzing apparatus 100 includes a clock gate detecting unit (CG detecting unit) 401 , a clock gate function (hereinafter, “CG function”) calculating unit 402 , a conversion table generating unit 403 , and a CG all-state group output unit 404 . The functions of the units 401 to 404 can be realized by the execution (by a computer) of relevant programs stored in the memory.

The output data from the units 401 to 404 are stored in the memory. Functional constituent elements at the destinations of connection indicated by arrows shown in FIG. 4 read, from the memory, the output data from functional constituent elements at the sources of connections and the CPU executes the programs related to the functions.

First, the clock gate detecting unit 401 receives design data 400 , such as a netlist related to the circuit 200 , to detect the clock gate CGi present in the circuit 200 represented by the design data 400 . Specifically, among cells present between the clock source and the FF, cells other than buffers and inverters (e.g., the above AND circuit) are detected as the clock gates.

The CG function calculating unit 402 calculates a CG function representing activation/inactivation of the local clock LCi output from the clock gate CGi detected by the CG detecting unit 401 . The CG function is a function that represents a value of the control signal input to the other input terminal other than the input terminal of the clock clk in the clock gate CGi. The CG function of the clock gate CGi is hereinafter referred to as fi. The CG function fi indicates activation/inactivation of the local clock LCi (at the current time) of the clock gate CGi.

For example, since the clock gate CG 1 receives the output y 1 of the FF 1 as the control signal, the CG function f 1 of the clock gate CG 1 is expressed as

f1=y1  (1)

Since the clock gate CG 2 receives the output from a NAND circuit as the control signal, the CG function f 2 of the clock gate CG 2 is expressed as

f 2=( y 1 ×y 2 ×y 3)′  (2)

where “×” represents the logical AND operator and “′” represents the logical NOT operator.

Since the clock gate CG 3 receives the output from an OR circuit as the control signal, the CG function f 3 of the clock gate CG 3 is expressed as

f 3 =y 1′+ y 2+ y 3  (3)

where “+” is logical OR operator.

Based on the CG function fi calculated by the CG function calculating unit 402 , the conversion table generating unit 403 generates a conversion table T 1 of the conversion of FF output value combinations to the CG state, the FF output values being input sources.

Specifically, a truth table is generated as the conversion table T 1 to perform conversion on the combinations of the output values yj from the FFs that are the input sources to the clock gate CGi and on the combinations of the CG functions fi of the clock gate CGi.

The circuit 200 of FIG. 2 will be taken as an example for description. FIG. 5 is a schematic of the conversion table T 1 for the circuit 200 shown in FIG. 2 . Since the input-source FFs of the clock gate CG 1 to CG 3 are the FF 1 to FF 3 and the output values thereof are y 1 , y 2 , and y 3 , respectively, eight patterns of the output value combination {y 1 , y 2 , y 3 } exist. By substituting the eight patterns of the combination {y 1 , y 2 , y 3 } for the CG functions f 1 to f 3 , the converted combination {f 1 , f 2 , f 3 } can be obtained.

In the case of the CG function fi=1, since the local clock LCi is in the active state, the local clock LCi is supplied to the clock terminals of the FFs in the FF group. Therefore, {f 1 , f 2 , f 3 } shown in FIG. 5 directly represents the clock gating state, and “1” and “0” represent the active state and the inactive state, respectively.

For example, in FIG. 5 , if {f 1 , f 2 , f 3 }={0, 1, 1}, this represents that the clock gate CG 1 terminates the supply of the local clock LC 1 to the clock terminals of the FFs in the FF group A 1 , that the clock gate CG 2 supplies the local clock LC 2 to the clock terminals of the FFs in the FF group A 2 , and that the clock gate CG 3 supplies the local clock LC 3 to the clock terminals of the FFs in the FF group A 3 .

As shown in FIG. 4 , the CG all-state group output unit 404 outputs a CG all-state group S based on the conversion table T 1 generated by the conversion table generating unit 403 . The CG all-state group S is a CG state group including all the CG states possible.

Specifically, for example, since the conversion table T 1 covers all the combinations of the output values {y 1 , y 2 , y 3 } of the FF 1 to FF 3 that are the input sources of the clock gate CG 1 to CG 3 , the CG all-state group S can be acquired by organizing the conversion results, i.e., the CG state {f 1 , f 2 , f 3 }.

For example, the conversion table T 1 shown in FIG. 5 , although up to eight CG states emerge because the CG state {f 1 , f 2 , f 3 } is a combination of the CG functions f 1 to f 3 , the CG state {f 1 , f 2 , f 3 } can take on four patterns, which include {0, 1, 1}, {1, 1, 0}, {1, 1, 1}, and {1, 0, 1} since overlapping CG states exist.

FIG. 6 is a flowchart of a first clock gating analyzing process of the clock gating analyzing apparatus 100 . First, the design data 400 stored in the memory are read (step S 601 ) and the clock gate detecting unit 401 detects the clock gate CGi in the circuit 200 (step S 602 ). The index i=1 and the clock gate detection count n are defined for the clock gate CGi (step S 603 ), and the CG function calculating unit 402 calculates the CG function fi of the clock gate CGi (step S 604 ).

It is determined whether i>n is satisfied (step S 605 ), and if i>n is not satisfied (step S 605 : NO), i is incremented by one (step S 606 ) and the process returns to step S 604 . On the other hand, if i>n is satisfied (step S 605 : YES), the conversion table generating unit 403 creates the conversion table T 1 (step S 607 ). The CG all-state group output unit 404 outputs the CG all-state group S (step S 608 ).

According to the first configuration and the first clock gating analyzing process of the clock gating analyzing apparatus 100 , a mutual change in the state of the clock gate CGi can be automatically generated for each time-point.

In a second configuration, the CG all-state group S generated by the first configuration shown in FIG. 4 is used to calculate a state coverage rate of the CG state and to generate an input pattern that increases the state coverage rate. The same reference numerals refer to the same constituent elements as those shown in FIG. 4 and description thereof is omitted.

FIG. 7 is a functional diagram of the second configuration of the clock gating analyzing apparatus 100 . The clock gating analyzing apparatus 100 includes a simulation executing unit 701 , a state-coverage-rate calculating unit 702 , a non-detected CG state extracting unit 703 , and an input pattern generating unit 704 . The functions of the units 701 to 704 can be realized by executing, with the CPU, relevant programs stored in the memory.

The output data from the units 701 to 704 are stored in the memory. Functional constituent elements at the destinations of connection indicated by arrows shown in FIG. 7 read, from the memory, the output data from functional constituent elements at the sources of connection and the CPU executes the programs related to the functions.

First, the simulation executing unit 701 inputs an arbitrary input pattern (hereinafter, “first input pattern P 1 ”) P 1 to the design data 400 to execute a circuit simulation of the circuit 200 . The simulation executing unit 701 can be realized by an existing analysis tool. The CG state is detected for each time-point from the simulation result. The CG state detected from the simulation result of the simulation executing unit 701 is referred to as a “detected CG state 710 ”.

Since the CG all-state group S covers all the CG states generated in the circuit 200 , all the detected CG states 710 are included in the CG all-state group S.

The state-coverage-rate calculating unit 702 calculates a state coverage rate RS, which is a rate of the detected CG states 710 covering the CG all-state group S. That is, the state coverage rate RS is calculated by defining the number of CG-states in the CG all-state group S as a denominator value and number of the detected CG states 710 as a numerator value. For example, if the three detected CG states 710 exist which are {011}, {110}, and {111}, three CG states are covered in the CG all-state group S shown in FIG. 5 and, therefore, the state coverage rate RS is 3/4.

The non-detected CG state extracting unit 703 extracts the CG states other than the detected CG states 710 from the CG all-state group S shown in FIG. 5 (hereinafter, “non-detected CG state 720 ”). For example, if {011}, {110}, and {111} are the detected CG states 710 from the CG all-state group S shown in FIG. 5 , while {101} is identified as the non-detected CG state 720 .

The input pattern generating unit 704 generates an input pattern covering the non-detected CG states (hereinafter, a “second input pattern P 2 ”). The input pattern generating unit 704 will specifically be described.

FIG. 8 is a detailed functional diagram of the input pattern generating unit 704 . The input pattern generating unit 704 includes a next-state function calculating unit 801 , a state table generating unit 802 , a circuit-state-transition-graph generating unit 803 , a searching unit 804 , and an output unit 805 . The next-state function calculating unit 801 analyzes the design data 400 to calculate a next-state function zj of the FFs. The next-state function zj is a function indicating an output of each FF at the next time-point.

The circuit 200 shown in FIG. 2 is used for description. Since x 1 is input to the FF 1 at each time-point, a next-state function z 1 is expressed as

f1=x1  (4)

If y 1 to y 3 are output from the FF 1 to FF 3 at the current time-point, the output of the AND circuit on the input side of the FF 2 is received as the output of the FF 2 at the next time-point. Therefore, a next-state function z 2 is expressed as

z 2 =y 1′ ×y 3  (5)

If y 1 to y 3 are output from the FF 1 to FF 3 at the current time-point, the output of the NOR circuit on the input side of the FF 3 is received as the output of the FF 3 at the next time-point. Therefore, a next-state function z 3 is expressed as

z 3=( y 1+ y 2)′  (6)

The state table generating unit 802 generates a state table T 2 based on the next-state function zj calculated by the next-state function calculating unit 801 and the conversion table T 1 . The state table T 2 is a table correlating the input pattern x 1 , the FF output {y 1 , y 2 , y 3 } at the current time-point, the FF output {z 1 , z 2 , z 3 } at the next time-point, the CG state {f 1 , f 2 , f 3 } at the current time-point, and the CG state {g 1 , g 2 , g 3 } at the next time-point.

FIG. 9 is a schematic of the state table T 2 related to the circuit 200 shown in FIG. 2 . A first column from the left of the state table T 2 shows values of the input x 1 . A second column shows values of the FF output {y 1 , y 2 , y 3 } at the current time-point. It is assumed here that the values of the initial state are {y 1 , y 2 , y 3 }={0, 0, 0}.

A third column shows values of the FF output {z 1 , z 2 , Z 3 } at the next time-point. The values of {z 1 , z 2 , Z 3 } indicate the next output values of {y 1 , y 2 , y 3 } on the left thereof.

A fourth column shows the CG state {f 1 , f 2 , f 3 } at the current time-point. The values of {f 1 , f 2 , f 3 } are values acquired by converting the values of the FF output {y 1 , y 2 , y 3 } at the current time-point with the use of the conversion table T 1 .

A fifth column shows the CG state {g 1 , g 2 , g 3 } at the next time-point. The values of {g 1 , g 2 , g 3 } are values acquired as a conversion result {f 1 , f 2 , f 3 } of the conversion performed by substituting the values of the FF output {z 1 , z 2 , z 3 } at the next time-point for {f 1 , f 2 , f 3 } of the conversion table T 1 .

As shown in FIG. 8 , the circuit-state-transition-graph generating unit 803 generates a state transition graph G 1 (hereinafter, a “circuit state transition graph G 1 ”) of the circuit 200 with the use of the two columns on the left side of the state table T 2 . However, since the object is to obtain the clock gate function, the FFs to be considered as the state of the circuit include only an FF included in the clock gate function and an FF considered as the state of the FF circuit included in the next state function of that FF. FIG. 10 is a schematic of the circuit state transition graph G 1 .

Numeric strings surrounded by ellipses are nodes representing the output of the FFs (values of the FF output {y 1 , y 2 , y 3 } at the current time-point), and arrows represent state transition branches. Nodes at the start of the arrows are nodes of transition sources, and nodes at the end of the arrows are nodes of transition destinations (the values of the FF output {z 1 , z 2 , z 3 } at the next time-point). A node {000} is a node representing the initial state.

The searching unit 804 assumes the non-detected clock gating state 720 as the clock gating state of the next time-point to search the circuit state transition graph G 1 for the state transition branch(es) from a combination of FF output values at the next time-point (corresponding to the non-detected clock gating state 720 ) to the initial state. Specifically, in the circuit state transition graph G 1 , the searching unit 804 searches for the second input pattern P 2 , which is a value of the input x 1 and a time-point at the time of each state transition from the FF output {y 1 , y 2 , y 3 }={0, 0, 0} in the initial state to the values of the FF output {z 1 , z 2 , z 3 } at the next time-point causing the non-detected CG state 720 to emerge.

The output unit 805 outputs the second input pattern P 2 obtained by the searching unit 804 . Specifically, for example, the second input pattern P 2 may be stored in the memory or may be output from the output device.

The searching process of the searching unit 804 will be described in detail. The state table T 2 is searched for a value of the input x 1 that causes the CG state at the next time-point to become the non-detected CG state 720 , the FF output at the current time-point, and the FF output at the next time-point.

FIG. 11 is a schematic of a first search example of the state table T 2 . For example, if the non-detected CG state 720 is {111}, the state table T 2 is searched for x 1 , {y 1 , y 2 , y 3 }, and {z 1 , z 2 , z 3 } that cause the CG state at the next time-point to become {g 1 , g 2 , g 3 }={111} (shown by hatching in FIG. 11 ).

From the circuit state transition graph G 1 , a state transition branch is then detected for the search result, i.e., from the value of the FF output {y 1 , y 2 , y 3 } at the current time-point to the value of the FF output {z 1 , z 2 , z 3 } at the next time-point. FIG. 12 is a schematic of an example of state transition branch detection from the search result shown in FIG. 11 .

The search result shown in FIG. 11 includes {y 1 , y 2 , y 3 }={000} and {z 1 , z 2 , z 3 }={101}. Therefore, a state transition branch e 01 is detected which transitions from a node N 0 , i.e., {000} to a node N 1 , i.e., {101}. It can be known from the search result shown in FIG. 11 that the value of the input x 1 at the time of the state transition of the state transition branch e 01 is x 1 =1.

It is determined whether the state transition source, i.e., the node N 0 is a node in the initial state. Since the value of the node N 0 is {y 1 , y 2 , y 3 }={000}, the node is in the initial state. Therefore, a time-point t=0 is correlated with the value (x 1 =1) of the input x 1 at the time of the state transition of the state transition branch e 01 , and the identified input pattern (the second input pattern P 2 ) is “the input x 1 =1 at the time-point t=0 (initial state)”.

If the non-detected CG state 720 is {111}, another set of x 1 , {y 1 , y 2 , y 3 }, and {z 1 , z 2 , z 3 } exists that causes the CG state at the next time-point to become {g 1 , g 2 , g 3 }={111}. FIG. 13 is a schematic of a second search example of the state table T 2 . In FIG. 13 , the search result in this case is a row indicated by a reference numeral 1301 (shown by hatching).

From the circuit state transition graph G 1 , a state transition branch is detected for the search result, i.e., from the value of the FF output {y 1 , y 2 , y 3 } at the current time-point to the value of the FF output {z 1 , z 2 , z 3 } at the next time-point. FIG. 14 is a schematic of an example of the state transition branch detection from the search result shown in FIG. 13 .

The search result shown in FIG. 13 includes {y 1 , y 2 , y 3 }={011} and {z 1 , z 2 , z 3 }={110}. Therefore, a state transition branch e 34 is detected which transitions from a node N 3 , i.e., {011} to a node N 4 , i.e., {110}. It can be known from a row 1301 of the search result shown in FIG. 13 that the value of the input x 1 at the time of the state transition of the state transition branch e 34 is x 1 =1.

It is determined whether the state transition source, i.e., the node N 3 is a node in the initial state. Since the value of the node N 3 is {y 1 , y 2 , y 3 }={011}, the node is not in the initial state. Therefore, a node N 2 is searched for, which is a transition source having the node N 3 as a state transition destination. From the state table T 2 , it can be known, from a row 1302 shown in FIG. 13 , that the value of the input x 1 at the time of the state transition from the node N 2 to the node N 3 is x 1 =0.

It is determined whether the state transition source, i.e., the node N 2 is a node in the initial state. Since the value of the node N 3 is {y 1 , y 2 , y 3 }={001}, the node is not in the initial state. Therefore, a node N 0 is searched for, which is a transition source having the node N 2 as a state transition destination. From the state table T 2 , it can be known, from a row 1303 shown in FIG. 13 , that the value of the input x 1 at the time of the state transition from the node N 0 to the node N 2 is x 1 =0.

It is determined whether the state transition source, i.e., the node N 0 is a node in the initial state. Since the value of the node N 0 is {y 1 , y 2 , y 3 }={000}, the node is in the initial state. In this search process, on the circuit state transition graph G 1 , the state transition (e 02 ) occurs at the time-point t=0 from the node N 0 to the node N 2 ; the state transition (e 23 ) occurs at the next time-point t=1 from the node N 2 to the node N 3 ; and the state transition (e 34 ) occurs at the next time-point t=2 from the node N 3 to the node N 4 . Therefore, the values of the input x 1 of the state transition branches e 02 , e 23 , and e 34 are correlated with each time-point t.

Therefore, another obtained input pattern (the second input pattern P 2 ) is “the input x 1 =0 at the time-point t=0 (initial state), the input x 1 =0 at the time-point t=1, and the input x 1 =1 at the time-point t=2”. This pattern may be a pattern for detecting the non-detected state {110}. The non-detected CG state 720 is generated by applying the identified second input pattern P 2 to the circuit 200 .

The second clock gating analyzing process is a process for the second configuration shown in FIG. 7 . FIG. 15 is a flowchart of the second clock gating analyzing process.

First, waiting for input of the first input pattern P 1 occurs (step S 1501 : NO). If the first input pattern P 1 has been input (step S 1501 : YES), the simulation executing unit 701 executes a circuit simulation of the circuit 200 (step S 1502 ).

The state-coverage-rate calculating unit 702 calculates a state coverage rate RS indicating how much of the CG all-state group S is covered by the detected CG states 710 acquired as the result of the execution of the circuit simulation (step S 1503 ). The non-detected CG state extracting unit 703 extracts the non-detected clock gating state 720 , which is the CG state other than the detected CG states 710 , from the CG all-state group S (step S 1504 ). A process is then executed to generate an input pattern that increases the state coverage rate RS (step S 1505 ).

FIG. 16 is a flowchart of the process of generating the input pattern that increases the state coverage rate RS shown at step S 1505 . First, the next-state function calculating unit 801 calculates the next-state function zj of the FFs in the circuit 200 (step S 1601 ). The state table generating unit 802 then generates the state table T 2 (step S 1602 ). The circuit-state-transition-graph generating unit 803 generates the circuit state transition graph G 1 (step S 1603 ).

It is determined whether NS=Ø (null set) (step S 1604 ). The NS is a group of the non-detected clock gating states 720 . If NS≠Ø (step S 1604 : NO), the arbitrary non-detected clock gating state 720 is extracted from the NS and the non-detected clock gating state 720 is deleted from the NS (step S 1605 ).

The searching unit 804 executes an input pattern search process (step S 1606 ). The details of the input pattern search process will be described later. The process then returns to step S 1604 . If NS=Ø at step S 1604 (step S 1604 : YES), the output unit 805 outputs the search result as the input pattern (the second input pattern P 2 ) that increases the state coverage rate RS (step S 1607 ).

FIG. 17 is a flowchart of a procedure of the input pattern search process shown at step S 1606 . First, the CG state at the next time-point (corresponding to the non-detected clock gating state 720 ) is detected from the state table T 2 (step S 1701 ). The state table T 2 is searched for the value of the input x 1 , the value of the FF output {y 1 , y 2 , y 3 } at the current time-point, and the value of the FF output {z 1 , z 2 , z 3 } at the next time-point that bring about the detected CG state (step S 1702 ).

The value of the FF output {z 1 , z 2 , z 3 } at the next time-point is assumed as a state transition destination node (search start node) (step S 1703 ), and a transition source node for the transition destination node and a state transition branch between these nodes are identified from the circuit state transition graph G 1 (step S 1704 ).

The identified state transition branch is correlated with a value of the input x 1 identified by the transition source node (FF output {y 1 , y 2 , y 3 } at the current time-point) (step S 1705 ). It is determined at this point whether the transition source node is a node representing the initial state (step S 1706 ). If the node does not represent the initial state (step S 1706 : NO), it is determined whether a path has already been searched for from the node representing the initial state to the transition source node (step S 1707 ).

If the path has already been searched for (step S 1707 : YES), the process returns to step S 1709 . On the other hand, if the path has not already been searched for (step S 1707 : NO), the path is searched for from the node representing the initial state to the transition source node (step S 1708 ). The transition source node is newly assumed as the transition destination node (step S 1709 ), and a transition source node for that transition destination node and a state transition branch between these nodes are identified from the circuit state transition graph G 1 according to the identified path (step S 1710 ). The process then returns to step S 1705 .

On the other hand, if the transition source node is a node representing the initial state at step S 1706 (step S 1706 : YES), the time-points of the state transitions of the identified state transition branches are calculated from the circuit state transition graph G 1 and are correlated with the values of the input x 1 of the state transition branches (step S 1711 ).

It is then determined whether to terminate the process (step S 1712 ), specifically, if another value is included in the FF output {z 1 , z 2 , z 3 } at the next time-point identified at step S 1702 , the process is not terminated (step S 1712 : NO) and returns to step S 1703 , and if no other value is included in the FF output {z 1 , z 2 , z 3 } at the next time-point searched at step S 1702 , the process returns to step S 1604 shown in FIG. 16 .

According to the second configuration and the second clock gating analyzing process of the clock gating analyzing apparatus 100 , verification oversights of clock gate function bugs causing a function bug in the circuit 200 can be reduced by obtaining the state coverage rate RS and increasing the state coverage rate RS at the time of the function verification of the circuit 200 by simulation.

The state coverage rate RS can be automatically increased by generating the second input pattern P 2 that causes the CG state(s) not covered (non-detected clock gating state 720 ) to emerge, thereby enabling verification oversights of clock gate function bugs causing function bugs in the circuit 200 to be prevented.

According to the third configuration, the CG all-state group S generated by the first configuration shown in FIG. 4 is used to calculate a state transition branch coverage rate of the CG state transition branches and to generate an input pattern that increases the state transition branch coverage rate. The same reference numerals refer to the same constituent elements as those shown in FIGS. 4 , 7 , and 8 and description thereof is omitted.

FIG. 18 is a functional diagram of the third configuration of the clock gating analyzing apparatus 100 . The clock gating analyzing apparatus 100 includes the simulation executing unit 701 , the next-state function calculating unit 801 , the state table generating unit 802 , a CG-state-transition-graph generating unit 1801 , a CG-all-state-transition-branch output unit 1802 , a state-transition-branch-coverage-rate calculating unit 1803 , a non-detected-CG-state-transition-branch extracting unit 1804 , and an input pattern generating unit 1805 . The functions of the units 701 , 801 , 802 , and 1801 to 1805 can be realized by executing, by the CPU, relevant programs stored in the memory.

The output data from the units 701 , 801 , 802 , 1801 to 1805 are stored in the memory. Functional constituent elements at the destinations of connections indicated by arrows shown in FIG. 18 read, from the memory, the output data from functional constituent elements at the sources of connections and the CPU executes programs related to the functions.

The CG-state-transition-graph generating unit 1801 uses the state table T 2 to generate a CG state transition graph G 2 representing the state transitions of the CG states. FIG. 19 is a schematic of the CG state transition graph G 2 . Nodes M 1 to M 4 represent the CG states and arrows represent the state transition branches. The state transition branch is created by the state transition from a value of {y 1 , y 2 , y 3 } representing the CG state at the current time-point to a value of {z 1 , z 2 , Z 3 } representing the CG state at the next time-point in the state table T 2 .

As shown in FIG. 18 , the CG-all-state-transition-branch output unit 1802 extracts and outputs, as a CG all-state transition branch group E, all the state transition branches of the clock gating states from the CG state transition graph G 2 created by the CG-state-transition-graph generating unit 1801 . Specifically, the CG all-state transition branch group E is stored in the memory.

The state-transition-branch-coverage-rate calculating unit 1803 calculates a state transition branch coverage rate of the circuit 200 . Specifically, since a CG state of each time-point is detected from the simulation result of the simulation executing unit 701 , a CG state transition branch representing the state transition thereof is also detected for each time-point. The CG state transition branch detected from the simulation result of the simulation executing unit 701 is referred to as a “detected CG state transition branch 1810 ”.

A state transition branch coverage rate RE represents how much of the CG all-state transition branch group E is covered by the detected CG state transition branches 1810 . That is, the CG all-state transition branch group E is calculated by defining the number of all the branches of the CG all-state transition branch group E as a denominator value and the number of branches of the detected CG state transition branches 1810 as a numerator value. For example, if the detected CG state transition branches 1810 are all the branches except a state transition branch d 21 in FIG. 19 , the number of all the branches of the CG all-state transition branch group E is nine and, therefore, the state transition branch coverage rate RE is 8/9.

As shown in FIG. 18 , the non-detected-CG-state-transition-branch extracting unit 1804 extracts transition branches other than the detected CG state transition branches 1810 from the CG all-state transition branch group E (hereinafter, “non-detected CG state transition branch 1820 ”). For example, if the detected CG state transition branches 1810 are all the branches except the state transition branch d 21 shown in FIG. 19 , the transition branch d 21 is extracted as the non-detected CG state transition branch 1820 .

The input pattern generating unit 1805 generates an input pattern covering the non-detected CG state transition branches 1820 (hereinafter, a “third input pattern P 3 ”). The input pattern generating unit 1805 will specifically be described. FIG. 20 is a detailed functional diagram of a configuration of the input pattern generating unit 1805 .

The input pattern generating unit 1805 includes the circuit-state-transition-graph generating unit 803 , a searching unit 2001 , and an output unit 2002 . The searching unit 2001 assumes the non-detected CG state transition branch 1820 as the clock gating state transition branch of the next time-point to search for the state transition from the circuit state transition branch corresponding to the non-detected CG state transition branch 1820 to the initial state in the circuit state transition graph G 1 created by the circuit-state-transition-graph generating unit 803 .

Specifically, in the circuit state transition graph G 1 , the searching unit 2001 searches for the third input pattern P 3 , which is a value of the input x 1 and a time-point at the time of each state transition from the FF output {y 1 , y 2 , y 3 }={0, 0, 0} in the initial state to the values of the FF output {z 1 , z 2 , z 3 } at the next time-point causing the non-detected CG state transition branch 1820 to emerge.

The output unit 2002 outputs the third input pattern P 3 identified by the searching unit 2001 . Specifically, for example, the third input pattern P 3 may be stored in the memory or may be output from the output device.

The searching process of the searching unit 2001 will be described in detail. The searching unit 2001 detects from the CG state transition graph G 2 a combination of the CG state at the current time-point (i.e., the transition source of the non-detected CG state transition branch 1820 ), and the CG state at the next time-point (i.e., the transition destination of the non-detected CG state transition branch 1820 ).

For example, as shown in FIG. 19 , if the non-detected CG state transition branch 1820 is d 21 , the CG state {101} of the transition source is the CG state at the current time-point, and the CG state {011} of the transition destination is the CG state at the next time-point.

The state table T 2 is searched for a value of the input x 1 that causes the detected CG states at the current time-point and the next time-point to emerge, the values of the FF output {y 1 , y 2 , y 3 } at the current time-point, and the values of the FF output {z 1 , z 2 , z 3 } at the next time-point.

FIG. 21 is a schematic of a first search example of the state table T 2 . The state table T 2 is searched for a row having {101} as the CG state of the current time-point and {011} as the CG state at the next time-point (reference numeral 2201 ).

The detection from the circuit state transition graph G 1 is performed for a transition source node representing the identified values of the FF output {y 1 , y 2 , y 3 } at the current time-point, a transition destination node representing the FF output {z 1 , z 2 , z 3 } at the next time-point, and a state transition branch representing the state transition from the transition source node to the transition destination node. The detected state transition branch is correlated with the value of the input x 1 detected previously. The state transition branch detected at this point is referred to as a “tail-end state transition branch”.

FIG. 22 is a schematic of a first detection example from the circuit state transition graph G 1 . From the state table T 2 , the identified value of the input x 1 is x 1 =0; the value of the FF output {y 1 , y 2 , y 3 } at the current time-point is {111}; and the output the FF output {z 1 , z 2 , z 3 } at the next time-point is {000}. Therefore, a node N 5 is detected as the transition source node; a node N 0 is detected as the transition destination node; and a state transition branch e 50 between the nodes N 5 and N 0 is detected as the tail-end state transition branch that causes the non-detected CG state transition branch d 21 to emerge. The tail-end state transition branch e 50 is correlated with x 1 =0.

A state transition branch one time-point before the tail-end state transition branch and a corresponding value of the input x 1 at that time-point are then identified. Specifically, a row one time-point before the identified row is searched for in the state table T 2 . That is, a row is searched for, where the values of the FF output {z 1 , z 2 , z 3 } at the next time-point is defined as the values of the FF output {y 1 , y 2 , y 3 } at the current time-point of the identified row and the CG state at the next time-point is defined as the CG state at the current time-point of the identified row. In FIG. 21 , a row indicated by a reference numeral 2202 is searched for as the row one time-point before the row indicated by the reference numeral 2201 .

For the identified one-time-point-before row, the detection from the circuit state transition graph G 1 is also performed for a transition source node representing the values of the FF output {y 1 , y 2 , y 3 } at the current time-point, a transition destination node representing the FF output {z 1 , z 2 , z 3 } at the next time-point, and a state transition branch representing the state transition from the transition source node to the transition destination node. The detected state transition branch is correlated with the value of the input x 1 detected previously.

For example, in the case of the identified one-time-point-before row 2202 , from the state table T 2 , the value of the input x 1 in the one-time-point-before row is x 1 =1; the values of the FF output {y 1 , y 2 , y 3 } at the current time-point are {001}; and the values of the FF output {z 1 , z 2 , z 3 } at the next time-point are {111}. Therefore, the node N 2 is detected as the transition source node; the node N 5 is detected as the transition destination node; and a state transition branch e 25 between the nodes N 2 and N 5 is detected as the state transition that causes the non-detected CG state transition branch d 21 to emerge. The state transition branch e 25 is correlated with x 1 =1.

It is then determined whether the transition source node detected based on the one-time-point-before row is the node N 0 representing the initial state {000} on the circuit state transition graph G 1 . If the node is the node N 0 representing the initial state, the state transition branch correlated with the value of the input x 1 is further correlated with the time-point t=0. Each time the transition to the state transition branch of the transition destination occurs, the time-point t is incremented by one time-point. If the node is not the node N 0 , a path from the node N 0 to the transition destination node is searched for.

For example, as shown in FIG. 22 , since the transition source node N 2 is not the node N 0 , a path from the node N 0 to the node N 2 is searched for. Although a path for N 0 →N 2 (the shortest path) is searched for in this case, the search can freely be performed, for example, for a number of state transition branches that exceeds a predetermined number.

The transition source node detected based on the one-time-point-before row is defined as a transition destination node to identify a transition source node and a transition branch between the nodes according the identified path. For example, as shown in FIG. 22 , the transition source node N 2 is defined as a transition destination node, and according to the identified path, the node N 0 is defined as a transition source node.

In the state table T 2 , a row is searched for where the newly set transition source node is defined as the values of the FF output {y 1 , y 2 , y 3 } at the current time-point and the transition destination node is defined as the values of the FF output {z 1 , z 2 , z 3 } at the next time-point, and a value of the input x 1 in this case is identified and correlated with the transition branch.

For example, as shown in FIG. 22 , the new transition destination node is the node N 2 and the new transition source node, according to the identified path, is the node NO. Therefore, as shown in FIG. 21 , a row indicated by a reference numeral 2203 is searched for. Therefore, as shown in FIG. 22 , the value of the input x 1 (x 1 =1) is correlated with the transition branch e 02 .

If the transition source node is not the node N 0 at this point, the process is further continued according to the identified path, and if the node is the node N 0 , the state transition branch correlated with the value of the input x 1 is further correlated with the time-point t=0. Each time the transition to the state transition branch of the transition destination occurs, the time-point t is incremented by one time-point. The values of the input x 1 and the time-point t correlated with the state transition branches are the input pattern (the third input pattern P 3 ) that increases the state transition branch coverage rate RE.

For example, as shown in FIG. 22 , since the transition destination node at this point is the node N 2 and the transition source node is the node N 0 , the transition branch e 02 correlated with the value of the input x 1 (x 1 =0) is correlated with the time-point t=0 representing the initial state. Therefore, the transition branch e 02 is correlated with x 1 =0 and t=0; the transition branch e 25 is correlated with x 1 =1 and t=1; and the transition branch e 50 is correlated with x 1 =0 and t=2. Therefore, the third input pattern P 3 is “the input x 1 =0 at the time-point t=0 (initial state), x 1 =1 at the time-point t=1, and x 1 =0 at the time-point t=2”.

A third clock gating analyzing process is a process for the third configuration shown in FIG. 18 . FIG. 23 is a flowchart of the third clock gating analyzing process of the clock gating analyzing apparatus 100 .

First, the next-state function calculating unit 801 calculates the next-state function (step S 2301 ), and the state table generating unit 802 generates the state table T 2 (step S 2302 ). The CG-state-transition-graph generating unit 1801 generates the CG state transition graph G 2 (step S 2303 ). The CG-all-state-transition-branch output unit 1802 extracts and outputs all of the state transition branches of the clock gating state from the CG state transition graph G 2 as a CG all-state transition branch group E (step S 2304 ).

The input of the first input pattern P 1 is then waited for (step S 2305 : NO), and if the first input pattern P 1 has been input (step S 2305 : YES), the simulation executing unit 701 executes a circuit simulation (step S 2406 ).

The state-transition-branch-coverage-rate calculating unit 1803 calculates the state transition branch coverage rate RE (step S 2307 ), and branches other than the detected CG state transition branches 1810 are extracted, from the state transition branch group E, as the non-detected CG state transition branch 1820 (step S 2308 ). A process is then executed to generate an input pattern that increases the CG all-state transition branch coverage rate RE (step S 2309 ).

FIG. 24 is a flowchart of a process of generating an input pattern that increases the state transition branch coverage rate RE at step S 2309 . First, the circuit-state-transition-graph generating unit 803 generates the circuit state transition graph G 1 (step S 2401 ), and it is determined whether NE=Ø (empty set) (step S 2402 ).

The NE is a group of the non-detected CG state transition branches 1820 . If not NE=Ø (step S 2402 : NO), the arbitrary non-detected CG state transition branches 1820 are extracted and deleted from the NE (step S 2403 ). The searching unit 2001 executes an input pattern search process (step S 2404 ). The details of the input pattern search process are described hereinafter.

The process returns to step S 2402 . If NE=Ø at step S 2402 (step S 2402 : YES), the output unit 2002 outputs the search result as the input pattern (the third input pattern P 3 ) that increases the state transition branch coverage rate RE (step S 2405 ).

FIG. 25 is a flowchart of the input pattern search process shown at step S 2404 . First, the CG states at the current and next time-points coinciding with the transition source and destination of the non-detected CG state transition branch 1820 are detected from the state table T 2 (step S 2501 ).

The state table T 2 is searched for the value of the input x 1 that generates the detected CG state, the values of the FF output {y 1 , y 2 , y 3 } at the current time-point, and the values of the FF output {z 1 , z 2 , z 3 } at the next time-point (step S 2502 ).

From the circuit state transition graph G 1 , the tail-end state transition branch is identified, which has the values of the FF output {y 1 , y 2 , y 3 } at the current time-point as the transition source node and the values of the FF output {z 1 , z 2 , z 3 } at the next time-point as the transition source node (step S 2503 ).

The value of the input x 1 at the time of generation of the identified tail-end state transition branch is read from the state table T 2 and is correlated with the tail-end state transition branch (step S 2504 ). A state transition branch one time-point before the tail-end state transition branch and the value of the input x 1 at that time-point are identified (step S 2505 ). The state transition branch is correlated with the value of the input x 1 at that time-point (step S 2506 ).

It is determined whether the state transition source node identified by the state transition branch is a node representing the initial state (step S 2507 ). If the node does not represent the initial state (step S 2507 : NO), it is determined whether a path (from the node representing the initial state to the state transition source node) has already been searched for (step S 2608 ).

If the path has already been searched for (step S 2508 : YES), the process proceeds to step S 2510 . On the other hand, if the path has not already been searched for (step S 2508 : NO), the path (from the node representing the initial state to the state transition source node) is searched for (step S 2509 ).

The transition source node is assumed as the transition destination node (step S 2510 ), and a transition source node of the newly assumed transition destination node and a state transition branch therebetween are identified according to the path (step S 2511 ). The value of the input x 1 at the time of generation of the state transition due to this state transition branch is then read from the state table T 2 and correlated with the state transition branch (step S 2512 ). The process returns to step S 2507 .

At step S 2507 , if the state transition source node is a node representing the initial state at step S 2507 (step S 2507 : YES), the time-points of the state transitions of the acquired state transition branches are calculated based on the initial state (t=0) and are correlated with the values of the input x 1 corresponding with the state transition branches (step S 2513 ).

It is determined whether to terminate the process (step S 2514 ). Specifically, for example, if another value is included in the FF output {z 1 , z 2 , z 3 } at the next time-point identified at step S 2502 , the process is not terminated (step S 2514 : NO) and returns to step S 2503 , and if no other value is included in the FF output {z 1 , z 2 , z 3 } at the next time-point identified at step S 2502 , the process returns to step S 2402 shown in FIG. 24 .

According to the third functional configuration and the third clock gating analyzing process of the clock gating analyzing apparatus 100 , verification oversights of a clock gate function bug causing a function bug in the circuit 200 can be reduced by obtaining the state transition branch coverage rate RE and increasing the state transition branch coverage rate RE at the time of function verification of the circuit 200 by simulation.

The state transition branch coverage rate RE can automatically be increased by generating the third input pattern P 3 that causes the CG state(s) not covered (non-detected CG state transition branch 1820 ) to emerge, thereby enabling verification oversights of a clock gate function bug causing a function in the circuit 200 to be prevented.

According to a fourth configuration, the CG all-state group S generated by the first configuration shown in FIG. 4 is used to verify a possibility of recovery from the inactive state to the active state of the local clock LCi. That is, verification is performed by taking advantage of the nature of the circuit in that the local clock LCi will eventually be recovered to the active state if the local clock LCi becomes the inactive state (state of stopping the clock) once. The same reference numerals refer to the same constituent elements as those shown in FIGS. 4 , 8 , and 18 , and description thereof is omitted.

FIG. 26 is a functional diagram of the fourth configuration of the clock gating analyzing apparatus 100 . The clock gating analyzing apparatus 100 of the fourth configuration is includes the next-state function calculating unit 801 , the state table generating unit 802 , the CG-state-transition-graph generating unit 1801 , and a state transition extracting unit 2600 . The functions of the units 801 , 802 , 1801 , and 2600 can be realized by executing, by the CPU, relevant programs stored in the memory.

The output data from the units 801 , 802 , 1801 , and 2600 are stored in the memory. Functional constituent elements at the destinations of connections indicated by arrows shown in FIG. 26 read, from the memory, the output data from functional constituent elements at the sources of connections and the CPU executes the programs related to the functions.

The state transition extracting unit 2600 extracts, from the CG state transition graph G 2 created by the CG-state-transition-graph generating unit 1801 , a state transition having the local clock LCi that has not recovered from the inactive state to the active state.

Specifically, it is determined whether the state transitions in the CG state transition graph include a state transition having a local clock LCi that is recovered from the inactive state (LCi=0) to the active state (LCi=1). That is, it is determined whether a state transition from LCi=0 to LCi=1 exists on the CG state transition graph. The local clock LCi determined to be unrecoverable is extracted as an unrecoverable state transition.

For example, in FIG. 19 , with regard to the local clock LC 1 , for example, although the node M 1 has the local clock LC 1 =0, since state transitions exist to the nodes M 2 to M 4 which have LC 1 =1, a state transition can be performed that enables recovery from 0 to 1. Therefore, the local clock LC 1 is a recoverable local clock.

A fourth clock gating analyzing process is a process for the fourth configuration shown in FIG. 26 . FIG. 27 is a flowchart of the fourth clock gating analyzing process of the clock gating analyzing apparatus 100 .

First, the next-state function calculating unit 801 calculates the next-state function (step S 2701 ), and the state table generating unit 802 generates the state table T 2 (step S 2702 ). The CG-state-transition-graph generating unit 1801 generates the CG state transition graph G 2 (step S 2703 ).

The index i is set to i=1 and the clock gate count is set to n (step S 2704 ). It is then determined whether the CG state transition graph G 2 includes a state transition in which the local clock LCi has changed from 0 to 1 (step S 2705 ).

For a local clock LCI, if there is no state transition in which the local clock LCi has changed from 0 to 1 (step S 2705 : NO), the local clock LCi is added to a unrecoverable group SL (step S 2706 ). On the other hand, if there is a state transition in which the local clock LCi has changed from 0 to 1 (step S 2705 : YES), the process proceeds to step S 2707 .

At step S 2707 , the index i is incremented by one (step S 2707 ) and it is determined whether i>n is satisfied (step S 2708 ). If i>n is not satisfied (step S 2708 : NO), the process proceeds to step S 2705 . On the other hand, if i>n is satisfied (step S 2708 : YES), a series of processes is terminated.

According to the fourth configuration and the fourth clock gating analyzing process, reach-ability analysis of the CG state transition graph G 2 can be performed to automatically verify the presence of error, in which the inactive state of the local clock LCi cannot be recovered to the active state. This enables bugs of a particular clock gate function to be completely detected without oversight.

According to a fifth configuration, the CG all-state group S generated by the first configuration shown in FIG. 4 is used to generate an error-state candidate of the clock gate CGi.

The error-state is a state when the active state (state of supplying the clock) exists even though the local clock LCi may be turned to the inactive state (state of stopping the clock). In other words, this is a state of supplying the local clock LCi to the FFs of the FF group Ai even though the supply is not required, i.e., a state of failing to perform the clock gating. The same reference numerals refer to the same constituent elements as those shown in FIGS. 4 , 8 , and 18 , and description thereof is omitted.

FIG. 28 is a functional diagram of the fifth configuration of the clock gating analyzing apparatus 100 . The clock gating analyzing apparatus 100 according the fifth configuration includes the simulation executing unit 701 , a converting unit 2801 , an error-state candidate group generating unit 2802 , a determining unit 2803 , and a deleting unit 2804 . The function of the units 701 and 2801 to 2804 can be realized by executing, by the CPU, relevant programs stored in the memory.

The output data from the units 701 and 2801 to 2804 are stored in the memory. Functional constituent elements at the destinations of connections indicated by arrows shown in FIG. 28 , read from the memory, the output data from functional constituent elements at the sources of connections and the CPU executes programs related to the functions.

The converting unit 2801 converts an arbitrary CG state in the CG all-state group S into a CG state having the clock gate CGi changed from the active state to the inactive state. The error-state candidate group generating unit 2802 generates, based on the converted CG state, an error-state candidate mi related to the local clock LCi.

An example of generation of the error-state candidate by the converting unit 2801 and the error-state candidate group generating unit 2802 is described. FIG. 29 is a schematic of an example of generation of the error-state candidate by the converting unit 2801 and the error-state candidate group generating unit 2802 . FIG. 29 shows an example of generation of an error-state candidate m 1 in the case of i=1, i.e., when the local clock LCi is LC 1 .

(1) First, the CG states having the local clock LC 1 =1 are obtained from among the CG states in the CG all-state group S, and the value of LC 1 is converted from 1 to 0, resulting in conversion from {101} to {001}, from {110} to {010}, and from {111} to {011}. (2) The converted CG state identical to the unconverted CG state is deleted. Since {011} after the conversion is also included in the original CG all-state group S and is not in the error-state, {011} is deleted. (3) Finally, the remaining CG states after (2) are restored to the CG state before the conversion. As a result, {001} is restored to {101}, and {010} is restored to {110}.

The remaining CG states {101} and {110} after the conversion are generated as the error-state candidates m 1 . Such a process is executed for the local clocks LC 1 to LCn to generate an error-state candidate group SM. The error-state candidate mi is an element within the error-state candidate group SM and is an element having the CG state not included in the CG all-state group S when the state of LCi is changed from 1 to 0. This enables generation of the CG state that cannot accept a state of not performing the clock gating of the FFs as the CG state of the circuit 200 .

The determining unit 2803 determines whether the error-state candidate mi in the error-state candidate group SM is identical to the CG state acquired from the simulation result of the simulation executing unit 701 (hereinafter, a “particular CG state 2800 ”). It is also determined from the simulation result whether values of the FFs in the FF group Ai of the local clock LCi are changed at the time of the particular CG state 2800 .

The deleting unit 2804 deletes the particular CG state 2800 from among the error-state candidates mi. Specifically, if the error-state candidate mi is identical to the particular CG state 2800 and the values of the FFs in the FF group Ai of the local clock LCi are changed, the clock gate CGi is in the active state. Therefore, such a particular CG state 2800 is deleted from the error-state candidates mi. This can narrow down the error-state candidates mi.

A fifth clock gating analyzing process is a process for the fifth configuration shown in FIG. 28 . FIG. 30 is a flowchart of the fifth clock gating analyzing process of the clock gating analyzing apparatus.

The index i is set to i=1 and the CG detection count is set to n (step S 3001 ). The converting unit 2801 converts the local clock LCi of the CG states in the CG all-state group S from 1 to 0 (step S 3002 ). The converted CG states identical to the unconverted CG states are deleted (step S 3003 ). The remaining converted CG states are restored to the CG state before the conversion to generate the error-state candidates mi, which are added to the error-state candidate group SM (step S 3004 ).

The index i is incremented by one (step S 3005 ) and it is determined whether i>n is satisfied (step S 3006 ). If i>n is not satisfied (step S 3006 : NO), the process returns to step S 3002 . If i>n is satisfied (step S 3006 : YES), a series of processes are terminated. This enables the simple conversion process to solely and automatically generate the error-state candidates mi.

FIG. 31 is a flowchart of a process for narrowing down the error-state candidates mi. First, the input of the input pattern P is waited for (step S 3101 : NO), and when the input pattern P is input (step S 3101 : YES), the simulation executing unit 701 executes a circuit simulation (step S 3102 ). As a result, the particular CG state 2800 is obtained.

The index i is set to i=1 (step S 3103 ), and the determining unit 2803 determines whether the error-state candidates mi include the particular CG state 2800 (step S 3104 ). If the particular CG state 2800 is not included (step S 3104 : NO), the process proceeds to step S 3107 .

If the particular CG state 2800 is included (step S 3104 : YES), it is determined whether values of the FFs driven by the local clock LCi, i.e., FFs in the FF group Ai are changed by the particular CG state 2800 (step S 3105 ). If the values of the FFs are not changed (step S 3105 : NO), the process proceeds to step S 3107 . If the values of the FFs are changed (step S 3105 : YES), the particular CG state 2800 is deleted from among the error-state candidate mi (step S 3106 ).

At step S 3107 , i is incremented by one (step S 3107 ) and it is determined whether i>n is satisfied (step S 3108 ). If i>n is not satisfied (step S 3108 : NO), the process returns to step S 3104 . On the other hand, if i>n is satisfied (step S 3108 : YES), a series of processes are terminated. As a result, the error-state candidates mi can effectively be narrowed down from the simulation result.

According to the fifth configuration and the fifth clock gating analyzing process of the clock gating analyzing apparatus 100 , the error-state candidate mi can be obtained which fails to perform the clock gating for the CG state that cannot be accepted as the CG state of the circuit 200 .

If the values of the FFs in the FF group of the local clock LCi are not changed by a particular CG clock gating state from the simulation result, the particular CG state 2800 can be left among the error-state candidates mi as a candidate of improper the clock gating (state of not stopping the clock even though the clock can be stopped). Therefore, improper clock gating, which causes increased power consumption of the circuit 200 , can be reduced.

As described above, the clock gating analyzing apparatus, the clock gating analyzing method, and the clock gating analyzing program can alleviate the design burden of designers, improve credibility of a circuit subject to analysis, and achieve low power consumption.

The clock gating analyzing method described in the present embodiment can be implemented using a computer, such as personal computer and a work station, to execute a program that is prepared in advance. The program is recorded on a computer-readable medium such as a hard disk, flexible disk, compact disk read-only memory (CD-ROM), magneto optical disk (MO), and digital versatile disk (DVD) and is read from the recording medium by the computer for execution. The program may be a transmission medium distributable through a network such as the Internet.

Although the invention has been described with respect to a specific embodiment for a complete and clear disclosure, the appended claims are not to be thus limited but are to be construed as embodying all modifications and alternative constructions that may occur to one skilled in the art which fairly fall within the basic teaching herein set forth.