Method for resolving overloads in autorouting physical interconnections
AssigneeCadence Design Systems, Inc.
InventorsKen Wadland, William Schilp
Life of this patent
Estimating the term…
Abstract
Overloaded regions in the routing space of a physical network are resolved via a routing procedure composed of a topological routing phase and a geometric routing phase. The overloads are resolved in the topological routing phase where the constraints of routing are less prohibitive. Multiple topological transformations directed toward resolving the overloads are executed in the topological routing phase prior to a geometric arrangement being realized. The topological transformations may be applied concurrently by way of a multi-threaded embodiment of the invention.
Claims19
A method for routing interconnection paths between terminals via a routing procedure comprising:
- executing a topological routing phase prior to executing a geometric routing phase;
- selectively executing in said topological routing phase a plurality of topological transformations on a routed topological graph indicative of a geometric arrangement of the terminals, said plurality of topological transformations including shove, jump, and unwind operations each operably distinct one from another for execution to resolve an overload condition determined at said routed topological graph prior to said geometric routing phase;
- and,
- subsequently executing said geometric routing phase following completion of said topological routing phase to route the interconnection paths in said geometric arrangement of the terminals in accordance with said topological graph.
A method for routing interconnection paths between terminals via a routing procedure comprising:
- executing a topological routing phase prior to executing a geometric routing phase;
- selectively executing in said topological routing phase a plurality of topological transformations on a routed topological graph indicative of a geometric arrangement of the terminals, said plurality of topological transformations including shove, jump, and unwind operations each operably distinct one from another;
- and,
- subsequently executing said geometric routing phase following completion of said topological routing phase to route the interconnection paths in said geometric arrangement of the terminals in accordance with said topological graph;
- where said topological routing phase includes executing a plurality of said topological transformations to generate a set of transformed candidate graphs for a local topological graph corresponding to a portion of said routed topological graph responsive to a determination of an overload condition thereat;
- and, selecting one of said transformed candidate graphs in accordance with a first predetermined criterion.
A non-transitory computer program product for routing interconnection paths between terminals via a routing procedure, the computer program product comprising a computer usable medium having program instructions for:
- executing a topological routing phase prior to executing a geometric routing phase;
- selectively executing in said topological routing phase a plurality of topological transformations on a routed topological graph indicative of a geometric arrangement of the terminals, said plurality of topological transformations including shove, jump, and unwind operations each operably distinct one from another for execution to resolve an overload condition determined at said routed topological graph prior to said geometric routing phase;
- and,
- subsequently executing said geometric routing phase following completion of said topological routing phase to route the interconnection paths in said geometric arrangement of the terminals in accordance with said topological graph.
A non-transitory computer program product for routing interconnection paths between terminals via a routing procedure, the computer program product comprising a computer usable medium having program instructions for:
- executing a topological routing phase prior to executing a geometric routing phase;
- selectively executing in said topological routing phase a plurality of topological transformations on a routed topological graph indicative of a geometric arrangement of the terminals, said plurality of topological transformations including shove, jump, and unwind operations each operably distinct one from another;
- and,
- subsequently executing said geometric routing phase following completion of said topological routing phase to route the interconnection paths in said geometric arrangement of the terminals in accordance with said topological graph;
- where said topological routing phase includes executing a plurality of said topological transformations to generate a set of transformed candidate graphs for a local topological graph corresponding to a portion of said routed topological graph responsive to a determination of an overload condition thereat;
- and, selecting one of said transformed candidate graphs in accordance with a first predetermined criterion.
Dependencies are inferred from the claim text.