High speed machine for the physical design of very large scale integrated circuits

• US 4,484,292 A
• Filed: 06/12/1981
• Issued: 11/20/1984
• Est. Priority Date: 06/12/1981
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shapiro, Eugene, Nair, Ravindra K., Hong, Se J.
• Primary Examiner(s): Gruber, Felix D.
• Assistant Examiner(s): Cosimano, Edward R.
• Application Number:
  US06/272,880
• Time in Patent Office: 1,257 Days
• Field of Search: 361/428, 364/488, 364/489, 364/490, 364/491, 364/520, 364/300, 364/579, 364/580, 364/200, 364/900
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Method and apparatus for the physical design of very large scale integrated (VLSI) circuits, and in particular the interconnection and wire routing between circuits formed on a chip. Apparatus is set forth for determining the wire routings in a VLSI circuit comprised of cells, wherein the cells are composed of electronic devices functioning as logic gates. Groups of cells may be interconnected to function as flip flops, shift registers and the like. A supervisory controller communicates with n, where n is an integer, identical multi-port processors, with one processor dedicated to each cell, for determining the wire routings between the respective cells. Each processor communicates simultaneously with its four adjacent neighbor processors to determine channel routings from one point to the next in the array of cells, wherein a channel routing includes vertical and horizontal paths. Following determination of global channel routings, exact vertical and horizontal tracks for the wire paths are assigned. The array or processors may be utilized to wire a much larger array of cells.

Claims

1. In a system for determining wire routings between terminals on a master-slice chip, wherein a plurality of devices are formed on said chip, with a plurality of mutually orthogonal horizontal and vertical wiring channels formed on said chip, with a plurality of wiring tracks being formed in each channel, with said devices and channels forming an array of cells, with said terminals being placed along the wiring tracks in at least one of the horizontal and vertical wiring channels, the combination comprising:

an array of processing elements, equal in number to at least a submultiple of the number of cells formed on said chip, said processing elements including at least four input/output ports for communicating with at least four neighbors in said array of processing elements, including a control input/output port;

a control processor for selectively providing commands to said control input/output port of each said processing element in said array to concurrently determine the wire routing from a plurality of source terminals to a plurality of sink terminals on said chip; and

means in each of said processing elements for responding to said commands from said control processor and communications from said four neighbors to first determine the best channel routings from said source terminals to said sink terminals, and then to determine the best wiring track in each of said best channel routings.

2. The combination claimed in claim 1, including:

means, in each of said processing elements, for computing a wire routing congestion estimate for each channel in each of the four directions from each cell.

3. The combination claimed in claim 2, including:

means, in each of said processing elements, for computing port costs for each of the ports of a given processing element based on the number of unused tracks and the congestion estimate at each port, wherein port cost is defined as the penalty for occupying a given track in a given direction.

4. A method of determining wire routings between terminals on a master-slice chip, wherein a plurality of devices are formed on said chip, with a plurality of mutually orthogonal horizontal and vertical wiring channels being formed on said chip, with a plurality of wiring tracks being formed in each channel, witn said devices and channels forming an array of cells, with said terminals being placed along the wiring tracks in at least one of the horizontal and vertical wiring channels, with a net being defined as a set of at least two terminals that have to be connected together, including an array of processing elements, equal in number to at least a submultiple of the number of cells formed on said chip, said processing elements including at least four input/output ports for communicating with at least the four adjacent neighbors in the array of processing elements, and including a control input/output port, with a control processor for selectively providing commands to said control input/output port of each said processing elements in said array of processing elements to concurrently determine the wire routings from a plurality of source terminals to a plurality of sink terminals, said method comprising the steps of:

computing, for each net to be wired, and for each cell, the likelihood of said cell being a member of a connection in said net;

computing a wire routing congestion estimate for each channel in each of the four directions from a given cell;

designating one of the terminals of a net as the source terminal and at least one other terminal in the net as the sink terminal;

determining the best wiring channel from said source terminal to said sink terminal; and

determining the best wiring track in said wiring channel.

5. A method of determining wire routings between terminals on a master-slice chip, wherein a plurality of devices are formed on said chip, with a plurality of mutually orthogonal horizontal and vertical wiring channels being formed on the chip, with a plurality of wiring tracks being formed in each channel, with said devices and channels forming an array cells, with said terminals being placed along the wiring tracks in at least one of the horizontal and vertical wiring channels, with a net being defined as a set of at least two terminals that have to be connected together, with port cost being defined as the penalty for occupying a given track in a given direction, including an array of processing elements, equal in number to at least a submultiple of the number of devices formed on said substrate, said processing elements each including at least four input/output ports for communicating with at least the four adjacent neighbors in the array of processing elements, and including a control input/output port, with a control processor for selectively providing commands to said control input/output port of each said processing elements in said array of processing elements to concurrently determine the wire routing from a plurality of source terminals to a plurality of sink terminals, said method comprising the steps of:

(a) computing, for each net to be wired, and for each cell, the likelihood of said cell being a member of a connection in said net;

(b) following step (a), steps (c) through (g) are performed for the first net and then is iterated net by net until all of the nets are wired;

(c) subtracting by a given processing element for a given net, said given processing elements contribution to the congestion estimate from the total remaining congestion estimate;

(d) computing port costs for each of the ports of a given processing element based on the number of unused tracks and the congestion estimate at each port;

(e) designating the cell associated with one of the terminals as the source cell, and designating the cells which contain the remaining terminals of the net as the sink cells;

(f) determining the best wiring channel from said source cell to one of said sink cells; and

(g) designating all cells in all the best channel routes so far formed for the net as source cells for the next iteration.

6. A method of determining wire routings between terminals on a master-slice chip, wherein a plurality of devices are formed on said chip, with a plurality of mutually orthogonal horizontal and vertical wiring channels being formed on the chip, with a plurality of wiring tracks being formed in each channel, with said devices and channels forming cells in an N by M array which may be divided into n by m frames, where n<

N and m<

M, with said terminals being placed along the wiring tracks in at least one of the horizontal and vertical wiring channels, with a net being defined as a set of at least two terminals that have to be connected together, with port cost being defined as the penalty for occupying a given track in a given direction, including an n by m array of processing elements, said processing elements including at least four input/output ports for communicating with at least the four adjacent neighbors in the array, and including a control input/output port, with a control processor for selectively providing commands to said control input/output port of each said processing elements in said array to concurrently determine the wire routing from a plurality of source terminals to a plurality of sink terminals, an n by m frame at a time, said method comprising the steps of;

(a) computing, for each net to be wired, and for each cell, the likelihood of said cell being a member of a connection in said net;

(b) following step (a) for all nets having been completed, steps (c) through (g) are performed for the first net and then is iterated net by net until all of the nets are wired;

(c) subtracting by a given processing element for a given net, said processing element'"'"'s contribution to the congestion estimate from the total remaining congestion estimate;

(d) computing port costs for each of the ports of a given processing element based on the number of unused tracks and the congestion estimate at each port;

(e) designating the cells associated with one of the terminals as the source cell, and designating the cells which contain the remaining terminals of the net as the sink cells;

(f) determining the best wiring channel from said source cell to said sink cell;

(g) designating all cells in all the best channel routes so far formed for the net as source cells for the next iteration; and

(h) repeating steps (a) through (g) for each n by m frame in said N by M array.