US 4,777,606 AGranted

Method for deriving an interconnection route between elements in an interconnection medium

AssigneeNorthern Telecom Limited

InventorSerge Fournier

Life of this patent

Estimating the term…

Loading patent…

Abstract

In a routing method for efficiently routing interconnections of a printed circuit board, an ordered list of interconnections to be made is first developed, each interconnection consisting of a source and a target. The interconnection medium is notionally divided into cells and, in a flooding routine for deriving the route between a particular source and target, cells at a progressively increasing distance from the source are considered. The progressive flooding is performed under a preset control by associating a respective cost with each of a number of possible flooding directions. At any time, flooding occurs from that cell to which the accummulated cost of flooding from the source is a minimum. Eventually a target cell is reached and by tracing backpointer directions associated with the intervening cells, the least cost route is derived as a series of contiguous line segments having position, length and orientation. The same sequence is performed for all interconnections and the line segments are subsequently implemented as circuit board conductors and vias.

A method for deriving an interconnection route between elements in a connection medium, comprising the steps of:

(i) defining:
(a) a cell map comprising a plurality of addressable cells representing grid positions in the connection medium,
(b) a plurality of flags including an empty cell flag, a seed cell flag, a target cell flag, an unavailable cell flag, and a plurality of pointer direction flags, each pointer direction flag having an associated pointer direction and an associated cost;
and
(c) a plurality of cost bins, each cost bin Bn being associated with a cost n and having a plurality of locations for storing data items comprising a cell address and an associated flag;
(ii) writing in software:
(a) unavailable cell flags into cells associated with grid positions not available for routing of an interconnection;
(b) target cell flags into cells associated with grid positions occupied by a target element;
and
(c) data items comprising addresses of cells associated with grid positions occupied by a seed element and associated seed cell flags into a cost bin B.sub.O associated with zero cost;
(iii) and repeating the following steps until a data item containing a cell address corresponding to a cell containing a target cell flag is selected:
(a) scanning the cost bins in order of increasing associated cost until a cost bin B.sub.n containing at least one data item is located:
(b) selecting a data item from said cost bin, and:
(I) if an empty cell flag is stored in the cell corresponding to the cell address contained in said selected data item, said cell being a correspondent cell, overwriting the empty cell flag with the flag of the selected data item, deleting the selected data item from the cost bin and, for each cell adjacent to the correspondent cell other than cells containing unavailable cell flags, writing a data item into cost bin B.sub.n +.sub.m, the data item comprising the address of the adjacent cell and an associated pointer direction flag, the associated pointer direction flag corresponding to a direction from the adjacent cell to the correspondent cell and m being the cost associated with said pointer direction flag;
and
(II) if the flag stored in the cell corresponding to the cell address contained in said selected data item is a pointer direction flag, deleting said selected data item from the cost bin;
wherein the derived interconnection route comprises a path from the selected cell containing a target cell flag to a cell containing a seed cell flag through intermediate cells following directions corresponding to pointer direction flags stored in said intermediate cells.

14 more elements

Abstract

Claims13