JP3166521B2 - Logic circuit generation 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 method for generating a logic circuit, and more particularly, to a method for generating a logic circuit with fan-out adjustment from functional logic constituted by modules.

[0002]

2. Description of the Related Art In recent years, in the field of logic generation, many fan-out adjustment methods have been proposed to reduce the delay of a generation logic circuit.
Design Automation Conference (Proceedi
ngs of the 30th ACM / IEEE Design AutomationConfere
nce) pp. 230-235, June 1993. This method performs provisional arrangement of the generation logic circuit before performing the fan-out adjustment, and when the fan-out destinations are sorted based on the provisional arrangement result, each signal line in the generated fan-out adjustment circuit does not intersect. Under such a constraint, the fan-out adjustment is performed so that the simple delay of the generation logic circuit is minimized.

[0003]

In the design of an ultra-high-speed processor, delay constraints are very strict. Therefore, even in functional design, design is performed in consideration of optimization of wiring delay of a logic circuit after layout. Therefore, in the fan-out adjustment method, it is necessary to generate a fan-out adjustment circuit in consideration of the optimization from the functional logic. In addition, when a countermeasure for delay is required, the function logic is changed by predicting the layout result of the logic circuit generated from the changed function logic. An adjustment circuit needs to be created.

The above-mentioned conventional method considers the optimization of the wiring delay of the logic circuit after layout. However, since the structure of the fan-out adjusting circuit to be generated depends on the provisional arrangement result, the fan-out adjusting circuit to be generated is There was a first problem that the structure of the structure could not be predicted. The first object of the present invention is to
In order to solve this problem, it is an object of the present invention to provide a method of generating a fan-out adjustment circuit that can consider the optimization of the wiring delay of a logic circuit after layout and has a predictable circuit structure.

In addition, the above-mentioned conventional method does not take into account multiple representations described in functional logic when performing fan-out adjustment, and thus has a second problem that wiring delay of a logic circuit after layout becomes large. there were. A second object of the present invention is to provide a method for generating a fan-out adjusting circuit for further reducing the wiring delay of a logic circuit after layout in consideration of multiple representation in order to solve this problem. .

[0006]

In order to achieve the first object, the present invention provides an input means for inputting functional logic constituted by a module in which a Boolean expression or a macro is described, and a Boolean gate. And a gate allocating means for expanding a macro into a logic circuit; and determining whether fan-out adjustment is required for each output (source) of each module. Inputs (sinks) of a plurality of modules connected to the source are arranged based on the order of the module IDs of the modules, and each pair of components (source, sink, amplifier) of the fanout adjustment circuit to be generated is connected. Under the constraint that the signal lines do not cross when laid out in a straight line, the optimization criteria for the quality of the generated logic (1) Fanout for generating fanout adjustment logic that satisfies the condition that the maximum number of gate stages in the path between the input and output edges of the generation logic circuit is the minimum and (2) the number of gates of the generation logic circuit is the minimum under the condition of (1). An adjusting means and a main processing means for generating the logic circuit by controlling the fan-out adjusting means and the gate allocating means while tracing the modules constituting the functional logic (means 1). .

Further, according to the present invention, in order to achieve the second object, in the above means 1, the functional logic includes a plurality of multiple expression modules, and the input means includes a plurality of multiple expression modules. When expanding to a single expression module group (expansion module group), when the sink connected to the source includes a sink of one or more expansion module groups, The condition that the fan-out adjustment signal line supplied to the sink of the module group is dedicated to the sink of the expansion module group, and the fan-out adjustment signal line is not supplied to the sink of the module that is not multiplexed with other expansion module groups. This is added to the constraint condition (means 2).

[0008]

The above-mentioned means 1 enables generation of a fan-out adjusting circuit which can optimize the wiring delay of a logic circuit after layout and has a predictable circuit structure.

The above means 2 enables the generation of a fan-out adjusting circuit for further reducing the wiring delay of the logic circuit after layout.

[0010]

FIG. 2 is a block diagram of a logic generation system on which the present invention is based. This system is an input / output device 20
2, 209, design master file (functional logic) 203,
Main processing device 204, arrangement order allocating device 205, gate allocating device 206, fan-out adjusting device 207,
A design master file (logic circuit) 208. Hereinafter, an outline of the function of each block will be described.

The input / output device 202 is a functional logic diagram 201 composed of modules describing Boolean expressions or macros.
Is read, and if there are multiple expression modules, the modules are developed into a single expression module group, and the result is written in the design master file (functional logic) 203.

The main processing unit 204 first reads the functional logic from the design master file (functional logic) 203, and arranges the arrangement order assigning unit 205, the gate assigning unit 206,
Using the fan-out adjusting device 207, the polarity of the input / output parameters of the modules constituting the function logic and the fan-out adjustment are performed.

Next, a logic circuit is generated from the functional logic by using the gate assignment device 206, and the logic circuit is written in a design master file (logic circuit) 208. Here, the gate assignment device 206 is an extension of, for example, the device described in Japanese Patent Application No. 5-232825, and has a function of assigning a gate in a Boolean manner and a function of expanding a macro into a logic circuit. The input / output device 209 reads a logic circuit from the design master file (logic circuit) 208 and outputs a logic circuit diagram 210.

FIG. 1 is a flowchart of a logic generation process according to the present invention, which operates on the main processing unit 204. Hereinafter, each step of the flowchart will be described in detail, taking as an example a case where the functional logic of FIG. 8 is input.

The functional logic of FIG. 8 is processed by the input / output device 202 as shown in FIG. 9, and the functional logic of FIG. 9 is written in the design master file (functional logic) 203. Here, single expression modules 904 to 906 and 907 to 90 developed from the multiple expression modules 804 and 805
9 is assigned a unique, identical and positive multiple expression identification number 1 or 2, respectively.
The multiple expression identification number 0 is assigned to all of 10, 911.

Step 101: This step inputs functional logic from the design master file (functional logic) 203.

Step 102: This step is Step 1
The amplifier information used in the fan-out adjustment of 06 is acquired. The amplifier information is the driving capability of the output pin of the amplifier, the load of the input pin, the number of gate stages, and the number of gates. The amplifier information sets the gate assignment device 206 to the trial mode, and inputs an amplifier Boolean expression (Y = X). Acquire by executing. Hereinafter, it is assumed that the P-pole driving capability and the N-pole driving capability of the output pin of the amplifier are respectively 2, the load of the input pin is 1, the number of gate stages is 1, and the number of gates is 1.

Step 103: This step is Step 1
It is checked whether or not there is an input edge on which the tracing process in step 104 has not been performed in the functional logic input in step S01.
Go to step 4, otherwise go to step 107.

Step 104: This step is Step 1
Steps 05 and 106 are repeated.

Step 105: This step is Step 1
03 or the fan-out destination of the trace target set in the previous step, which has not been subjected to step 104, is checked. If there is a fan-out destination, the process proceeds to step 104 with that fan-out destination as the trace target. Proceed to 106.

Step 106: In this step, if the trace target set in step 103 or 105 is a module, a gate allocation trial and fan-out adjustment are performed on the module. If the trace target is an input edge, the input edge Perform fan-out adjustment.

FIG. 10 shows that the object to be traced is a module 90.
In the case of 3, the state before performing step 106 on the module is shown. Here, the output parameter Z of the module 903 is set to s, the input parameter A of the modules 904 to 909, and the input parameter A of the modules 910 and 911.
0 is sequentially set to a to h, and the polarity of the input parameters a to f is P pole, and the polarity of the input parameters g and h is N
It is assumed that the number of poles and gate stages of gates 1001 to 1006 is 1, and the number of gate stages of gates 1007 and 1008 is 2. Hereinafter, s is called a source, and ah are called sinks.

FIG. 3 is a flowchart of the gate allocation trial / fan-out adjustment processing in step 106. Hereinafter, the processing procedure of this step will be described in detail with reference to the flowchart.

Step 301: In this step, the arrangement order is assigned to each sink by the arrangement order assignment device 205. This arrangement order is a lexicographic order of module IDs assigned to each module.

In FIG. 10, the module IDs of the modules 904 to 911 are I1, I2, I3, J1, J2, J
3, K1 and K2, 1 to 8 are assigned to the sinks a to h as the arrangement order.

Step 302: This step is Step 1
03 or a gate allocation trial is performed on the trace target module set in step 105. As a result, the P-pole driving capability and the N-pole driving capability of the output pin of the most output side gate of the logic circuit generated from the module, the load of the input pin of each most input side gate of the logic circuit, the number of gates of the logic circuit and the gate The number is obtained.

In FIG. 10, it is assumed that the source s has a P-pole driving capability and an N-pole driving capability of 2.

Step 303: This step checks whether or not the source satisfies the "source fan-out constraint (1)". If so, the gate assignment trial / fan-out adjustment processing ends.
Go to 04. Here, the “source fan-out constraint (1)” satisfies both the source P-pole driving capability ≧ the sum of the P-pole load of the sink and the source N-pole driving capability ≧ the sum of the N-pole load of the sink. That is.

Step 304: This step adjusts the fan-out of the source.

FIG. 4 is a flowchart of the fan-out adjustment processing in step 304. Hereinafter, the processing procedure of this step will be described in detail with reference to the flowchart.

Step 401: This step determines the number of accumulated gate stages of the source. Here, the cumulative gate stage number of the source is the maximum value of the gate stage number of each path from the source to the output edge.

FIG. 5 is a flowchart of the process of determining the cumulative number of gate stages of the source in step 401. Hereinafter, the processing procedure of this step will be described in detail with reference to a flowchart.

Step 501: This step sets the target value h of the number of accumulated gate stages of the source as follows.

(A) First time of this step h = max di, di = the number of accumulated gate stages of sink i.

(B) The second and subsequent times of this step. H = h '+ a, h' = the target value of the previous cumulative gate stage number of the source, a = the gate stage number of the amplifier.

In FIG. 10, the target value of the cumulative gate stage number of the source s is 2.

Step 502: This step sets the level of the sink i to li = (h-di) / a. here,
li truncates the value after the decimal point.

FIG. 11 shows a state after setting the levels of the first sinks a to h. Here, the first element in parentheses of each sink is the input polarity of the sink, and the second element is
The arrangement order of the sinks allocated in 1 and the third element are the multiple expression identification numbers of the modules having the sinks as input parameters, allocated in the input / output device 202.

Step 503: This step inserts an amplifier between the source and the sink.

FIG. 6 is a flowchart of the amplifier insertion process in step 503. Hereinafter, the processing procedure of this step will be described in detail with reference to the flowchart.

Step 601: This step sets the maximum value of the sync level to L.

In FIG. 11, the maximum value 1 of the levels of the sinks a to h is set to L.

Step 602: In this step, first, if there is a fan-out destination (amplifier or sink) of level L + 1, the minimum number of amplifiers capable of supplying a signal to the fan-out destination is inserted into level L, and the amplifier is described later. The arrangement order and the multiple expression identification number are given by the method.

In the following, the amplifier has a fan-out destination with a multiple expression identification number of 0, or all the sinks with the same multiple expression identification number as the fan-out destination of the amplifier have the level L +.
If it is one or more, the amplifier is called a type 1 amplifier; otherwise, the amplifier is called a type 2 amplifier.

In the above-described amplifier insertion, the P-pole signal and the N-pole signal output from the same amplifier are regarded as different output signals, and the constraint condition (a) arranges the fan-out destination of the level L + 1 in accordance with their arrangement order. L amplifier and level L +
When the signal lines connecting the 1 fan-out destination are wired so as to be linear, the signal lines do not intersect. (B) The output signals of a plurality of amplifiers are sent to the fan-out destination having the same positive multiple expression identification number. When supplying, the fan-out destination and the fan-out destination of another multiple expression identification number are the same output signal of the type 1 amplifier (either P-pole signal or N-pole signal) or the same type 2 amplifier. (The P-pole signal and the N-pole signal) are not supplied.

Next, the minimum value of the arrangement order of the fan-out destinations of the amplifiers is assigned to the arrangement order of the inserted amplifiers.
If the amplifier is of type 1, 0 is assigned to the multiple expression identification number of the amplifier, and if the amplifier is of type 2, the same multiple expression identification number as the fan-out destination of the amplifier is assigned. The input polarity of the amplifier is not determined.

Step 603: In this step, it is checked whether L = 0 is satisfied, and if it is satisfied, the amplifier insertion processing ends, and if not, the flow proceeds to step 604.

Step 604: This step sets the value of L to 1
Make it smaller.

In FIG. 11, steps 602, 603, 60
By sequentially performing steps 4, 602 and 603, the amplifiers 1201 to 1204 are inserted at level 0 as shown in FIG. Here, the input polarities of the amplifiers are all undecided (U
Pole), the arrangement order is 1, 3, 4, 6, which is the minimum value of the arrangement order of the fan-out destinations of the amplifiers, and the multiple expression identification numbers are all 0.

Step 504: This step is Step 5.
It is checked whether or not the result of 03 satisfies the “source fan-out constraint (2)”. If the result is satisfied, the process for determining the number of accumulated gate stages of the source is completed. If not, the process proceeds to step 501. Here, “source fan-out constraint (2)” means (a) P-pole drive capability of source ≧ level 0
Sum of P-pole load at fan-out destination of (b) N of source
Pole drive capability ≧ sum of the N-pole loads at the fan-out destination at level 0, (c) Sum of the P-pole drive capability and the N-pole drive capability of the source ≧
The sum of the loads of the P pole, N pole and U pole of the fan-out destination of level 0. (d) If the amplifier is in the fan-out destination of the same positive multiple representation identification number of level 0, the fan-out destination is That is, the same output signal (either the P-pole signal or the N-pole signal) of the source is not supplied to the fan-out destinations of the other multiple expression identification numbers.

In FIG. 12, the sum of the P-pole driving capability and the N-pole driving capability of the source s is 4, and the sum of the loads of the P-pole, N-pole, and U-pole at the fan-out destination of level 0 is 6, The state 12 does not satisfy the “source fan-out constraint (2)”.
Therefore, the process proceeds to step 501. Second step 50
Due to 1, the target value of the cumulative gate stage number of the source s becomes 3. FIG. 13 shows a state after performing the second step 502, and FIG. 14 shows a state after performing the second step 503. In FIG. 14, the level 0 fan-out destination P
Since the sum of the loads of the pole, the N pole, and the U pole is 2, the state of FIG. 14 satisfies the “source fan-out constraint (2)”. Accordingly, the process of determining the number of accumulated gate stages of the source ends. At this time, the number of accumulated gate stages of the source s is determined to be three.

Step 402: This step is Step 4.
01 minimizes the number of inserted amplifiers. FIG. 7 is a flowchart of the process of minimizing the number of amplifiers. Hereinafter, the processing procedure of this step will be described in detail with reference to a flowchart.

Step 701: This step sets flg to F
Set to.

Step 702: In this step, the sinks are sorted in descending order of the levels, and if the levels are the same, in accordance with the arrangement order.

In FIG. 14, the sinks a to h are sorted in the order of a to h.

Step 703: This step sets i to 1.

Step 704: This step is performed when i> n (n
Is the number of sinks), and if so, proceed to step 710; otherwise, proceed to step 705.

Step 705: This step is Step 7
The level of the i-th sync in the sort of 02 is reduced by one.

Step 503: This step inserts an amplifier between the source and the sink.

Step 706: This step is Step 5.
It is checked whether or not the result of 03 satisfies the “source fan-out constraint (2)”. If so, the process proceeds to step 707. If not, the process proceeds to step 709.

Step 707: This step sets flg to S
Set to.

Step 708: This step sets the value of i to 1
Enlarge.

Step 709: This step is Step 7
In step 05, the level of the sink whose level is reduced by 1 is returned to the original level.

FIG. 15 shows the state after the amplifier is inserted with the level of the sink a reduced by 1 when i = 1, and FIG. 16 shows the state of the sinks a to f when i = 6. This shows the state after the amplifier is inserted with the level reduced by one. In the above, when i = 7, if the level of each of the sinks a to g is reduced by 1 and the amplifier is inserted, the “source fan-out constraint (2)” is not satisfied, and therefore g
Is restored, and when i = 8, the sinks a to f,
If the level of h is decreased by one and the amplifier is inserted, the "source fan-out constraint (2)" is not satisfied, so the level of h is restored.

Step 710: This step is flg = S
And if so, proceed to step 701,
If not, the amplifier minimization process ends.

As described above, if i = 1 to 6, flg = S, so that the process proceeds to the second step 701. Thereafter, if the processing of steps 701 to 710 is repeated, flg = S in the case of i = 1, so the processing proceeds to the third step 701.

FIG. 17 shows a state after the amplifier is inserted with the level of the sink a further reduced by 1 when i = 1. Thereafter, the processing of steps 701 to 710 is repeated, and as a result, no matter which sink level is reduced by 1 in step 705, the “source fan-out constraint (2)” is not satisfied. Therefore, flg = F, and the process of minimizing the number of amplifiers ends.

Step 403: This step determines the input polarity of the amplifier. More specifically, the same polarity as that of the sink having the same multiplex expression identification number as that of the amplifier is used. Under this condition, the number of P-pole used loads and the number of N-pole used loads of the source or the amplifier are made as equal as possible. Determine the input polarity.

FIG. 18 shows a state after the input polarity of the amplifier is determined. Here, the input polarity of the amplifier 1801 is determined to be the same P-pole as that of the sink a having the same multiplex expression identification number as the amplifier, and the input polarity of the amplifiers 1802 and 1803 is determined to be the source s.
The N pole is determined so that the P pole use load number and the N pole use load number are equal.

Step 107: In this step, a gate is assigned to the functional logic for which the fan-out adjustment and the polarity have been determined in the step, and a logic circuit is generated.

FIG. 19 shows a logic circuit generated from the functional logics of FIGS. 10 and 18.

Step 108: This step is Step 1
The logic circuit generated in step 07 is output to the design master file (logic circuit) 208.

[0073]

According to the present invention, since a wiring delay of a logic circuit after layout can be reduced and a fan-out adjustment circuit having a predictable circuit structure can be generated, a logic circuit having a higher speed than the conventional one can be provided. It is possible to design in a shorter time.

[Brief description of the drawings]

FIG. 1 is a flowchart of a logic generation process according to the present invention.

FIG. 2 is a block diagram of a logic generation system which is a premise of the present invention.

FIG. 3 is a flowchart of a gate assignment trial / fan-out adjustment process.

FIG. 4 is a flowchart of a fan-out adjustment process.

FIG. 5 is a flowchart of processing for determining the number of accumulated gate stages of a source.

FIG. 6 is a flowchart of an amplifier insertion process.

FIG. 7 is a flowchart of a process of minimizing the number of amplifiers.

FIG. 8 is an explanatory diagram showing an example of functional logic.

FIG. 9 is an explanatory diagram showing functional logic after a module of multiple expression is developed.

FIG. 10 is an explanatory diagram showing a state before performing a gate assignment trial and a fan-out adjustment on a module 903.

FIG. 11 is an explanatory diagram showing a state after a first sync level is set.

FIG. 12 is an explanatory diagram illustrating a state after the first amplifier insertion.

FIG. 13 is an explanatory diagram illustrating a state after a second sync level is set.

FIG. 14 is an explanatory diagram illustrating a state after the second amplifier insertion.

FIG. 15 is an explanatory diagram illustrating a state after the amplifier a is inserted with the level of the sink a reduced by one.

FIG. 16 is an explanatory diagram showing a state after the amplifiers are inserted with the levels of the sinks a to f reduced by one.

FIG. 17 is an explanatory diagram showing a state after the amplifier a is inserted with the level of the sink a further reduced by one.

FIG. 18 is an explanatory diagram illustrating a state after the input polarity of the amplifier is determined.

FIG. 19 is an explanatory diagram showing a generation logic circuit.

[Explanation of symbols]

101 to 108: logic generation processing step, 201: functional logic diagram, 202, 209: input / output device, 203: design master file (functional logic), 204: main processing device, 205
... Arrangement order allocating device, 206 gate allocating device, 207 fan-out adjusting device, 208 design master file (logic circuit), 210 logic circuit diagram.

──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Hiroo Watai 1st Horiyamashita, Hadano-shi, Kanagawa Prefecture Hitachi, Ltd. General-purpose Computer Division (72) Inventor Iku Moriwaki 1st Horiyamashita, Hadano-shi, Kanagawa Hitachi, Ltd. (56) References JP-A-4-124775 (JP, A) JP-A-62-297974 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) G06F 17 / 50

Claims (2)

(57) [Claims] In a logic generation system for automatically generating a logic circuit of a target circuit from a functional logic constituted by a module describing a Boolean expression or a macro, an input means for inputting the functional logic and a gate in the Boolean expression are provided. allocation,
A gate assigning means for expanding a macro into a logic circuit, and judging whether fan-out adjustment is required at each source of each module, and when fan-out adjustment of the source is necessary, being connected to the source. Sinks of a plurality of modules are arranged based on the order of the module IDs of the modules, so that signal lines connecting each pair of a source, a sink, and an amplifier, which are components of a fan-out adjustment circuit to be generated, are linear. Under the constraint that the signal lines do not intersect when wired, the maximum number of gate stages in the path between the input and output edges of the generated logic circuit is the minimum, and the condition (1) A fan-out adjusting means for generating fan-out adjusting logic in which the number of gates of the generating logic circuit satisfies the following: Logic generating system comprising: a main processing unit operable to suppress a fan-out adjustment means the gate allocation means while tracing Le generates the logic circuit. 2. The logic generation system according to claim 1, wherein
A method of generating a logic circuit , wherein the functional logic includes a plurality of multiple expression modules, and the input means expands each multiple expression module into a single expression expansion module group. When the sink connected to the source includes a sink of one or more expansion modules, a fan-out adjustment signal line to be supplied to the sink of each expansion module is dedicated to the sink of the expansion modules. A method of generating a logic circuit in which a condition that the fan-out adjustment signal line is not supplied to a sink of a module of a non-multiplex expression with another expansion module group is added to a constraint condition.