Channel routing method

• US 5,272,645 A
• Filed: 05/22/1991
• Issued: 12/21/1993
• Est. Priority Date: 05/24/1990
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Kawakami, Yoshiyuki, Toyonaga, Masahiko
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/704,181
• Time in Patent Office: 944 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/126
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A plurality of wires are effectively laid in a channel having a plurality of wiring layers and sandwiched between two rows of terminals. In order to complete channel routing, horizontal segments of the wires are initially generated. The horizontal segments are then allocated on at least one imaginary segment generated on each layer contained in the channel. The imaginary segment is in parallel with the rows of terminals in the channel. The horizontal segments are bent for reduction of the channel height based on design rules for each layer. Finally, vertical segments of the wires are generated.

Claims

1. A computer implemented channel routing method for determining the layout of a plurality of wires in a channel having a plurality of layers formed therein and sandwiched between two rows of terminals, said method comprising the steps of:

(a) generating horizontal segments required for completing a wiring in the channel;

(b) allocating said horizontal segments on at least one imaginary segment generated on each layer contained in the channel, said imaginary segment being in parallel with the rows of terminals in the channel;

(c) bending said horizontal segments for reduction of a channel height based on design rules for each layer; and

(d) generating vertical segments of the wires;

said step (b) comprising the steps of;

(b1) determining an allocation order of said horizontal segments based on a positional relationship among said terminals;

(b2) selecting from said horizontal segments candidates which can be allocated on a single imaginary segment;

(b3) calculating a longest path length on an expanded vertical constraint graph required for completing the channel routing;

(b4) estimating in advance a channel height required for completing the channel routing;

(b5) enumerating locations of wiring densities greater than a given value, said wiring density being equal to a sum of widths of said horizontal segments and intervals between said horizontal segments along a vertical segment lying between said rows of terminal;

(b6) calculating a degree of crossing between each horizontal segment and vertical segments having respective wiring densities;

(b7) calculating an attraction of each horizontal segment toward one of an upper wide and a lower side of the channel;

(b8) calculating a degree of allocation priority of each horizontal segment; and

(b9) selecting horizontal segments from said candidates and allocating selected horizontal segments on said imaginary segment based on a result obtained at at least one of said steps (b3), (b6), (b7), and (b8), and

wherein said steps (b1) to (b9) are repeated until said horizontal segments are all allocated.