Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system
Reexamination Certificate
2001-02-09
2004-10-05
Phan, Thai (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
C703S017000
Reexamination Certificate
active
06801884
ABSTRACT:
TECHNICAL FIELD
This application is related in general to VLSI CAD design, and in specific to an apparatus and method for traversing a design that uses a lightweight occurrence model.
BACKGROUND
Prior computer aided design (CAD) systems represent designs in a hierarchical connectivity form that provides design information to system designers with different levels of abstraction. An example of such a schematic configuration
100
is shown in
FIG. 1
, which depicts the relationships between a cell
101
, a port
102
, a net
103
, an instance
104
, and a port instance
105
. Such a configuration is known as a folded connectivity model. The cell block
101
describes a device or structure of the system, e.g., a full adder. A cell contains collections of instances of other cells, nets (which are wires) and the external interfaces to the cell (ports). The net block
103
describes the wires that make up the internal connections within the cell block. The port block
102
describes the interface to the cell and provides the connection points for the nets (wires) to carry (“Co”) signals into and out of the cell block's logic.
As stated above, a cell block provides the definition of a device or structure. Once a cell has been defined, it can then be instantiated (wherein an instance block
104
is created of that cell), so that it may be used in other cell definitions. In this way, a design hierarchy can be created. The instance block describes the devices or structures used to form the functionality of a cell, e.g., for a two bit adder: two full adder cell instances are created. Just as an instance records the instantiation (or use of) a cell block, the port instance block
105
records the instantiation of the ports on the cell. The port instances allow us to record the specific nets that are connected to a given instance.
The hierarchical nature of the information stored in the folded connectivity model is shown by way of example only in
FIGS. 2A-2C
.
FIG. 2A
depicts the highest level of hierarchy, that is cell block
200
, which is a two bit adder. The two bit adder block has 8 ports (the inputs A
1
, B
1
, A
0
, B
0
, Cin; and the outputs Cout, S
1
, and S
0
). It contains the nets that are connected to these ports (A
1
, B
1
, A
0
, B
0
, Cin, Cout, S
1
, and S
0
), in addition to one internal net (Co) which is not connected to a port on the cell boundary, but is none-the-less a net contained within the two bit adder cell definition. Finally, the two bit adder contains two instances, FA
0
block
202
and FA
1
block
203
, each of which are instances of a full adder (or a one-bit adder).
FIG. 2B
depicts the next lower level of the hierarchy of the system, showing the cell definition for the full adder. Note that the instances FA
0
(block
202
) and FA
1
(block
203
) in the top level are described by a cell at the next lower level of hierarchy. The full adder block
201
has 5 ports (input ports A, B, and Cin; the output ports S and Co). It also contains 11 nets (ported nets A, B, Cin, Co, and S; internal nets Co sig_
1
, sig_
2
, sig_
3
, sig_
4
, and sig_
5
), and 8 instances (2 instances of an inverter, I
1
, and I
2
; 2 instances of a 2-input NOR gate, NO
1
, NO
2
; 2 instances of a 2-input XOR gate, XO
1
and XO
2
; and 2 instances of a 2-input NAND gate, NA
1
and NA
2
). Finally,
FIG. 2C
depicts one of the cells at the lowest level of hierarchy, the 2-input NAND gate. Note that there are 3 other cells at this same level of hierarchy that are not depicted (namely the inverter, the 2-input NOR gate, and the 2-input XOR gate). Additional levels of hierarchy may exist, e.g., one or more levels higher than FIG.
2
A.
A folded connectivity model provides a memory efficient representation of source VLSI design data as seen by the VLSI designer. A fundamental limitation of the folded connectivity model, however, is its ability to represent a truly unique addressable object for each object created across the many levels of design hierarchy. Although this is not an issue for many existing CAD tools, it is becoming more of an issue for the next generation analysis and design tools which need to analyze design entities that span the hierarchy. The design of
FIGS. 2A-2C
can be walked through to illustrate the fundamental limitation of a folded connectivity model. In these FIGURES, the top level cell
FIG. 2A
contains two instances of the cell “full_adder”, FA
0
and FA
1
. The cell “full_adder” contains two instances of the block “nand_
2
”, NA
1
and NA
2
. This information is recorded in the folded connectivity model as shown in FIG.
4
. Notice that, in this diagram, there is only one cell
406
for the NA
1
and NA
2
instances (blocks
415
and
405
respectively). But, when the same design in the form shown in
FIG. 3
is viewed, there are in reality, two different occurrences of the instance NA
1
(FA
0
/NA
1
and FA
1
/NA
1
). The same is true for the instance NA
2
(and, as a result, the nets contained within the describing cells for each of these instances). The folded connectivity model only records that a single instance of cell “nand_
2
” named NA
1
is an element of the cell “full_adder”.
A common technique used to avoid this problem is to perform a ‘flattening’ process. The process of flattening a hierarchical design removes all intermediate levels of hierarchy, so only primitive elements exist. There are two primary problems with flattening. First, flattening uses a great deal of computer memory. With today's microprocessor designs, it is often impossible to flatten the entire hierarchy. The second problem is that flattening is a one-way process. Once flattened, it is impractical to relate flattened circuit elements back to a hierarchical view.
For these reasons, the occurrence (or unfolded) model representation is becoming a more important representation for many of today's CAD tools. In a typical occurrence model, each and every cell is stored, including those cells that are duplicated, while retaining the notion of the original design hierarchy. The primary advantage of an occurrence model is that it allows tools to obtain the benefits of flattening (being able to see a flattened view of the design and the interconnecting nets that span hierarchy) without losing hierarchical information. In addition, using an occurrence model gives some flexibility to the tool developer, so that they do not have to build a model to represent the entire design, only for those pieces currently being evaluated. As an example, each adder
202
and
203
is stored separately in the model, as well as each second NAND (N
2
) circuit
205
,
208
or each adder, and each N
2
transistor
207
,
209
of N
2
circuit, as shown in FIG.
3
.
FIG. 3
depicts the multi-level view of the cell of
FIG. 1
with the different levels of the example of
FIGS. 2A-2C
. (Note that for simplicity, the other elements of the circuit, as well as the sub-elements, e.g., I
1
, I
2
, XO
1
, XO
2
, NO
1
, and NO
2
are not shown.) However, modern IC circuits, e.g., processors, comprise millions of instances. Thus, the size of the model quickly becomes large as the lower levels are added to the model. Current computer systems do not have adequate memory to store the complete occurrence model. However, the lower levels are becoming more important to designers. The presence of the lower levels in the model allows for more detailed analysis of the system, e.g., for parasitic losses from the net connections, which thereby improves the speed and efficiency of the system.
FIG. 4
depicts a partial example of the in-memory representation of the folded connectivity model for the schematic design described in FIG.
2
. In this model, only one copy of lower level instances are maintained. Pointers
409
-
414
are used to associate an upper level cell with lower level instances of that cell.
FIG. 4
models the same example as shown in
FIGS. 2A-2C
and
3
. This model does not store specific instance and net occurrence information. Instead, each instance of a cell points to a generic higher lev
Ferreri Richard Anthony
Wang Lanzhong
Hewlett--Packard Development Company, L.P.
Phan Thai
LandOfFree
Method and apparatus for traversing net connectivity through... 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 traversing net connectivity through..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for traversing net connectivity through... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3308126