Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-12-20
2003-09-23
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06625799
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention generally relates to technology mapping methods and storage media, and more particularly to a technology mapping method for automatically converting a logic circuit which does not depend on a specific circuit technology into a circuit which uses a specific cell library, and to a computer-readable storage medium which stores a program for causing a computer to carry out a technology mapping process using such a technology mapping method.
When designing a logic circuit, it is necessary to take into consideration various restricting conditions such as the circuit area, delay time and power consumption, in addition to the logic specifications. For this reason, the logic combining process which automatically designs the logic circuit normally employs a method which divides the process into a technology-independent combining process which is independent of the circuit technology and a technology-dependent combining process which is dependent on the circuit technology, and carries out the combining process according to respective partial targets.
The technology-dependent combining process is also called technology mapping, and is carried out when converting a technology-independent logic circuit into an actual circuit. Presently, the popularly used technology mapping employs a technique called a cell based design technique. When realizing a circuit by this cell based design technique, logic element parts which are prepared in advance, that is, cells, are combined to form the logic circuit.
BACKGROUND ART
The technology mapping which is conventionally reduced to practice is based on an algorithm called DAGON proposed in Kurt Keutzer, “DAGON: Technology Binding and Local Optimization”, Proc. 24th ACM/IEEE Design Automation Conference, pp. 341-247, June 1987. This proposed algorithm called DAGON temporarily converts a target circuit which is to be designed into a circuit using basic cells such as 2-input NAND gates and NOT gates, and generates the actual circuit by assigning larger cells with respect to partial circuits which are made up of the NAND gates and the NOT gates.
A description will be given of an example of the design using the DAGON algorithm. First, with respect to each cell of a cell library, patterns made up of one or more 2-input NAND gates and/or one or more NOT gates and describing logical functions are prepared in advance. The decomposition of the cell is not uniquely determined, and various different decomposition patterns are conceivable. For this reason, all of the decomposition patterns are considered for each cell.
FIGS. 1 and 2
are diagrams showing examples of cells of the cell library and decomposition patterns of the cells. In
FIG. 1
, (a) shows a decomposition pattern of a cell NOT, (b) shows a decomposition pattern of a cell NAND
2
, (c) shows a decomposition pattern of a NAND
3
, (d) shows a decomposition pattern of a cell NAND
4
, (e) shows a decomposition pattern of the NAND
4
, (f) shows a decomposition pattern of a cell AOI
21
, (g) shows a decomposition pattern of a cell AOI
22
, and (h) shows a decomposition pattern of a cell AND
2
. In addition, in
FIG. 2
, (a) shows a decomposition pattern of a cell NOR
2
, (b) shows a decomposition pattern of a cell NOR
3
, (c) shows a decomposition pattern of a cell NOR
4
, (d) shows a decomposition pattern of the cell NOR
4
, (e) shows a decomposition pattern of a cell OAI
21
, (f) shows a decomposition pattern of a cell OAI
22
, and (g) shows a decomposition pattern of a cell AOR
2
. In
FIG. 1
, the cell NAND
4
has two kinds of decomposition patterns as shown in (d) and (e). In
FIG. 2
, the cell NOR
4
has two kinds of decomposition patterns as shown in (c) and (d).
If it is assumed for the sake of convenience that a target technology-independent logic circuit which is to be designed is formed by virtual AND gates, OR gates and NOT gates, the AND gate can be realized by use of 2-input NAND gates and NOT gates as shown in FIG.
3
(
a
), and the OR gate can be realized by use of 2-input NAND gates and NOT gates as shown in FIG.
3
(
b
). Accordingly, it is possible to easily convert an initial circuit into a circuit consisting solely of the 2-input NAND gates and the NOR gates. In this case, a plurality of decomposition patterns are conceivable, but only one decomposition pattern is normally considered since it is difficult to consider all of the decomposition patterns.
FIG. 4
shows an example of the initial circuit which is decomposed in the above described manner. With respect to the initial circuit shown in
FIG. 4
, it is possible to assign partial circuits as shown in FIG.
5
. In
FIG. 5
, each partial circuit surrounded by a bold solid line is assigned with respect to one cell. However, such an assignment of the partial circuits with respect to the cells is not uniquely determined, and for example, it is possible to assign partial circuits as shown in
FIG. 6
with respect to the initial circuit shown in FIG.
4
. In
FIG. 6
, each partial circuit surrounded by a bold solid line is assigned with respect to one cell.
When assigning the partial circuits with respect to the cells, the technology mapping process selects a most desirable assignment by taking into consideration the restricting conditions and the target functions such as the circuit area, delay time and power consumption. Accordingly, the technology mapping process requires two stages of processes, namely, a matching process and a covering process. The matching process lists the cells which match the partial circuits of the initial circuit. In addition, the covering process generates the actual circuit by combining the matching cells. In this case, a match refers to a combination of the partial circuit surrounded by the bold solid line and the cell indicated beside the partial circuit in
FIGS. 5 and 6
. In the matching process, all possible matches are listed regardless of whether or not the match is obtained as a result.
With respect to the matching process, an algorithm called graph matching is proposed in R. L. Rudell, “Logic Synthesis For VLSI Design”, PhD Thesis, UCB/ERL M89/49, 1989.
FIG. 7
is a flow chart showing a typical matching process. In
FIG. 7
, a step S
1
decides whether or not a non-tested node exists in the initial circuit, and the process ends if the decision result in the step S
1
is NO. On the other hand, if the decision result in the step S
1
is YES, a step S
2
obtains one node and denotes this node by v. A step S
3
decides whether or not a non-tested pattern exists, and the process returns to the step S
1
if the decision result in the step S
3
is NO. If the decision result in the step S
3
is YES, a step S
4
obtains one pattern and denotes this pattern by p. A step S
5
obtains a match with respect to the pattern p at the node v, and the process returns to the step S
3
. The graph matching referred above is used in the process of the step S
5
.
Accordingly, when testing the matching of all of the patterns shown in
FIGS. 1 and 2
with respect to an initial circuit shown in FIG.
17
(
a
) which will be described later, the conventional matching process must successively carry out the matching with respect to all of the patterns with respect to all nodes
1
,
2
,
3
, . . . of the initial circuit.
For the sake of convenience, a description will be given of a case where the matching of only one pattern is checked with respect to the initial circuit shown in FIG.
17
(
a
) by the matching process shown in FIG.
7
. In this case, a check is made to determine whether or not a pattern OAI
21
shown in FIG.
17
(
b
) matches with respect to each node of the initial circuit shown in FIG.
17
(
a
). In FIG.
17
(
b
), a
1
through h
1
indicate both nodes and corresponding input/output signal names, and these node names are unrelated to the node names shown in
FIGS. 1 and 2
.
(1) First, a check is made to determine whether or not a match having the node
1
as a root exists. In this case, the node
1
is an inverter, but the node a
1
is a 2-input NAND gate, and no
Levin Naum
Staas & Halsey , LLP
LandOfFree
Technology mapping method and storage medium does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Technology mapping method and storage medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technology mapping method and storage medium will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3035881