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

Claim 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.

Claim 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 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.

Claim 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 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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.