×

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

  • US 4,777,606 A
  • Filed: 06/05/1986
  • Issued: 10/11/1988
  • Est. Priority Date: 06/05/1986
  • Status: Expired due to Term
First Claim
Patent Images

1. 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 BO 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 Bn 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 Bn +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.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×