Behavioral level observability analysis and its applications

• US 6,728,945 B1
• Filed: 02/26/2001
• Issued: 04/27/2004
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Wang, Qi
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): Levin, Naum
• Application Number:
  US09/793,309
• Time in Patent Office: 1,156 Days
• Field of Search: 716/1, 716/3-6, 716/7, 716/18
• US Class Current: 716/103
• CPC Class Codes: G06F 2119/06 Power analysis or power optimisation
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

A method and system are provided for computing behavioral level observabilities of a digital system. In one example, a logic network is provided for performing an observability analysis at the behavioral level of a digital system. The logic network includes logic objects configured to emulate behavioral observabilities computed from a control data flow graph (CDFG), wherein the logic objects include at least one of: first logic objects configured to compute a token observable condition (TOC) of an edge of the CDFG; and second logic objects configured to compute a node observable condition (NOC) of a node of the CDFG. A logic optimization is used to optimize the logic network to obtain an optimized logic network of the behavioral observabilities.

Claims

1. A method of performing an observability analysis at the behavioral level of a digital system, the method comprising:

computing a token observable condition of an edge of a control data flow graph (CDFG), wherein the token observable condition is used to identify a redundant edge of the control data flow graph (CDFG); and

computing a node observable condition of a node of the CDFG, wherein the node observable condition is used to identify a redundant node of the control data flow graph (CDFG).

2. The method of claim 1, wherein each step of computing comprises:

traversing the control data flow graph from output nodes to input nodes; and

applying appropriate Boolean algebra operations to the traversed control data flow graph (CDFG).

3. The method of claim 1, wherein the node is an output node having a single input port, and wherein the edge is connected to the single input port of the node, and wherein the token observable condition for the edge is 1, and wherein the node observable condition for the output node is 1.

4. The method of claim 1, wherein the node is an operation node having at least one input port and at least one output port.

5. The method of claim 1, further comprising computing an observability of the node of the control data flow graph, wherein the node is a branch node having an input control port and an input data port and at least one output data port.

6. The method of claim 1, further comprising computing an observability of the node of the control data flow graph, wherein the node is a merge node having an input control port and an output data port and at least one input data port.

7. The method of claim 4, wherein a construct node is the same as an operation node.

8. A method of computing behavioral level observabilities of a digital system, the method comprising:

constructing a logic network based on a control data flow graph (CDFG) of the digital system, wherein the logic network is constructed to compute the behavioral level observabilities;

optimizing the logic network using a logic optimization technique to obtain an optimized Boolean function of the behavioral level observabilities; and

traversing the optimized Boolean function to obtain the behavioral level observabilities, wherein the behavior-level observabilities are used to identify redundant edges and redundant nodes of the control data flow graph (CDFG).

9. The method of claim 8, wherein the logic optimization technique includes algebraic transformations.

10. The method of claim 8, wherein the behavioral level observabilities are used in conjunction with a front-end register transfer level (RTL) synthesis tool.

11. The method of claim 10, wherein the behavioral level observabilities are used to optimize the digital system at the gate-level.

12. The method of claim 8, wherein the behavioral level observabilities are used to design the digital system to be more efficient with the use of power.

13. The method of claim 8, further comprising removing redundant edges and redundant nodes from the control data flow graph (CDFG) without changing the functionality of the CDFG.

14. A computer-readable medium carrying one or more sequences of one or more instructions for performing an observability analysis at the behavioral level of a digital system, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of:

computing a token observable condition of an edge of a control data flow graph (CDFG), wherein the token observable condition is used to identify a redundant edge of the control data flow graph (CDFG); and

computing a node observable condition of a node of the CDFG, wherein the node observable condition is used to identify a redundant node of the control data flow graph (CDFG).

15. The computer-readable medium as recited in claim 14, wherein each step of computing further causes the processor to carry out the steps of:

traversing the control data flow graph from output nodes to input nodes; and

applying appropriate Boolean algebra operations to the traversed control data flow graph (CDFG).

16. The computer-readable medium as recited in claim 14, wherein the node is an output node having a single input port, and wherein the edge is connected to the single input port of the node, and wherein the token observable condition for the edge is 1, and wherein the node observable condition for the output node is 1.

17. The computer-readable medium as recited in claim 14, wherein the node is an operation node having at least one input port and at least one output port.

18. The computer-readable medium as recited in claim 14, wherein the instructions further cause the processor to carry out the step of computing an input control edge of the control data flow graph, wherein the node is a branch node having an input control port and an input data port and at least one output data port.

19. The computer-readable medium as recited in claim 14, wherein the instructions further cause the processor to carry out the step of computing an input control edge of the control data flow graph, wherein the node is a merge node having an input control port and an output data port and at least one input data port.

20. The computer-readable medium as recited in claim 14, wherein a construct node is the same as an operation node.

21. A logic network for performing an observability analysis at the behavioral level of a digital system, the logic network comprising:

logic objects configured to emulate behavioral observabilities computed from a control data flow graph (CDFG), wherein the logic objects include at least one of;

first logic objects configured to compute a token observable condition (TOC) of an edge of the CDFG, wherein the token observable condition is used to identify a redundant edge of the control data flow graph (CDFG); and

second logic objects configured to compute a node observable condition (NOC) of a node of the CDFG, wherein the node observable condition is used to identify a redundant node of the control data flow graph (CDFG).

22. The logic network of claim 21, wherein the portion of the control data flow graph (CDFG) includes at least one of:

an output node;

an operation node;

a branch node;

a merge node;

a data edge; and

a control edge.