Efficient method for multichip module interconnect

Abstract

A method for interconnecting integrated circuits (ICs) mounted on a multichip module so as to minimize spacing between the ICs and maximize their density. A multichip module (20,80) includes a plurality of ICs (22,82) that are mounted on a substrate (24,84). The ICs are electrically connected to pads (28), spaced apart from each other and offset from the boundaries of the ICs to define vertical routing channels (35) and horizontal routing channels (42). The horizontal routing channel includes a top routing channel (36), a bottom routing channel (38), and a central routing channel (40). Initially, a minimal number of tracks are provided in the central routing channel. Each pad has an electrical connection point or pin (44,46) associated with it and the pins are organized into nets. The method provides for dividing the nets into two pin subnets. Each subnet in the horizontal routing channel is assigned to a vertical track so as to minimize violation of a constraint graph. Horizontal tracks are assigned to the subnets so as to minimize an associated element in a COST matrix of subnets and tracks. The method uses a conventional maze router approach to connect pins in subnets not otherwise connected. If any subnet then still remains unconnected, an additional track is added to the central routing channel and the steps of method are then repeated. Use of the top and bottom routing channels reduces the need for routing interconnections through the central routing channel and thus allows the ICs to be mounted more closely together.

The invention in which an exclusive property or privilege is claims is defined as follows: 
     
       1. A method for interconnecting a plurality of integrated circuits that are mounted on a substrate to form a multichip module so as to maximize a density of the integrated circuits on the substrate, terminals on each integrated circuit being electrically connected to a plurality of pads disposed in a spaced apart array within routing channels defined between boundaries of adjacent integrated circuits, each routing channel including a central routing channel defined between the pads of the adjacent integrated circuits, and side routing channels defined between the pads and the adjacent boundaries of the integrated circuits, crossover regions being defined where the routing channels transversely cross each other, the pads including a plurality of pins that must be interconnected, the method comprising the steps of: a. defining a plurality of two pin subnets that must be interconnected;   b. assigning each subnet to a track within the routing channels so as to maximize the use of the side routing channels and minimize the use of the central routing channels, subject to a plurality of constraints, including: i. subnets are not assigned to a track if such assignment would cause overlap with subnets that are not to be interconnected;   ii. jogged interconnection of pins in each subnets is accomplished with a minimum number of jogs; and     c. additional tracks are added to the central routing channel only if required to interconnect pins in any subnet remaining unconnected after step (b).   
     
     
       2. A method for electrically interconnecting a plurality of integrated circuits that are attached to a substrate forming a multichip module, the integrated circuits being interconnected by conductive traces defined in a plurality of layers applied to the substrate outside boundaries of the integrated circuits, the conductive traces extending along generally orthogonal vertical and horizontal tracks in different layers, each integrated circuit having a plurality of terminals that are electrically connected to a corresponding plurality of pads disposed in a spaced apart array outside the boundaries of that integrated circuit, routing channels between the integrated circuits including variable width central routing channels defined between the pads of adjacent integrated circuits and side routing channels defined between the pads and the boundaries of the integrated circuits, the method being applied to interconnect the pads of the plurality of integrated circuits so as to minimize the width of the central routing channels between the adjacent integrated circuits on the multichip module, the method comprising the steps of: a. defining a plurality of pins to be electrically interconnected, each pin comprising a point on one of the pads;   b. defining a plurality of nets, each net comprising the pins that are to be electrically interconnected;   c. dividing each net into a plurality of two-pin subnets;   d. for each routing channel that is horizontal, moving horizontally in a preferred direction to successive vertical tracks and at each vertical track, assigning a specific horizontal track to each subnet that has one pin in that vertical track and another pin in a vertical track that is offset in the preferred direction, giving preference to assigning horizontal tracks in the side routing channels, so as to minimize violations of the following constraints: i. subnets of different nets that lie along a common vertical track can not lie in overlapping horizontal tracks;   ii. subnets of different nets that lie along a common vertical track can not overlap along that common vertical track;     e. for subnets including pins that can not be interconnected without violating the constraints in steps (d)(i) and (d)(ii), either modifying the position of at least one of the pins comprising such subnets to avoid violation of said constraints, or interconnecting the pins of such subnets using additional horizontal and vertical tracks to form a jogged path, subject to the constraint of assigning horizontal and vertical tracks to said pins so that pins comprising each subnet are interconnected using a minimum number of additional horizontal and vertical tracks;   f. logically orienting the multichip module so that the horizontal tracks are treated as vertical tracks and the vertical tracks are treated as horizontal tracks; and   g. repeating steps (d) and (e) in respect to the logical orientation in step (f), whereby the vertical tracks are treated as horizontal tracks and the horizontal tracks are treated as vertical tracks while repeating steps (d) and (e).   
     
     
       3. The method of claim 2, wherein a crossover region is defined where two orthogonal routing channels cross, and wherein the crossover region includes boundary pins aligned generally horizontally along opposite edges of one of the two routing channels where it crosses the other routing channel, further including the step of temporarily assigning a vertical track aligned with one of the boundary pins to each subnet passing over the boundary pins. 
     
     
       4. The method of claim 3, wherein after logically orienting the multichip module, each subnet having the temporarily assigned vertical track that is aligned with one of the boundary pins retains its previously assigned horizontal track, but is subject to reassignment to a different track through another boundary pin, in accordance with steps 1(d) and 1(e). 
     
     
       5. The method of claim 3, wherein a "cost" is associated with each horizontal track that can be assigned to each subnet, based upon the conformance of the assignment to the constraints in steps 1(d) and 1(e), and wherein the step of assigning the horizontal track comprises the step of selecting the horizontal track that minimizes the cost. 
     
     
       6. The method of claim 3, wherein the step of assigning horizontal tracks to subnets in step 1(e) includes the step of shifting pins disposed within the crossover region horizontally to avoid overlap of vertical tracks for subnets of different nets. 
     
     
       7. The method of claim 3, wherein step 1(e) includes the step of shifting pins that are disposed in the crossover region and vertically aligned to avoid overlap of horizontal tracks assigned to subnets of different nets. 
     
     
       8. The method of claim 2, wherein assigning horizontal tracks in step 1(e) includes the step of positioning the pads so that the side routing channels overlap between adjacent integrated circuits. 
     
     
       9. The method of claim 2, wherein step 1(d) includes the step of alternating the preferred direction in first one direction and then in an opposite direction so that the sequence of vertical tracks extends first in said one direction and then in said opposite direction, thereby reducing a total track length required for interconnection of the pins comprising at least some of the subnets. 
     
     
       10. The method of claim 2, wherein step 1(e) includes reassigning horizontal tracks to subnets to enable interconnection of pins comprising subnets that could not otherwise be interconnected without violating the constraints. 
     
     
       11. The method of claim 2, wherein step 1(e) is effected by a maze routing procedure. 
     
     
       12. A method for interconnecting a plurality of integrated circuits that are mounted on a substrate to form a multichip module so as to minimize spacings between the integrated circuits on the multichip module, terminals on each integrated circuit being electrically connected to a plurality of pads disposed in a spaced apart array within routing channels that extend both vertically and horizontally between boundaries of adjacent integrated circuits, each routing channel including a central routing channel defined between the pads of adjacent integrated circuits, and side routing channels defined between the pads and the boundaries of the integrated circuits, the vertical and horizontal routing channels crossing in crossover regions that include vertical pins, which are aligned vertically, and boundary pins disposed along the edges of the crossover region, the routing channels including a plurality of internal pins that are disposed outside of the crossover region, the vertical pins and the internal pins being electrically connected to the pads, a plurality of horizontal tracks and a plurality of vertical tracks disposed in the routing channels being available to interconnect the internal and vertical pins in a plurality of nets, each net including vertical and internal pins connected in common, the method comprising the steps of: a. dividing a total number of pins, N, in each net, into N-1 subnets, each subnet comprising two pins that must be interconnected;   b. determining the routing channels for each subnet, including the crossover regions, if any, through which the two pins comprising the subnets must be interconnected;   c. for any two internal pins not in the same net that lie in a common vertical track, shifting at least one of said two internal pins horizontally by at least one vertical track;   d. for any two vertical pins not in the same net that lie in a common horizontal track, shifting at least one of the two vertical pins vertically closer to a center of the side channel in which that vertical pin is disposed;   e. for each horizontal routing channel, determining a preferred relative order in which the horizontal tracks contained therein should be assigned to the subnets comprising at least one pin disposed within that horizontal routing channel, from one boundary of the horizontal routing channel to the other, so that subnets of different nets that lie in a common vertical track in the routing channel do not lie in overlapping horizontal tracks and so that subnets of different nets that lie in a common vertical track within the routing channel do not overlap along that common vertical track;   f. assigning a horizontal track to each of the subnets within each horizontal routing channel so as to minimize a cost associated with that assignment, where the cost is less for horizontal tracks that are in the side routing channels and greater for horizontal tracks that are in the center routing channels;   g. interconnecting pins comprising subnets not yet connected following step (f) by using additional vertical and horizontal tracks to form a jogged interconnect pattern that avoids interconnecting to subnets of different nets;   h. logically orienting the multichip module so that horizontal and vertical routing channels are treated as vertical and horizontal and vertical routing channels, respectively, and horizontal and vertical tracks are treated as vertical and horizontal tracks, respectively; and   i. repeating steps (e) through (g) in respect to the logical orientation of the multichip module in step (h).   
     
     
       13. The method of claim 12, wherein the step of determining the preferred relative order comprises the step of constructing a vertical constraint graph, G(V,E), wherein V represents a set of all the subnets considered and E is a set of directed edges, each directed edge having a subnet V i  that includes a pin in a horizontal track above a horizontal track in which a pin of a subnet V j  is disposed with no other pin disposed between the pin of subnet V i  and the pin of subnet V j , thereby defining a relative order V i , V j  in respect to those subnets. 
     
     
       14. The method of claim 12, wherein the step of assigning horizontal tracks comprises the step of developing a cost matrix having M rows and N columns, where M is the number of subsets being considered and N is the number of horizontal tracks in the horizontal routing channel. 
     
     
       15. The method of claim 14, wherein a cost associated with assigning a specific horizontal track in the horizontal routing channel to a specific subnet comprises an element of the cost matrix and wherein the cost for each element of the cost matrix is a sum of a first quantity and a second quantity, the first quantity being selected to give a preference to assigning a horizontal track disposed in the side routing channels to the specific subnet, and the second quantity being set equal to one of a plurality of predetermined values having successively smaller relative magnitudes, as follows: a. a first value that is the largest of the predetermined values is used, if assigning the specific track for the subnet would cause an overlap with the subnet of a different net;   b. a second value that is the next smaller predetermined value than the first value is used, if assigning the specific track for the subnet would cause conflicts with subnets already assigned the specific horizontal track;   c. a third value that is the next smaller predetermined value than the second value is used, if the specific horizontal track can not be accessed by the pins comprising the subnet; and   d. a fourth value that is the smallest of the predetermined values is used, if the specific track can be assigned to the subset without conflict with other subnets.   
     
     
       16. The method of claim 15, wherein the first quantity varies depending upon the total number of horizontal tracks available in the horizontal routing channel and the location of the pins comprising the subnet. 
     
     
       17. The method of claim 15, wherein the plurality of predetermined values are selected to weight the assignment of the horizontal track to each subnet to achieve the minimum cost for the horizontal track assigned to each subnet. 
     
     
       18. The method of claim 12, further comprising the step of reassigning horizontal tracks to subnets in order to connect pins comprising subnets that have not been successfully connected after step 11(i). 
     
     
       19. The method of claim 12, further comprising the step of adding a horizontal track to enable interconnection of pins comprising subsets that have not been successfully connected after step 11(i). 
     
     
       20. The method of claim 12, wherein the step of determining the preferred relative order includes the steps of selecting a starting pin and alternating directions while moving to successive vertical tracks, first in one direction, and then in the opposite direction, so that for each subnet having a pin in one vertical track and another pin in a different vertical track that is offset in the last direction moved, the preferred order of the subnet is determined. 
     
     
       21. The method of claim 12, further comprising the step of mounting the integrated circuits on the substrate so as to shift the routing channels between two of the integrated circuits out of alignment with the routing channel disposed between two other adjacent integrated circuits, thereby increasing the number of horizontal tracks available for assignment to the subnets.