Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-02-26
2004-04-27
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S116000, C716S030000
Reexamination Certificate
active
06728945
ABSTRACT:
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to digital system design and, more particularly, to techniques for analyzing behavior and optimizing performance of digital systems, such as integrated circuits.
2. Discussion of Background
Designing of digital hardware involves a multi-leveled synthesis process. At a higher level, the behavior of the digital hardware may be written in a hardware behavioral description language, such as Verilog or Very High Speed Integrated Circuit Hardware Description Language (VHDL). This description is parsed into a control data flow graph (CDFG). The CDFG is synthesized into a register transfer level (RTL) description. At the logic level, logic circuitry is synthesized from the RTL description. At a lower architecture level, physical layouts are synthesized from the logic circuitry.
Observability analysis in logic circuits has been widely used in logic synthesis, test generation, and many other Electronic Computer-Aided Design (ECAD) problems. For more information on observability analysis, see De Micheli, Giovanni, “Synthesis and Optimization of Digital Circuits,” McGraw-Hill, Inc., 1994.
Observability analysis has traditionally been performed at the lower levels of the synthesis process. Unfortunately, performing an analysis, for example, at the logic level oftentimes makes it difficult to make necessary changes to the circuit design. The logic level relates to the generation of performance-optimal circuit representations from models in hardware description languages.
A general rule of thumb is that the lower the level, the more difficult it is to make changes to the digital system design. For example, in a synthesis process, architectural level decisions include the following: determining which type of multiplier to be used; determining whether the calculation is to be implemented serially or in parallel. These early stage decisions will have a more significant impact on the final implementation of a design. Then after the architectural level decisions are made, the design is then mapped to a network of logic gates. At the logic level, the freedom of design is substantially less than that at the architectural level. Thus, changes made at the lower levels, such as the logic level, are increasingly time-consuming and costly.
SUMMARY OF THE INVENTION
It has been recognized that what is needed is a technique for analyzing observabilities of digital systems at a higher level of the synthesis process. Broadly speaking, the present invention fills these needs by providing a method and system for computing behavioral level observabilities of an digital system. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, or a method. Several inventive embodiments of the present invention are described below.
In one embodiment, a method is provided for performing an observability analysis at the behavioral level of a digital system. The method comprises computing a token observable condition of an edge of a control data flow graph (CDFG); and computing a node observable condition of a node of the CDFG. 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 CDFG.
In another embodiment, a logic network is provided for performing an observability analysis at the behavioral level of a digital system. The logic network comprises 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.
Advantageously, in synthesis of digital systems such as integrated circuits, the more important decisions are made at the behavioral level. Moreover, it has been found that much of the information easily available at the behavioral level may become very difficult to retrieve at lower levels. Thus, the proposed behavioral level observability analysis provides valuable information for optimization in later design cycles.
The value of the present invention is exemplified and demonstrated by two applications, one is for power optimization and the other is for behavioral level redundancy removal. Also provided is an efficient, practical approach to computing the token observable conditions (TOC's) and node observable conditions (NOC's).
The invention encompasses other embodiments of a method, an apparatus, and a computer-readable medium, which are configured as set forth above and with other features and alternatives.
REFERENCES:
patent: 5502645 (1996-03-01), Guerra et al.
patent: 5774370 (1998-06-01), Giomi
patent: 6192504 (2001-02-01), Pfluger et al.
Qi Wang, Lei Wei “Graph-based iterative decoding algorithms for parity-concatenated trellis codes”, IEEE translations on information theory, vol. 47, No. 3, Mar. 2001.*
Bryant, R.E. (1986) “Graph-Based Algorithms for Boolean Function Manipulation,”IEEE Transactions on Computers, C-35(8):677-691.
van Eijndhoven, J., (1991) “The ASCIS Data Flow Graph: Semantics and Textual Format,”Technical Report EUT-Report 91-E-251Eindhoven University of Technology, Eindhoven, Netherlands.
DeMicheli, (1994) “Synthesis and Optimization of Digital Circuits,” McGraw Hill, Inc.
Cadence Design Systems Inc.
Levin Naum
Reed Smith Crosby Heafey LLP
Siek Vuthe
LandOfFree
Behavioral level observability analysis and its applications does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Behavioral level observability analysis and its applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Behavioral level observability analysis and its applications will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3253582