1. Field of the Invention
The present invention relates to a method of optimizing a logic circuit for achieving optimal connection of driver gates, and more particularly to a method of optimizing a logic circuit to ensure reduction in total length of interconnections, delay and routing area of an LSI.
2. Description of the Background Art
A buffer tree refers to a logic circuit in which positive-logic and inverted-logic driver gates are connected like a tree shown in FIG. 13. In the buffer tree, an output signal from a gate is input to a plurality of other gates. Therefore, the buffer tree is added to the output of a gate in such a logic circuit as can not be driven by the driving capability of a single gate. Many logic circuits in data-bus system with a large bit width need the buffer tree.
Many logic circuits in data-bus system have symmetric circuit configurations. Effective utilization of this symmetric configuration allows a layout with a small routing area and high gate utilization. For higher gate utilization, it is needed to construct the buffer trees to be in a symmetrical relation.
A logic synthesis tool receives a logic description and automatically synthesizes a logic circuit in correspondence with the logic description. If the input logic description has a symmetry in logic structure, the synthesized logic circuit normally has a symmetry. The buffer tree, however, is a logic circuit to be added to honor the restrictions on the number of fanouts and driving capability and hence is unrelated to the logic structure of the whole circuit. The logic synthesis tool applies the buffer tree to the circuit without taking the symmetry in logic structure of the whole circuit into account. Therefore, some eventually-obtained logic circuit with the buffer tree loses the symmetry.
Discussion will be presented taking a logic circuit having symmetric logic structures shown in FIG. 14 as an example. Square blocks shown in FIG. 14 represent gates. Logic structures GX' (X=0, 1, 2, 3) are in a symmetrical relation with one another. Names in the blocks (SEL, FF) denote the kinds of gates. Names under the blocks (UX, FX) are gate names for distinguishing the gates. Solid lines represent interconnections which connect the gates. Names near the contacts between the interconnections and the blocks (A, B, S, Y of SEL and D, CL, Q of FF) denote pins of the gates. Arrowheads on the left and right sides represent input and output pins, and names near the arrowheads (clk, sel, a[X], b[X], y[X]) are input/output pin names.
Now discussed will be a case of addition of buffer trees in a balance-tree shape using two positive-logic driver gates BX to the input pins sel and clk of the logic circuit of FIG. 14. FIG. 15 illustrates an exemplary addition of buffer trees in a symmetrical relation. FIG. 16 illustrates an exemplary addition of buffer trees out of a symmetrical relation. The logic synthesis tool synthesizes either of the logic circuits of FIGS. 15 and 16 based on judgment that both logic circuits of FIGS. 15 and 16 output the same result. Names shown in FIGS. 15 and 16 correspond to those in FIG. 14.
A difference between the two logic circuits of FIGS. 15 and 16 is found after placement. FIGS. 17 and 18 illustrate layouts after placement of the logic circuits of FIGS. 15 and 16, respectively. The logic circuits shown herein are optimally placed by the Min-Cut method which is an ordinary method of placement algorithm. In the Min-Cut method, the placement is evaluated by the total number of interconnections crossing cut lines. Heavy lines of FIGS. 17 and 18 represent the cut lines. The number of interconnections crossing a cut line is shown on the underside or rightside of the cut line. The total number of interconnections crossing the cut lines in the logic circuit of FIG. 17 is thirty-two and that of FIG. 18 is thirty-four. The logic circuit of FIG. 17 has better placement result. Only the interconnections between the gates B0, B2 and the gates U1, U2 contribute to the difference between the two placement results. The interconnections between these gates do not cross the center cut line in a horizontal direction in FIG. 17, while those in FIG. 18 do. More interconnections crossing a cut line result in congested channels near the cut line, and that makes it difficult to compact the routing area by compaction function of a layout tool. As can be seen from FIGS. 17 and 18, the routing of FIG. 18 is more complicate and the total length of interconnections of FIG. 18 is longer. An increase in total length of interconnections results in an increase in delay.
Thus, since the logic synthesis tool performs addition of the buffer trees without taking the symmetry in logic structure into account, it may disadvantageously result in an increase in total length of interconnections, routing area and delay in the circuit after placement. One of the methods relating to restructuring of buffer trees is shown in "Routability-Driven Fanout Optimization" (Proc. of 30th DAC, pp. 230-235). In the logic synthesis using this method, placement of logic circuits is made before addition of buffer trees and optimization of the buffer trees is performed in accordance with the placement result. However, the buffer trees are not optimized so as to be in a symmetrical relation by this method.