Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-05-28
2002-06-11
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06405345
ABSTRACT:
FIELD OF INVENTION
This invention pertains to the field of electronic design automation. More specifically, this invention pertains to the operation of a technology mapping tool.
BACKGROUND OF THE INVENTION
Modem logic circuits are so complex that designers generally require computer-based techniques to aid in their design. During the design of a complex logic circuit, a process called “Technology Mapping” is employed to transform an abstract representation of a design into a technology-dependent netlist, which is a representation of the design using cells of a technology-specific target library. The abstract representation of the design is generally made up of combinatorial blocks separated by sequential blocks. A combinatorial block represents a multiple-input Boolean equation in which the output is a logical combination of the input signals, and is often described by Directed Acyclic-Graphs (DAGs). A sequential block is one that maintains a state representation, so that the outputs are not simply a logical combination of the inputs.
The technology mapping can be carried out in a series of steps. In a first step, the technology mapper partitions a DAG into a set of interconnected logic cones and buffer trees. A logic cone is a set of fanout free interconnected 2-input AND nodes and 2-input OR nodes delimited by multi-fanout nodes, inverters, and buffers. A buffer tree is a set of interconnected inverters and buffers (sometimes reduced to a simple multi-fanout wire) delimited by 2-input AND nodes, 2-input OR nodes, and by DAG terminals. In
FIG. 1
, a DAG is illustrated as having been partitioned into three logic cones and eight buffer trees. After the DAG has been partitioned, the logic cones and the buffer trees are sorted in a forward Breadth First Search (BFS) order.
The logic cones are tiled one by one, according to the BFS sorted order. During the tiling step, the inputs of each logic cone are assumed to be available both in direct and inverted form. Also, the tiling is attempted for each logic cone in both direct and inverted form, with the best tiling being kept. At each node of a logic cone, the technology mapper iterates through all of the available library cells to determine whether each cell can cover the current node. This involves determining whether a covering is possible in either direct. or inverted form. If so, a correspondence is established between the current cell input terminals and the input nodes driving that cell. The polarity of the terminals is defined as well. When the technology mapper reaches the root node of a logic cone (whose output is the logic cone output), it determines the best cover for the whole logic cone. That selection induces a polarity on the logic cone, as well as on all the logic cone input terminals.
The buffer trees are then buffered one by one, based on: (i) the initial polarity of the logic cone input terminals driven by the buffer tree, (ii) the tiler-produced polarity of the logic cone input terminals driven by the buffer tree, and (iii) the tiler-produced polarity of the logic cone output terminals driving the buffer tree. The results of the tiling and buffering replace the abstract representation of the combinatorial block in the design.
In the tiling step above, the technology mapper visits nodes within a logic cone in a BFS order from the inputs to the output. At each visited node, in a first phase, the technology mapper invokes a matcher with a given matchable library cell. The matcher produces a list of matches, each of which is composed of the following information:
TABLE 1
Contents of a Match
the matched library cell
the polarity of the match of the appropriate node output connector
the correspondence between the child nodes and the gate input
connectors
the polarity of each of the child nodes
For example, in the case of
FIG. 2
a
, the matcher invoked for node n would produce a match including information such as that presented in
FIG. 2
b
. A child node is one which has an output connected to an input of the current node.
After the production of the list of matches is completed, potential node covers are determined. A node cover is recursively defined as a match plus one cover for each child node of the match. A node cover can be seen as one set of interconnected components which are necessary to cover the functionality of that node from the logic cone input terminals. A node cover includes the following information:
TABLE 2
Contents of a Cover
a match for the node
the performance of the node cover
the polarity of the node cover
node covers for each of the child nodes of the match
As used herein, the performance of a cover includes the area of the cover and the slack of the cover. The slack of the cover is automatically deduced by comparing the covered node rising/falling arrival times with the covered node budgeted required times. In some cases the potential of creating physical problems (i.e. routing problems) is also included in performance. A logic cone root node cover may be called a logic cone cover, because the full cover of the logic cone is revealed by recursively visiting the child node covers of that cover.
The tiling process generates many potential covers and it is a difficult task to select the best of these. The task is difficult in part because covers are difficult to compare and to trim. For example, it is not clear whether a smaller and slower cover should be preferred to a bigger and faster cover. However, there does exist an inferiority relationship between some covers which allows for an easy comparison of these covers. A cover is considered to be inferior to another cover if it is worse (i.e. bigger, worse slack, more difficult to place and route) than the other cover in at least one aspect and is not better than the other cover in any other aspect. Inferior covers can generally be immediately rejected in the tiling process.
A child node cover is said to be Logic Design Rule (LDR) compatible with a node cover if the connection of the child cover to the node cover does not create any LDR violation.
Two covers are considered to be timing equivalent if the difference between their slacks is smaller than a certain threshold &tgr;. The physical concept behind the &tgr; parameter is the fact that below a certain threshold, the timing that is measured within a timing engine is not meaningful. Note that the direct impact of the &tgr; parameter is that non-inferior covers can be considered as inferior. For instance, if cover a produces a slack &tgr;/2 better than cover b and if cover b is smaller than cover a, then cover a will be considered inferior to cover b, and will be rejected. This rejection is meaningful up to a certain threshold, because selecting smaller cover will decrease the final size of the design and will thus decrease the average wiring capacitance of the design.
In a second phase, the technology mapper associates covers with the matches produced by the matcher and evaluates the performance of these covers. The performance of a cover which is exclusively driven by logic cone input terminals can be computed as follows:
the area is the area of the matched cell; and
the slack is computed as the difference between the timing engine budgeted required time and the timing engine computed arrival time on the output node of the matched cell.
While producing the different covers, the technology mapper compares the performance of the covers, eliminating rejectable covers, such as covers which do not respect a Logic Design Rule, covers which cover gates placed very far away from each other, and inferior covers.
The performance of a cover which is not exclusively driven by logic cone input terminals is computed as follows:
the area is the sum of the matched cell area plus the areas of the cover child node covers; and
the slack is computed as the difference between the timing engine budgeted required time and the timing engine computed arrival time on the output node of the matched cell.
Once the logic cone output node has been visited, and once the cover performance values are known, the technolo
Cadence Design Systems Inc.
Lyon & Lyon LLP
Siek Vuthe
LandOfFree
Updating placement during technology mapping does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Updating placement during technology mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Updating placement during technology mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2913860