Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-08-16
2003-06-03
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06574787
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention pertains to the field of logic synthesis and, in particular, to method and apparatus for converting a hardware description language (“HDL”) model of an electronic logic system to a netlist (wherein a netlist is a data structure representation of the electronic logic system that comprises a set of modules, each of which modules comprises a data structure that specifies sub-components and their interconnection).
BACKGROUND OF THE INVENTION
Automated design of application specific integrated circuits (“ASIC”) as well as programming of either programmable. logic devices or programmable gate arrays requires specification of a logic circuit by a designer. A hardware description language (“HDL”) provides the designer with a mechanism for describing the operation of the desired logic circuit in a technology independent manner.
FIG. 1
shows a flow chart of a prior art method of logic synthesis that starts with a designer-specified HDL model of an electronic logic system and generates a Gate-Level netlist. As shown in
FIG. 1
, in step
100
, a designer inputs a model of an electronic logic system having a desired logic functionality in the form of a set of files (HDL
10
) that describe the model in a prior art HDL. As further shown in
FIG. 1
, in step
110
, HDL
10
is parsed by a lexical analyzer and parser (lex,yacc parser
120
). During parsing step
110
, lex,yacc parser
120
calls routines to populate parse tree
130
(a database that is commonly referred to in the art as a parse tree). As still further shown in
FIG. 1
, in step
140
, parse tree
130
is traversed to generate control-flow-graph
150
(CFG
150
), also known in the art as a control-data-flow-graph. As yet still further shown in
FIG. 1
, elaboration step
160
is performed to traverse CFG
150
and populate Gate-Level Netlist
170
. Gate-Level Netlist
170
is an independent and complete representation of HDL
10
. It is well known to those of ordinary skill in the art how to traverse Gate-Level Netlist
170
to create a logic netlist as output.
As is well known to those of ordinary skill in the art, CFG
150
is an independent representation of the logic system (using edge and control) that is not dependent on parse tree
130
or Gate-Level Netlist
170
.
In accordance with prior art logic synthesis systems, the result of elaboration step
160
is a data base, i.e., Gate-Level Netlist
170
, in which each bit of a bussed net and each elaborated gate is represented by a separate data base object. Such a database is called “bit-oriented.” Optionally, additional objects in Gate-Level Netlist
170
track groups of bits to indicate their association as a bus object (as indicated in the HDL model). These objects are optional because the bit-oriented representation of the HDL model, while not concise, is complete. This is illustrated in
FIG. 2
which shows, in schematic form, a bussed net represented in a prior art logic netlist. As shown in
FIG. 2
, bussed net
300
is represented by a multiplicity of individual net objects
320
1
, . . . ,
320
n
and a separate bus net object
310
that associates these individual net objects into a bus.
Using such prior art netlists, it is easy to represent configurations in which bits of a bussed net behave differently because each net bit is broken into a separate object in the data base. However, due to the large number of such objects, such data bases require a large amount of computer memory. Additionally, it takes large computer runtimes to perform the prior art logic synthesis.
As one can readily appreciate from the above, a need exists in the art for a method and apparatus for logic synthesis that reduces use of computer memory and reduces computer runtime.
SUMMARY OF THE INVENTION
Embodiments of the present invention advantageously satisfy the above-identified need in the art and provide a method and apparatus for logic synthesis that reduces use of computer memory and reduces computer runtime.
In particular, an embodiment of the present invention is a method for logic synthesis which comprises the steps of: (a) analyzing an HDL model to develop a parse tree and (b) elaborating the parse tree to create a word-oriented netlist.
Aspects of the present invention include, without limitation: (a) an inventive Gate-Level netlist comprising word-oriented data objects (i.e., vector gate objects); (b) an inventive Gate Level netlist comprising novel connection objects; (c) a novel word-oriented (i.e., vector) elaboration method to create the inventive Gate-Level netlist; and (d) a novel method to infer complex components (for example, latches, flip-flops, multiplexors, and tristates) from a Gate-Level netlist (including the inventive Gate-Level netlist), without direction from the designer other than that contained within the designer-created HDL model.
In one embodiment of the present invention, novel connection objects “sit between” pin and net objects to create efficiency in connections represented in “G” data base. Examples of such novel connection objects include: (a) full conn; (b) bit-select conn; (c) part-select conn; (d) concat conn; (e) const conn; and (f) float conn. In particular, the novel const conn object enables efficient representation of constant logic values, for example, logic0 and logic1; the novel float conn object enables efficient representation of an undriven or floating output. Further, in accordance with the present invention, a single const conn object or a single float conn object can represent an arbitrary bit-width const or float connection and, a const conn object and a float conn object can be included in a concat conn object.
In further aspects of the present invention, the inventive elaboration method utilizes the following inventive data base constructs: (a) a chunk; (b) a cache; (c) a cache item; and (d) an update item. In addition, the inventive elaboration method comprises a novel method for dealing with exceptions.
In another embodiment of the present invention, the inventive elaboration method comprises the steps of: (a) preprocessing a parse tree; (b) recursively traversing top-level statement objects in parse tree process objects; and (c) connecting net objects in the inventive word-oriented “G” data base. In a further embodiment of the inventive elaboration method, step (b) of recursively traversing the top-level statement objects comprises the steps of: (i) setting “parent” and “previous” pointers of a statement object; (ii) creating a net object and a driver object for assignment statement objects; (iii) recursing into each sub-statement object of a statement object; and (iv) propagating cache items upwards to the statement object's “parent”. In a still further embodiment of the inventive elaboration method, step of (ii) of creating a net object and a driver object for assignment statement objects comprises, for an assignment statement object, the steps of (1) creating a net object in the “G” data base which has a bit-width equal to the width of the left-hand-side of the assignment statement object; (2) creating an update object in the “V” data base (the parse tree); (3) updating the cache item of the assignment statement object with the contents of the update object to provide an updated chunk list; (4) creating a “full-conn” object in the “G” data base to the net object created in the “G” data base in the first step; (5) carrying out a “makeConn” method for the right-hand side of the assignment statement object to create conn objects; and (6) creating a buffer gate object in “G” data base with an output of the buffer object being set to a full-conn object created in the fourth step and an input of the buffer gate object being set to a conn object created in the fifth step. In a yet still further embodiment of the inventive elaboration method, step (iii) of connecting net objects in the inventive word-oriented “G” data base comprises the steps of: (1) finding a net object corresponding to the cache item's HDL identifier; (2) creating a conn object to drive the net
Dinh Paul
Kwok Edward C.
MacPherson Kwok & Chen & Heid LLP
Sequence Design, Inc.
Siek Vuthe
LandOfFree
Method and apparatus for logic synthesis (word oriented... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for logic synthesis (word oriented..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for logic synthesis (word oriented... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3152499