JP3183415B2 - Logic synthesis method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a gate array and a PLD.
The present invention relates to a logic synthesis method for optimizing a logic circuit which can be used when designing (programmable logic device), and in particular, a logic synthesis method capable of further minimizing the number of wires, delay values, and gates. About.

[0002]

2. Description of the Related Art In recent years, as the degree of integration of semiconductor integrated circuits has become higher and higher, the amount of design work for semiconductor integrated circuits has also increased, and the contents of semiconductor integrated circuit design work for achieving required specifications have also increased. It's complicated.

Various methods have been conventionally proposed as a circuit design method of a logic circuit incorporated in a semiconductor integrated circuit. For example, there is a so-called top-down method of sequentially designing a detailed configuration and a logic circuit from predetermined functions, performances, and logics. In addition, there is a so-called bottom-up method of gradually designing a large-scale configuration while combining logical blocks that have already been used.

[0004] In designing such a logic circuit, a logic circuit to be designed is input by inputting a function description or a predetermined circuit diagram.

During or after the design of a logic circuit,
Logic synthesis is performed to further minimize the number of wires, delay values, and gates.

As one of the logic synthesis methods, for example, there is a logic synthesis method called Quinema-Cluskey method. In the Quinma-Kraskey method, logic is simplified and complex gates are used to reduce gate delays, common terms are extracted to reduce the number of gates, and assignment is mainly performed in one output logic cell sequentially. This is a method of minimizing the number of wirings, the delay value, and the number of gates.

On the other hand, as a technique for facilitating the work of designing a semiconductor integrated circuit, there is a circuit design technique using a gate array, a transistor array, a PLD, or the like.

[0008] The gate array is formed by arranging a large number of gates, which form the basis of a logic circuit, in a row in a semiconductor integrated circuit chip. Further, the transistor array has a configuration in which a large number of transistors necessary for forming a gate are laid out in a row on a semiconductor integrated circuit chip. or,
The PLD is such that a user can arbitrarily define the function of a logic circuit by using a fuse or a transistor switch arranged in a matrix inside.

[0009]

However, the above-described Quinma-Cluskie method has a problem that it is not guaranteed to obtain a sufficient solution, especially for minimizing the delay value. For this reason, when the Quinma-Cluskie method is used, there is a problem in that the design must be changed many times manually, and much design time is required.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned conventional problems, and it is an object of the present invention to minimize the number of wirings, delay values, and gates, and particularly to synthesize a logic circuit having a minimized delay value. It is an object of the present invention to provide a logic synthesis method that can perform the above.

[0011]

According to the present invention, in a logic synthesis method for optimizing a logic circuit, logic gates in the logic circuit are developed into basic logic gates, and the developed basic logic gates are multiplied. Complex gate into input logic gate,
After that, the merging process is performed focusing on the similar circuit, and further, by forming a composite gate into a multi-output logic gate,
The above object has been achieved.

[0012]

FIG. 1 is a flowchart showing the gist of the present invention.

As shown in FIG. 1 above, the present invention mainly comprises a step 108 for developing into basic logic gates;
Step 11 of making a composite gate into a multi-input logic gate
8, step 124 for performing merging processing, and step 128 for performing complex gate formation into multiple output logic gates.

Also, the logic synthesis method of the present invention
In the case of automation using a D (computer aided design) system or the like, a logic circuit to be subjected to logic synthesis is first input in step 104 by inputting a function description or a predetermined circuit diagram.

In the present invention, the step 108
Before and after step 114, a step 114 of making the inverter a composite gate may be inserted. For example, step 108
If a basic logic gate having an inverter function is also included in the basic logic gates of the above, a step 11 is carried out before the step 108 in which the inverter is turned into a composite gate.
4 may be charged. If the multi-input logic gates of step 118 include those having an inverter function, step 114 of compounding the inverters may be inserted before step 118.

In the step 108, when performing the logic synthesis, first, the logic circuit to be subjected to the logic synthesis is developed into a relatively single-function basic logic gate. For example, a two-input AND gate, a two-input OR gate, an inverter gate, a flip-flop, or the like is used. In some cases, a two-input NAND gate or a two-input NOR gate is used.

In step 118, the following step 1
A multi-input logic gate that can be processed in step 24 or step 128,
Further, after the completion of the step 128 and the completion of the logic synthesis, a composite gate is formed into a multi-input logic gate which can be incorporated in a PLD or the like. For example, a three-input AND gate,
It is compounded into a multi-input logic gate such as a 4-input AND gate.

In step 124, attention is paid to, for example, logic gates having a common input, and circuit portions to be processed are compared to make similar circuits common. As a result, not only the number of wires and the number of gates can be minimized, but also the number of branches of the wires can be reduced, so that the number of fan-outs can be reduced and the delay value can be minimized.

In the step 128, a composite gate is formed into a usable multiple output logic gate. For example, a composite gate is formed into a multi-output logic gate which is often used as a decoder and registered as one composite gate.

As described above, according to the present invention, a composite gate can be effectively formed into a usable multiple-input logic gate or multiple-output logic gate. This makes it possible to minimize the number of wirings, delay values, and gates, and in particular to synthesize a logic circuit in which the delay value is minimized.

It is to be noted that, in the above-mentioned step 118, the complex gate is formed into a multi-input logic gate, and in the above-mentioned step 128
The complex gate formation into the multi-output logic gates in the above is performed only on the available multi-input logic gates and multi-output logic gates. Therefore, for example, in the case of a PLD or the like, the combination of gates exceeding the restrictions of the cell structure is not performed. The same applies to the merging process in step 124 described above.

[0022]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be described below in detail with reference to the drawings.

FIG. 2 is a flowchart of the embodiment of the present invention.

In FIG. 2, in step 200,
A function description of a logic circuit to be subjected to logic synthesis according to the present embodiment is input. This function description input includes, for example, the following input method.

(1) State transition input (2) Truth table input (3) Boolean expression input (4) HDL (Hardware Description Language)
) Description input

When a logic circuit is generated from such a function description input, it must be converted into a common expression format. This conversion method includes, for example, the following.

(1) EDIF (Electronics Data)
Interchange Format) File description: The output file is mainly used for inputting a logic circuit diagram.

(2) Truth table description

In the present embodiment, the above-described truth table description is used as a conversion method to the common expression format.

When described in the truth table, step 202
After the completion of the logic synthesis shown in FIG. 2, the logic circuit is converted into a basic logic cell which can be used in a gate array or the like, for example.

On the other hand, in step 204, a logic circuit diagram is input by a predetermined method.

In step 210, step 202
Is combined with the input result in step 204 to generate one netlist.

Subsequently, in step 214, the number of wirings and the number of gates are minimized by forming the inverter and other logic cells into composite gates. The complex gate formation differs as follows depending on whether or not the output net of the target inverter is branched.

(1) When the output net of the inverter is not branched: The inverter is taken into a basic logic cell or an input / output buffer.

(2) When the output net of the inverter is branched: The branch of the output net of the inverter is moved to the input of the inverter. That is, the number of inverters is the same as the number of branches. After that, each inverter is taken into the input of the basic logic cell and the input of the output buffer.

It should be noted that the combination of the inverters in the step 214 is limited by the configuration of the logic cell library and the like. For example, in the logic cell library, there may be a case where the multi-input logic cell or the multi-output logic cell does not have the combination of the input inversion. In such a case, the process of step 214 is omitted.

In step 218, a plurality of basic logic cells are integrated into one composite gate. This step 2
The compound gate 18 is as follows in the present embodiment.

(1) Search sequentially from the net on the output side (hereinafter referred to as the search start net) to the input side.

(2) The searched basic logic cells are converted into composite gates in a range where the total number of input nets of the searched gates is equal to or less than the limit of the number of inputs of the logic cells registered in the logic cell library. Note that the total number of nets in the input is the total number of nets having different net numbers. Even if the nets are input to different basic logic cells which are formed into composite gates, only one net number is duplicated. Is calculated as

(3) If the searched net is branched, no further search is performed on the input side.

(4) The search depth when sequentially tracing the net to the input side, that is, the number of logic cells to be searched is limited. By increasing the depth of the search, the total number of input nets can be reduced in some cases. However, if the depth is too large, the logic synthesis operation generally increases.
In this embodiment, the depth of the search is defined as the depth of the number of basic logic cells searched up to the input net.

Subsequently, in step 224, a composite gate is further formed in accordance with the limitation of the logic cell library to be used. For example, the number of outputs of a logic cell library is limited, for example, according to the type of registered multiple output logic cells,
A composite gate of a plurality of logic cells is provided. The merging process of step 224 in the present embodiment is as follows.

(1) A similar part is found by paying attention to a logic cell having a common input, and a plurality of multi-input logic cells are formed into a composite gate.

(2) It is checked whether all the combination gates and all two combinations taken out of all the logic cells are usable multiple output logic cells such as registered in a logic cell library. Then, available ones are extracted as allocation candidates (two-output merging process).

(3) In the logic circuit which is a candidate for allocating a two-output logic cell extracted in the above (2), a logic cell library is further provided for all the combination gates and all the two combinations taken out from all the logic cells. Check whether or not the cell is a usable multiple output logic cell, such as whether or not it is registered, and extract a usable cell as an allocation candidate (3
Output merging).

(4) In the logic circuit which is a candidate for assigning a three-output logic cell extracted in the above (3), furthermore, the logic used for all two combinations extracted from all the composite gates and all the logic cells is used. Check whether or not the cell is an available logic cell, such as checking whether or not the cell is registered in the cell library, and extract a usable cell as an allocation candidate (merging process of four outputs) .

(5) The above (2) to (4) are repeatedly performed within the limit on the number of outputs of the logic cells that can be used.

(6) All composite gates and all logic cells are extracted as one-output allocation candidates (one-output candidate extraction). This process is performed in order to save a circuit that has not been allocated to the multiple output logic cell (for example, an FPGA).
(For field programmable gate array)).

After step 224, in the case of a logic circuit used for a general gate array, step 23 is then executed.
Proceed to 4. On the other hand, in the case of a logic circuit used for a PLD such as an FPGA, the process proceeds to step 238.

In step 234, first, a set of allocation candidates necessary for forming the entire logic circuit is extracted from the allocation candidates obtained in step 224. After this,
The following parameters are calculated for each set.

(1) Calculate the total number of nets (related to minimizing the number of nets).

(2) Calculating the total number of gates (related to minimizing the number of gates): In a PLD such as an FPGA, the total number of gates is calculated. In the case of a gate level in a general logic circuit or the like, the total number of transistors is calculated to minimize the number of transistors.

(3) Calculate the total number of net branches (minimize the number of net branches).

(4) Calculating the delay value of the critical path (related to minimizing the delay value of the critical path): For example, minimizing the number of gate stages.

Thereafter, in step 234, the values of the four types of parameters obtained are compared with each other with respect to the set of allocation candidates, and the priority between the four types of parameter items is also considered. While selecting one set of allocation candidates.

On the other hand, for a PLD such as an FPGA, the processing in step 238 performed after step 224 is almost the same as the processing in step 234. However, the condition of the logic cell used depends on the restrictions on the cell structure of the PLD.

FIG. 3 is a logic circuit diagram of an example of a logic circuit to be subjected to logic synthesis in this embodiment.

Hereinafter, the operation of this embodiment will be described by taking the logic circuit shown in FIG. 3 as an example and under the following conditions.

(1) Restriction on the number of inputs of the logic cell library = 4 inputs (2) Restriction on the depth of search when forming a basic logic cell into a composite gate = 2 (3) Restriction on the number of outputs of the logic cell library = 4 outputs

In the example described later with reference to FIG. 14, the limit on the number of outputs is two.

The logic circuit shown in FIG.
A total of eight logic cells U01 to U08 which are ND logic cells
And a total of four logic cells U09 to U which are OR logic cells
12 and a total of four logic cells U as inverter gates
13 to U16. Further, a total of four inputs of the logic circuit shown in FIG. 3 are terminals A to D, respectively, and a total of four outputs are terminals Z0 to Z3, respectively. Symbols N01 to N20 are net numbers assigned to the nets of the respective parts.

First, the logic circuit of FIG. 3 performs steps 200, 202, 204, and 2 of the flowchart of FIG.
When the input is made at 10 and the completion of the compounding of the inverters at step 214 is completed, a logic circuit as shown in FIG. 4 is obtained.

In FIG. 4, a total of four logic cells U13 to U16 are reduced as compared with FIG. Further, a total of four nets N05 to N08 have disappeared.

FIG. 5 is a flow chart showing the processing in step 214 in FIG.
7 is a list of basic logic cells having a total number of inputs of 2 after the completion of the composite gate formation of the inverter of FIG.

In the steps of FIGS. 4 and 5,
The total number of gates is 12. The total number of nets is 12.

When step 218 is performed after step 214 in FIG. 2, the composite gate is formed as shown in FIG.

FIG. 6 is a diagram showing each logic cell after it has been converted into a composite gate into a multi-input logic cell.

As shown in FIG. 6, the logic cell U01 and the logic cell U09 shown in FIGS. 4 and 5 are combined to form a logic cell U21. Logic cell U02 and logic cell U09 are combined to form logic cell U22. The logic cell U03a and the logic cell U10 are combined to form a logic cell U23. Logic cell U04a and logic cell U10 are combined to form logic cell U24. Logic cell U05a
And the logic cell U11 are combined to form a logic cell U25. The logic cell U06a and the logic cell U11 are combined,
The logic cell becomes U26. Logic cell U07a and logic cell U
12 is compounded to form a logic cell U27. Logic cell U
08a and the logic cell U12 are combined, and the logic cell U28
Becomes

Therefore, after the end of step 218 in FIG. 2, the total number of gates is reduced to eight as shown in FIG.

Following the step 218 in FIG. 2, merging of the basic logic cell and the composite gate in the step 224 is sequentially performed as shown in FIGS.

FIG. 7 is a diagram showing a logic cell at the stage of one output logic cell at the end of the merging process.

At the stage shown in FIG. 7, the merging process focusing on similar circuits has been completed. At this stage, the logic cells U01, shown in FIG. 4 and FIG.
Logic cell U02 and logic cell U09 are connected to logic cell U31.
Has been compounded. Logic cell U03a, logic cell U04
a and the logic cell U10 are combined with the logic cell U32. Logic cell U05a, logic cell U06a and logic cell U11 are combined into logic cell U33. Logic cell U07a, logic cell U08a and logic cell U12
It is combined with the logic cell U34.

In the stage of FIG. 7, the total number of gates is minimized to a total of four gates.

FIG. 8 is a diagram showing a logic cell at the stage of a two-output logic cell at the end of the merging process.

At the stage shown in FIG. 8, the logic cell U31 and the logic cell U32 of FIG.
The logic cell is U41. At the stage shown in FIG. 8, the total number of gates is three, including the logic cell U33 and the logic cell U34 not shown.

FIG. 9 is a diagram showing a logic cell at the stage of a three-output logic cell at the end of the merging process.

In the stage of FIG. 9, the logic cell U41 of FIG. 8 and the logic cell U33 of FIG. 7 are combined to form a logic cell U42. Therefore, at this stage, the logic cell U34 in FIG.
, The total number of gates is two.

FIG. 10 is a diagram showing the logic cells at the end of the merging process at the stage of the four-output logic cells.

At the stage shown in FIG. 10, the logic cell U42 of FIG. 9 and the logic cell U34 of FIG. 7 are combined to form a logic cell U43.
At this stage, the total number of gates is one.

According to the merging process relating to steps 224 in FIGS. 7 to 10 and FIG. 2, usually, a plurality of allocation candidates are generated while the allocation candidates necessary to constitute the entire logic circuit are generated. Multiple sets are extracted.

In step 234 or step 238 in FIG. 2, the above-mentioned parameters of each set serving as a selection criterion are calculated from the plurality of sets, and the parameters calculated between these sets are calculated. The parameters are compared with each other to select one logic circuit.

FIG. 11 is a logic circuit diagram of a logic circuit selected for a gate array.

In FIG. 11, selection is made in accordance with the condition that a logic cell library having a group of logic circuits of multiple inputs and multiple outputs with four inputs and four outputs or less and capable of handling all logics including inverted inputs is provided. Have been. This FIG.
The logic cell U44 shown in FIG. 10 corresponds to the logic cell U43 in FIG.

When logic synthesis is completed as shown in FIG. 11, the total number of gates can be reduced to one.
The total number of nets is eight.

On the other hand, in the FPGA having the following restriction conditions, the logic cells shown in FIGS. 12 and 13 are generated after the end of the step 224.

(1) Limit of the number of inputs of the logic cell library = 4 (2) Depth of search for the basic logic cell = 2 (3) Limit of the number of outputs of the logic cell library = 2

When a plurality of sets of allocation candidates as shown in FIGS. 12 and 13 are extracted, in step 238 in FIG. 2, a logic circuit as shown in FIG. 14 is selected.

In FIG. 14, the logic cell U45 is as shown in FIG. 12, and the logic cell U46 is as shown in FIG. Each of the logic cell U45 and the logic cell U46 is configured by an FPGA.

As described above, when logic synthesis is performed as shown in FIG. 14, the total number of gates can be reduced to two, and the total number of nets becomes eight.

[0090]

As described above, according to the present invention, it is possible to minimize the number of wirings, delay values, and gates, and especially to synthesize a logic circuit with a minimized delay value. The effect can be obtained.

[Brief description of the drawings]

FIG. 1 is a flowchart showing the gist of the present invention.

FIG. 2 is a flowchart of an embodiment of the present invention.

FIG. 3 is a logic circuit diagram of an example of a logic circuit to be subjected to logic synthesis according to the embodiment;

FIG. 4 is a logic circuit diagram of a logic circuit after completion of the complex gate conversion of the inverter.

FIG. 5 is a diagram of a list of basic logic cells having a total number of inputs of 2 after the inverter is formed into a composite gate.

FIG. 6 is a diagram showing a logic cell after complex gate formation into a multi-input logic cell;

FIG. 7 is a diagram showing a logic cell at the stage of one output logic cell at the end of the merging process.

FIG. 8 is a diagram showing a logic cell at the stage of a two-output logic cell at the end of the merging process.

FIG. 9 is a diagram showing a logic cell at the stage of a three-output logic cell at the end of the merging process.

FIG. 10 is a diagram showing a logic cell at the stage of a four-output logic cell at the end of the merging process.

FIG. 11 is a logic circuit diagram of a logic circuit selected for a gate array.

FIG. 12 is a logic circuit diagram of a first logic cell merged for an FPGA.

FIG. 13 is a logic circuit diagram of a second logic cell merged for an FPGA.

FIG. 14 is a logic circuit diagram of a logic circuit selected for an FPGA.

[Explanation of symbols]

U01 to U16, U03a to U12a, U09b to U1
2b: basic logic cells, U21 to U28, U31 to U34: multiple input logic cells, U41 to U46: multiple output logic cells, A to D: input, Z0 to Z3 ... output, N01 to N20: net (wiring).

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) G06F 17/50 H01L 27/118 H01L 21/82

Claims (1)

(57) [Claims] 1. A logic synthesis method for optimizing a logic circuit, comprising: expanding a logic gate in the logic circuit into a basic logic gate; converting the expanded basic logic gate into a multi-input logic gate; Thereafter, a merging process is performed by paying attention to similar circuits, and furthermore, a composite gate is formed into a multi-output logic gate.