Several approaches are known in the art of LSI circuit layout design for distributing the components of a network so that the available substrate area is well utilized and the placement of the components is advantageous for interconnecting them by conducting lines. Also known are several techniques for establishing a wiring pattern between given elements or circuits and the available input/output terminals on a substrate.
Some publications in this field disclose methods for partitioning a given surface and for assigning circuits or components that are to be accomodated to the dissected areas according to certain criteria. Representative articles are the following:
M. A. Breuer "Min-Cut Placement", Journal of Design Automation and Fault-Tolerant Computing, October 1977, pp. 343-362. PA1 L. R. Corrigan "A Placement Capability Based on Partitioning", Proc. 16th DA Conference, June 1979, pp. 406-413. PA1 S. J. Hong, R. Nair, E. Shapiro "A Physical Design Machine" Proceedings International Conference VLSI-81, Edinburgh, August 1981, pp. 267 ff. PA1 R. Nair, S. J. Hong, S. Liles, R. Villani, "Global Wiring on a Wire Routing Machine", Proc. 19th DA Conference, Las Vegas 1982, pp. 224-231.
These articles describe procedures for successively partitioning a given surface area by cut-lines into subsections of decreasing size and for then distributing or placing elements in such a way on both sides of each new cut-line that the number of signals which have to cross the cut-line is minimized. Advantages are gained for the subsequent design of the wiring pattern if the circuit elements are placed in this manner because the wiring length or density tends to be decreased. However, as the placement considers only specific local situations one at a time, the overall result of the final wiring process is not yet optimal.
For improving the design of the wiring pattern interconnecting elements that are already placed on a given-surface, suggestions were made in the following articles:
The suggested procedures find best wiring routes between terminals of processing elements in a given placement distribution and thus help in designing a good wiring pattern. However, the influence of the initial element placement distribution on the subsequent wiring procedures is not considered so that an overall optimization may not be achieved.
An article entitled "Hierarchical Channel Router" by M. Burstein et al, was published in Vol. 1, No. 1 Integration 1983 and also in the Proceedings of the 20th Design Automation Conference at Miami Beach, 1983. The article disclosed a 2.times.n routing algorithm similar to the 2.times.n wiring algorithm which forms a part of the method of the present invention. However, the article did not disclose any method for placement of components or for wiring in a master-slice VLSI layout.
As will be seen from a consideration of the prior art, traditional approaches to VLSI layout design consist of two independent stages: (1) placement of components and (2) wire routing. Such approaches may not result in an appropriate optimum layout, even if powerful placement and wiring techniques are applied. One of the main disadvantages of traditional layout processes is that there are no known universal criteria for placement.