Back to results
US 7,073,155 B1Granted
Method for computing and using future costing data in signal routing
AssigneeXilinx, Inc.
InventorsRaymond Kong, Jason H. Anderson
Life of this patent
Estimating the term…
Abstract
A systematic method for calculating future cost is disclosed. Pre-routing is performed from a source node to other nodes through a series of neighboring nodes. At each node in the pre-routing, the cumulative routing cost and Manhattan distance are calculated. This cumulative routing cost is used as a new future cost for a specific distance if it is lower than or there is no existing future cost for that distance. A table can be used to store the future cost data. During routing, the recorded future cost is added to the cumulative cost of a node to help guide the routing, improving router run-time.
Claims13
A method for establishing future cost values for use in routing signals of a circuit design on an integrated circuit, comprising:
- selecting a pre-routing source node from a graph of nodes that represents conductors in a device;
- determining for each node in the graph, a respective minimum future cost value as a function of a cumulative cost of nodes on a path from the pre-routing source node to the node;
- and
- storing each future cost value in a location that is addressable as a function of a distance from the node from which the future cost value was determined to the pre-routing source node, wherein the storing step includes, establishing a two-dimensional table for storage of the future cost values;
- determining a Manhattan distance from the node from which the future cost value was determined to the pre-routing source node;
- and storing each future cost value in the two-dimensional table at a location indexed by the Manhattan distance.
3 more elements
An apparatus for establishing future cost values of for use in routing signals of a circuit design on an integrated circuit, comprising:
- means for selecting a pre-routing source node from a graph of nodes that represents conductors in a device;
- means for determining for each node in a graph a respective minimum future cost value as a function of a cumulative cost of nodes on a path from the pre-routing source node to the node;
- and
- means for storing each future cost value in a location that is addressable as a function of a distance from the node from which the future cost value was determined to the pre-routing source node, wherein the storing step includes, mean for establishing a two-dimensional table for storage of the future cost values;
- mean for determining a Manhattan distance from the node from which the future cost value was determined to the pre-routing source node;
- and mean for storing each future cost value in the two-dimensional table at a location indexed by the Manhattan distance.
3 more elements
A method for routing signals of a circuit design on an integrated circuit, comprising:
- selecting a pre-routing source node from a graph of nodes that represents conductors in a device;
- determining for each node in the graph, a respective minimum future cost value as a function of a cumulative cost of nodes on a path from the pre-routing source node to the node;
- storing each future cost value in a location that is addressable as a function of a distance from the node from which the future cost value was determined to the pre-routing source node, wherein the storing step includes, establishing a two-dimensional table for storage of the future cost values;
- determining a Manhattan distance from the node from which the future cost value was determined to the pre-routing source node;
- and storing each future cost value in the two-dimensional table at a location indexed by the Manhattan distance;
- for each signal in the design having an assigned signal source node and at least one target node to which the signal is to be routed, selecting a path from the signal source node to the target node from a plurality of candidate paths as a function of relative cost values of the candidate paths, wherein the selecting includes,
- determining for each node in each candidate path, a distance from that node to the target node and a future cost value associated with the distance;
- determining for each node in each candidate path, an associated node cost value;
- and
- determining a cost value of each candidate path as a function of each future cost value and node cost value of each node in the candidate path.
7 more elements
An apparatus for routing signals of a circuit design on an integrated circuit, comprising:
- means for selecting a pre-routing source node from a graph of nodes that represents conductors in a device;
- means for determining for each node in a graph a respective minimum future cost value as a function of a cumulative cost of nodes on a path from the pre-routing source node to the node;
- means for storing each future cost value in association with a distance from the node from which the future cost value was determined to the pre-routing source node, wherein the storing step includes, mean for establishing a two-dimensional table for storage of the future cost values;
- mean for determining a Manhattan distance from the node from which the future cost value was determined to the pre-routing source node;
- and mean for storing each future cost value in the two-dimensional table at a location indexed by the Manhattan distance;
- means, responsive to each signal specified in the design having an assigned signal source node and at least one target node to which the signal is to be routed, for selecting a path from the signal source node to the target node from a plurality of candidate paths as a function of relative cost values of the candidate paths, wherein the selecting means includes,
- means for determining for each node in each candidate path, a distance from that node to the target node and a future cost value associated with the distance;
- means for determining for each node in each candidate path, an associated node cost value;
- and
- means for determining a cost value of each candidate path as a function of each future cost value and node cost value of each node in the candidate path.
7 more elements
Dependencies are inferred from the claim text.