Logic transformation and gate placement to avoid routing congestion

This application is a divisional application claiming priority to Ser. No. 11/153,707, filed Jun. 14, 2005, now U.S. Pat. No. 7,356,797 issued Apr. 8, 2008.

1. Technical Field

The present invention relates to logic design, and more particularly, to a logic design method to avoid routing congestion.

2. Related Art

In a conventional digital circuit, a logic block can receive signals from multiple inputs from different directions and send signals to multiple outputs at different directions. Typically, the logic block tends to be placed at a central area of the digital circuit surrounded by the inputs and outputs of the logic block. This tends to result in wiring congestion in the central area.

It is always desirable to reduce wiring congestion in logic design. Minimizing wiring congestion improves wirability and reduces the adjacency capacitance impact on timing and noise. As a result, there is a need for a logic design method for reducing wiring congestion in a logic design.

The present invention provides a logic design method, comprising the steps of (a) providing a logic block comprising an input stage and an output stage; and (b) placing each input gate of the input stage in a vicinity of the input gate's respective inputs.

The present invention also provides a logic design method, comprising the steps of (a) transforming a gate G into a logic block including an input stage and an output stage, wherein inputs of the input stage are the inputs of the gate G, and wherein outputs of the output stage are the outputs of the gate G; and (b) placing each input gate of the input stage in a vicinity of the input gate's respective inputs.

The present invention also provides a logic design method, comprising the steps of (a) transforming a two-stage logic into the logic block including an input stage and an output stage, wherein the two-stage logic includes a first stage and a second stage, wherein the first stage includes T gates, and wherein the second stage includes an output gate that is configured to receive input signals from all the T gates of the first stage; and (b) placing each input gate of the input stage in a vicinity of the input gate's respective inputs.

The present invention provides a logic design method for reducing wiring congestion in a logic design.

FIGS. 1A-1C show logic diagrams used to illustrate a first logic design method, in accordance with embodiments of the present invention.

FIG. 1D is a flowchart that illustrates the first logic design method.

FIGS. 2A-2C show logic diagrams used to illustrate a second logic design method, in accordance with embodiments of the present invention.

FIG. 2D is a flowchart that illustrates the second logic design method.

FIG. 3 illustrates a flow chart of a logic design method, in accordance with embodiments of the present invention.

FIG. 4 illustrates a computer system 90 used for simulating the methods of the present invention.

FIGS. 1A-1C show logic diagrams used to illustrate a first logic design method, in accordance with embodiments of the present invention. FIG. 1D is a flowchart 199 that illustrates the first logic design method. More specifically, with reference to FIG. 1A , as a first example to illustrate the first logic design method, assume that a gate G receives input signals from inputs A 1 , A 2 , A 3 , B 1 , and B 2 , and sends output signals to outputs O 1 , O 2 , O 3 , O 4 , and O 5 . The input signals from the inputs A 1 , A 2 , A 3 , B 1 , and B 2 come to the gate G from different directions: North, East, North-West, South, and West, respectively. The output signals from gate G fans-out to outputs O 1 , O 2 , O 3 , O 4 , and O 5 in different directions: North-West, North-East, South-East, South-East, and South-West, respectively.

With reference to FIG. 1B , in one embodiment, the first logic design method starts with the step of transforming the gate G ( FIG. 1A ) into a logic block 100 which comprises an input stage 110 and an output stage 120 . In one embodiment, the inputs of the input stage 110 can be also the inputs of the gate G of FIG. 1A (i.e., the inputs A 1 , A 2 , A 3 , B 1 , and B 2 ), and the outputs of the output stage 120 can be also the outputs of the gate G of FIG. 1A (i.e., the outputs O 1 , O 2 , O 3 , O 4 , and O 5 ). In addition, the input stage 110 is configured to send signals to the output stage 120 via connections 125 .

In one embodiment, the step of transforming the gate G ( FIG. 1A ) into the logic block 100 can comprise the following sub-steps (steps 180 - 190 of FIG. 1D ).

In a first sub-step (step 180 of FIG. 1D ), in one embodiment, all the inputs of the input stage 110 can be divided into M input groups of at least two proximate inputs (M is a positive integer). “Proximate” can be defined in different ways. For instance, in one definition, two or more points on a plane can be considered proximate to each other if the radius of the smallest circle within which the points reside is less than a pre-specified value. In the first example above, assume that inputs A 1 , A 2 , and A 3 are proximate to each other, and that inputs B 1 and B 2 are proximate to each other. As a result, the five inputs A 1 , A 2 , A 3 , B 1 , and B 2 can be divided into M=2 input groups of at least 2 proximate inputs: (A 1 , A 2 , A 3 ) and (B 1 , B 2 ).

In a next sub-step (step 182 of FIG. 1D ), in one embodiment, all the outputs of the output stage 120 can be divided into N output groups of at least two proximate outputs (N is a positive integer). In the first example above, assume that outputs O 1 and O 2 are proximate to each other, and that outputs O 3 , O 4 , and O 5 are proximate to each other. As a result, the five outputs O 1 , O 2 , O 3 , O 4 , and O 5 can be divided into N=2 output groups of at least two proximate outputs: (O 1 , O 2 ) and (O 3 , O 4 , O 5 ).

In a next sub-step (step 184 of FIG. 1D ), in one embodiment, as a result of the inputs division above, the input stage 110 can comprise M gates (not shown) corresponding to the M input groups. Similarly, the output stage 120 can comprise N gates (not shown) corresponding to the N output groups (step 186 of FIG. 1D ).

In the first example above, with reference to FIGS. 1B and 1C , because there are M=2 input groups (A 1 , A 2 , A 3 ) and (B 1 , B 2 ), the input stage 110 can comprise M=2 gates Gi 1 and Gi 2 ( FIG. 1C ) corresponding to the M=2 input groups (A 1 , A 2 , A 3 ) and (B 1 , B 2 ), respectively. Similarly, because there are N=2 output groups (O 1 , O 2 ) and (O 3 , O 4 , O 5 ), the output stage 120 can comprise N=2 gates Go 1 and Go 2 ( FIG. 1C ) corresponding to the N=2 output groups (O 1 , O 2 ) and (O 3 , O 4 , O 5 ), respectively.

In a next sub-step (step 188 of FIG. 1D ), in one embodiment, connections between the M gates and the N gates and the inputs and outputs can be made as follows. Each gate of the M gates of the input stage 110 is configured to receive input signals from all the inputs of the gate's corresponding input group. In the first example above, gate Gi 1 is configured to receive input signals from the inputs A 1 , A 2 , A 3 . Similarly, gate Gi 2 is configured to receive input signals from the inputs B 1 , B 2 .

In one embodiment, each gate of the N gates of the output stage 120 is configured to receive input signals from all the M gates of the input stage 110 . In the first example above, gate Go 1 is configured to receive input signals from all the M=2 gates Gi 1 and Gi 2 of the input stage 110 . Similarly, gate Go 2 is configured to receive input signals from all the M=2 gates Gi 1 and Gi 2 of the input stage 110 .

Also, in one embodiment, each gate of the N gates of the output stage 120 is configured to send output signals to all the outputs of its corresponding output group. In the first example above, gate Go 1 is configured to send output signals to the outputs O 1 and O 2 . Similarly, gate Go 2 is configured to send output signals to the outputs O 3 , O 4 , O 4 .

In a next sub-step (step 190 of FIG. 1D ), in one embodiment, the M gates and N gates in the input stage 110 and output stage 120 , respectively are such chosen such that they are functionally equivalent to the gate G ( FIG. 1A ).

In the first example above, if the gate G ( FIG. 1A ) is an OR gate, then the gates Gi 1 and Gi 2 and the gates Go 1 and Go 2 can all be OR gates. If the gate G ( FIG. 1A ) is an AND gate, then the gates Gi 1 and Gi 2 and the gates Go 1 and Go 2 can all be AND gates. Alternatively, if the gate G ( FIG. 1A ) is an OR gate, then the gates Gi 1 and Gi 2 of the input stage 110 can be NOR gates, and the gates Go 1 and Go 2 of the output stage 120 can be NAND gates. If the gate G ( FIG. 1A ) is an AND gate, then the gates Gi 1 and Gi 2 of the input stage 110 can be NAND gates, and the gates Go 1 and Go 2 of the output stage 120 can be NOR gates.

Next, after the step of transforming the gate G ( FIG. 1A ) into the logic block 100 (i.e., steps 180 - 190 of FIG. 1D ), the first logic design method continues with the step of placing each gate of the input stage 110 in a vicinity of the gate's respective inputs and placing each gate of the output stage 120 in a vicinity of the gate's respective outputs (step 192 of FIG. 1D ). “In a vicinity” can be defined in different ways. For instance, a point X can be considered being in a vicinity of points X i , i=1, . . . , L (L is a positive integer) if ΣD i 2 , (i=1, . . . , L) does not exceed a pre-specified value, wherein D i is the distance between X and X i .

In the first example above, with reference to FIG. 1C , gate Gi 1 of the input stage 110 can be placed in a vicinity of its respective inputs A 1 , A 2 , and A 3 . Similarly, the gate Gi 2 of the input stage 110 can be placed in a vicinity of its respective inputs B 1 and B 2 . Similarly, the gate Go 1 of the output stage 120 can be placed in a vicinity of its respective outputs O 1 and O 2 . The gate Go 2 of the output stage 120 can be placed in a vicinity of its respective outputs O 3 , O 4 , and O 5 .

As can be seen in FIG. 1C , the central area surrounded by the inputs A 1 , A 2 , A 3 , B 1 , and B 2 and the outputs O 1 , O 2 , O 3 , O 4 , and O 5 is less crowded because the replacing gates Gi 1 , Gi 2 , Go 1 , and Go 2 are placed close to their inputs or outputs.

FIGS. 2A-2C show logic diagrams used to illustrate a second logic design method, in accordance with embodiments of the present invention. FIG. 2D is a flowchart 299 that illustrates the second logic design method. More specifically, with reference to FIG. 2A , as a second example to illustrate the second logic design method, assume that a two-stage logic 200 comprises a first stage 201 and a second stage 202 . Assume further that the first stage 201 comprises 2 gates F 1 and F 2 (in general, the first stage 201 can comprise T gates, wherein T is a positive integer), and that the second stage 202 comprises an output gate E that is configured to receive input signals from all the 2 gates of the first stage 201 .

In the second example above, assume further that the gate F 1 has five inputs X 1 , X 2 , X 3 , Y 1 , and Y 2 , of which inputs X 1 , X 2 , and X 3 are proximate to each other, and inputs Y 1 and Y 2 are proximate to each other. Assume further that the gate F 2 has five inputs Z 1 , Z 2 , W 3 , W 1 , and V, of which inputs Z 1 and Z 2 are proximate to each other, and inputs W 1 and W 2 are proximate to each other. Assume further that the output gate E has five outputs Q 1 , Q 2 , Q 3 , Q 4 , and Q 5 of which outputs Q 1 , Q 2 , and Q 3 are proximate to each other, and outputs Q 4 and Q 5 are proximate to each other.

With reference to FIG. 2B , in one embodiment, the second logic design method starts with the step of transforming the two-stage logic 200 ( FIG. 2A ) into a logic block 205 which comprises an input stage 210 and an output stage 220 . In one embodiment, the step of transforming the two-stage logic 200 ( FIG. 2A ) into the logic block 205 can comprise the following sub-steps (steps 280 - 284 of FIG. 2D ).

In a first sub-step (step 280 of FIG. 2D ), in one embodiment, all the T gates of the first stage 201 ( FIG. 2A ), i.e., gates F 1 and F 2 in the second example above, are placed in the input stage 210 of the logic block 205 . In other words, the input stage 210 of the logic block 205 can comprise the same gates as the first stage 201 ( FIG. 2A ).

In a next sub-step (step 282 of FIG. 2D ), in one embodiment, the outputs of the output gate E ( FIG. 2A ) can be divided into P output groups of at least two proximate outputs, wherein P is a positive integer. In the second example above, the outputs Q 1 , Q 2 , Q 3 , Q 4 , and Q 5 can be divided into P=2 output groups: (Q 1 , Q 2 , Q 3 ) and (Q 4 , Q 5 ) because Q 1 , Q 2 , and Q 3 are proximate to each other, and because Q 4 and Q 5 are proximate to each other.

In a next sub-step (step 284 of FIG. 2D ), in one embodiment, as a result of the outputs division above, P gates (not shown) corresponding to the P output groups can be placed in the output stage 220 . In one embodiment, each gate of the P gates is (i) functionally equivalent to the output gate E ( FIG. 2A ), (ii) is configured to receive input signals from all the gates of the input stage 210 (i.e., gates F 1 and F 2 ), and (iii) is configured to send output signals to all the outputs of the gate's corresponding output group.

In the second example above, P=2 gates E 1 and E 2 can be placed in the output stage 220 , wherein each of the gates E 1 and E 2 is (i) functionally equivalent to the output gate E, (ii) is configured to receive input signals from both the gates F 1 and F 2 , and (iii) is configured to send output signals to all the outputs of the gate's corresponding output group. More specifically, gate E 1 is configured to send output signals to its outputs Q 1 , Q 2 , and Q 3 . Similarly, gate E 2 is configured to send output signals to its outputs Q 4 and Q 5 .

Next, in one embodiment, the second logic design method further comprises the step of (step 286 of FIG. 2D ), placing each gate of the input stage 210 in a vicinity of the gate's inputs. In the second example above, gate F 1 is placed in a vicinity of its inputs X 1 , X 2 , X 3 , Y 1 , and Y 2 . Similarly, gate F 2 is placed in a vicinity of its inputs Z 1 , Z 2 , W 1 , W 2 , and V.

Next, with reference to FIG. 2C , in one embodiment, the second logic design method further comprises the step of (step 288 of FIG. 2D ), for each gate Fi, i=1, . . . , T of the T gates of the input stage 210 , (a) dividing inputs of the gate Fi into Qi input groups of at least two proximate inputs and Ri individual inputs, wherein Qi and Ri are non-negative integers but are not both equal to zero; (b) replacing the gate Fi by Qi+1 gates, wherein one gate Fi 0 of the Qi+1 gates is located where the gate Fi was, and wherein the other Qi gates of the Qi+1 gates correspond to the Qi input groups; and (c) placing each gate of the other Qi gates in a vicinity of the gate's corresponding input group, wherein each gate of the other Qi gates is configured to receive input signals from all the inputs of the gate's corresponding input group, wherein the gate Fi 0 is configured to receive input signals from all the other Qi gates and from all the Ri individual inputs, and wherein each gate of the P gates of the output stage is configured to receive input signals from all the gates Fi 0 , i=1, . . . , T.

In the second example above, T=2. For gate F 1 ( FIG. 2B ), its inputs X 1 , X 2 , X 3 , Y 1 , and Y 2 can be divided into Q 1 =2 input groups: (X 1 , X 2 , X 3 ) and (Y 1 , Y 2 ). It should be noted that R 1 =0. As a result, gate F 1 ( FIG. 2B ) can be replaced by Q 1 +1=3 gates F 10 , F 11 , and F 12 ( FIG. 2C ), wherein F 10 is located where the gate F 1 was. The gates F 11 and F 12 correspond to and are placed in a vicinity of the input groups (X 1 , X 2 , X 3 ) and (Y 1 , Y 2 ), respectively. The gate F 10 receives signals from gates F 11 and F 12 .

Similarly, for gate F 2 ( FIG. 2B ), its inputs Z 1 , Z 2 , W 1 , W 2 , and V can be divided into Q 2 =2 input groups: (Z 1 , Z 2 ) and (W 1 , W 2 ) and R 2 =1 individual input V. As a result, gate F 2 ( FIG. 2B ) can be replaced by Q 2 +1=3 gates F 20 , F 21 , and F 22 , wherein F 20 is located where the gate F 2 was. The gates F 21 and F 22 correspond to and are placed in a vicinity of the input groups (Z 1 , Z 2 ) and (W 1 , W 2 ), respectively. The gate F 20 receives signals from gates F 21 and F 22 and also from the individual input V.

Next, in one embodiment, the functions of the gates in the input stage 220 are determined (step 290 of FIG. 2D ). In one embodiment, the replacing gates can be functionally equivalent to the gate they replace. More specifically, for i=1, . . . , T, if the gate Fi is an OR gate, then all the Qi gates and the gate Fi 0 can be OR gates; and if the gate Fi is an AND gate, then all the Qi gates and the gate Fi 0 can be AND gates.

In the second example above, if gate F 1 is an OR gate, then gates F 10 , F 11 , and F 12 can be OR gates. If gate F 1 is an AND gate, then gates F 10 , F 11 , and F 12 can be AND gates. Similarly, if gate F 2 is an OR gate, then gates F 20 , F 21 , and F 22 can be OR gates. If gate F 2 is an AND gate, then gates F 20 , F 21 , and F 22 can be AND gates.

Alternatively, in one embodiment, for i=1, . . . , T, if the gate Fi is an OR gate, then all the Qi gates can be NOR gates, and the gate Fi 0 can be a NAND gate; and if the gate Fi is an AND gate, then all the Qi gates can be NAND gates, and the gate Fi 0 can be a NOR gate.

In the example above, if gate F 1 is an OR gate, then F 11 and F 12 can be NOR gates, and the gate F 10 can be a NAND gate; and if the gate F 1 is an AND gate, then gates F 11 and F 12 can be NAND gates, and the gate F 10 can be a NOR gate. Similarly, if gate F 2 is an OR gate, then F 21 and F 22 can be NOR gates, and the gate F 20 can be a NAND gate; and if the gate F 2 is an AND gate, then gates F 21 and F 22 can be NAND gates, and the gate F 20 can be a NOR gate.

Next, in one embodiment, the second logic design method further comprises the step of placing each gate of the output stage 220 in a vicinity of the gate's corresponding outputs (step 292 of FIG. 2D ). In the second example above, gate E 1 is placed in a vicinity of outputs Q 1 , Q 2 , and Q 3 . Similarly, gate E 2 is placed in a vicinity of outputs Q 4 and Q 5 .

As can be seen in FIG. 2C , the central area surrounded by the inputs X 1 , X 2 , X 3 , Y 1 , Y 2 , Z 1 , Z 2 , W 1 , W 2 , and V and the outputs Q 1 , Q 2 , Q 3 , Q 4 , and Q 5 is less crowded because the replacing gates are placed close to their inputs or outputs.

In the embodiments described above, the transformed logic block can comprise one gate (e.g., gate G of FIG. 1A ) or two levels of gates (the two-stage logic 200 of FIG. 2A ). In general, if an original logic block has more than two levels of gates, the original logic block can be first reduced to two levels of gates using any conventional transformation methods. Then, the second logic design method of the present invention can be applied.

FIG. 3 illustrates a flow chart of a logic design method 300 that utilizes the present invention. The logic design method 300 starts with a step 310 in which a circuit is described at a high level (i.e., circuit component diagram). Next, in step 320 , the high level circuit description is synthesized (i.e., converted) into a list of logic gates and their interconnections called a netlist. Next, in step 330 , the locations of the logic gates are determined. Next, in step 340 , the routing scheme and congestion are analyzed. Next, in step 350 , based on the analysis in step 340 , logic blocks with congestion can be identified. Then, in step 360 , the methods of the present invention described in the embodiments above can be applied to the congested logic blocks.

The methods of the present invention can be applied to selective logical blocks during physical design. This does not require synthesis placement iteration.

FIG. 4 illustrates a computer system 90 used for simulating the methods of the present invention. The computer system 90 comprises a processor 91 , an input device 92 coupled to the processor 91 , an output device 93 coupled to the processor 91 , and memory devices 94 and 95 each coupled to the processor 91 . The input device 92 may be, inter alia, a keyboard, a mouse, etc. The output device 93 may be, inter alia, a printer, a plotter, a computer screen, a magnetic tape, a removable hard disk, a floppy disk, etc. The memory devices 94 and 95 may be, inter alia, a hard disk, a floppy disk, a magnetic tape, an optical storage such as a compact disc (CD) or a digital video disc (DVD), a dynamic random access memory (DRAM), a read-only memory (ROM), etc. The memory device 95 includes a computer code 97 . The computer code 97 includes an algorithm for simulating the methods of the present invention ( FIGS. 1D , 2 D, and 3 ). The processor 91 executes the computer code 97 . The memory device 94 includes input data 96 . The input data 96 includes input required by the computer code 97 . The output device 93 displays output from the computer code 97 . Either or both memory devices 94 and 95 (or one or more additional memory devices not shown in FIG. 4 ) may be used as a computer usable medium (or a computer readable medium or a program storage device) having a computer readable program code embodied therein and/or having other data stored therein, wherein the computer readable program code comprises the computer code 97 . Generally, a computer program product (or, alternatively, an article of manufacture) of the computer system 90 may comprise said computer usable medium (or said program storage device).

Thus the present invention discloses a process for deploying computing infrastructure, comprising integrating computer-readable code into the computer system 90 , wherein the code in combination with the computer system 90 is capable of performing a method for simulating the methods of the present invention.

While FIG. 4 shows the computer system 90 as a particular configuration of hardware and software, any configuration of hardware and software, as would be known to a person of ordinary skill in the art, may be utilized for the purposes stated supra in conjunction with the particular computer system 90 of FIG. 4 . For example, the memory devices 94 and 95 may be portions of a single memory device rather than separate memory devices.

While particular embodiments of the present invention have been described herein for purposes of illustration, many modifications and changes will become apparent to those skilled in the art. Accordingly, the appended claims are intended to encompass all such modifications and changes as fall within the true spirit and scope of this invention.