Efficient method for multichip module interconnect

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

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