Work ordering routine for use in a method of routing

• US 4,858,143 A
• Filed: 09/25/1986
• Issued: 08/15/1989
• Est. Priority Date: 09/25/1986
• Status: Expired due to Term

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Bell-Northern Research Ltd. (Nortel Networks Corporation)
• Inventors: Fournier, Serge
• Primary Examiner(s): Lall, P. S.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/911,386
• Time in Patent Office: 1,055 Days
• Field of Search: 364/488-491, 357/40, 357/45
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

In a routing method for efficiently routing the interconnections of a printed circuit board, the list of interconnections to be made is ordered to provide a work order for deriving routes. The circuit board is notionally divided into a grid of addressable cells. Then grid lines are considered in turn. A particular grid line may have a certain number (x) of cells that are full and so cannot be used for routing and other cells which are empty and so available for routing (capacity). If all interconnections to be made were made by direct spans then that particular grid line would have grid crossings occupying a certain number (y) of cells (occupancy). A MAOMIC (maximum occupancy-minimum capacity) product of that grid line is derived. When assigning routes, the routes of those interconnections which, if directly made, would cross the grid line of highest MAOMIC product are assigned first.

Claims

1. A method, to be carried out by a computer, of deriving routes of interconnections between elements in a connection medium, comprising the steps of:

generating a cell map consisting of a number of addressable cells representing grid positions in the connection medium;

designating certain of the cells which can accommodate routes as empty and designating remaining ones of the cells which cannot accommodate routes as full;

counting the number of empty cells in each of a plurality of rows of cells and columns of cells to define a capacity for each row and each column;

counting the number of cells in each row and each column which would be crossed by an interconnection if each interconnection extended along a straight line linking elements to be interconnected to define an occupancy for each row and each column;

dividing each row and column occupancy by a corresponding capacity to define a MAOMIC product for each row and each column;

comparing the MAOMIC products of each row and each column crossed by each straight line interconnection and storing the maximum MAOMIC product for each straight line interconnection; and

deriving routes for said interconnections in descending order of the MAOMIC products associated with said interconnections.

2. A method as claimed in claim 1 in which the routes have a predetermined width and a minimum permitted spacing so that a maximum number of routes are permitted to pass perpendicularly across each column of cells and a maximum number of routes are permitted to cross each row of cells, and wherein the number of cells in each column of cells equals the maximum number of routes permitted to cross that column of cells and the number of cells in each row of cells equals the maximum number of routes permitted to cross that row of cells.

3. A method as claimed in claim 1 wherein the cells represent square regions in the connection medium.

4. A method as claimed in claim 1 particularly for routing connections between elements in an electrical circuit in which several elements of the circuit can have a common signal applied thereto, the method comprising running a minimum spanning tree routine to select from n disconnections between n elements having a common signal (n-1) interconnections, said (n-1) interconnections having an aggregate direct interconnection span length which is a minimum aggregate length for connecting said n elements.