Method for routing

Claim 1

A method of deriving interconnection routes between elements in a connection medium, comprising the steps of: i) generating a cell map comprising a number of addressable cells representing grid positions in the connection medium, the method characterized by:- ii) storing a plurality of pointer directions according to permissible route segment orientations, each of the pointer directions having an associated cost; iii) setting up a series of cost bins from a least cost bin upwards, each bin for storing data items having a cell address and an associated pointer direction; iv) for a list of interconnections, designating certain of the addressable cells which can accommodate routes as empty and designating other cells which cannot accommodate routes as full; v) selecting an interconnection having source and target elements each made up of a number of connected cells; vi) assigning the source cell addresses to a 0 cost bin; vii) selecting a cell from the least cost (n) bin containing cell addresses and entering its pointer direction in the corresponding address of the cell map; viii) considering cells immediately adjacent to the selected cell; ix) assessing a backpointer direction for each considered cell, being a direction back to the selected cell from the considered cell; x) if the considered cell is in the source element placing the cell address in the cost n bin and if the considered cell is empty and has a pointer direction of cost m, placing the cell address in the cost (n + m) bin; xi) repeating the steps (vii) to (x) for each cell listed in the cost n bin; xii) repeating the step (xi) for progressively higher cost bins until a target cell is selected; xiii) retracing backpointers from the target cell to the source; xiv) recording the route of said retraced pointers; xv) repeating steps (v) to (xiv) for other interconnections.

Claim 2

A method of deriving interconnection routes between elements in a connection medium, comprising the steps of: i) generating a cell map comprising a number of addressable cells representing grid positions in the connection medium, the method characterized by:- ii) storing a plurality of pointer directions according to permissible route segment orientations, each of the pointer directions having an associated cost; iii) setting up a series of cost bins from a least cost bin upwards, each bin for storing data items having a cell address and an associated pointer direction; iv) for a list of interconnections, designating certain of the addressable cells which can accommodate routes as empty and designating other cells which cannot accommodate routes as full; v) selecting an interconnection having source and target elements each made up of a number of connected cells; vi) assigning the source cell addresses to a 0 cost bin; vii) selecting a cell from the least cost (n) bin containing cell addresses and entering its pointer direction in the corresponding address of the cell map; viii) considering cells immediately adjacent to the selected cell; ix) assessing a backpointer direction for each considered cell, being a direction back to the selected cell from the considered cell; x) if the considered cell is in the source element placing the cell address in the cost n bin and if the considered cell is empty and has a pointer direction of cost m, placing the cell address in the cost (n + m) bin; xi) repeating the steps (vii) to (x) for each cell listed in the cost n bin; xii) repeating the step (xi) for progressively higher cost bins until a target cell is selected; xiii) retracing backpointers from the target cell to the source; xiv) recording the route of said retraced pointers; xv) repeating steps (v) to (xiv) for other interconnections.