Back to results
US 8,479,138 B1Granted
Global constraint optimization
AssigneeCadence Design Systems, Inc.
InventorsRandall Scott Lawson, Richard Allen Woodward, Jr., Brett Allen Neal, Ken Wadland
Life of this patent
Estimating the term…
Abstract
Techniques that can improve the efficiency of routing where connections are subject to elongation constraints. The design can be optimized by estimating elongation needed to meet constraints after an initial routing solution has been generated, but before elongation is actually applied to detailed paths. Paths can be re-routed at this earlier stage if it is determined that too much elongation, or too much elongation in crowded areas, will need to be added after the detail routing stage.
Claims37
A routing method for a computer system having one or more computer processors and a non-transitory computer-readable storage medium storing a computer readable program for performing the method, the method comprising:
- for a set of connections subject to constraints including a set of elongation constraints, generating, with one or more of the computer processors, an initial set of topological paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint;
- estimating, with one or more of the computer processors, an initial set of elongations that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the initial set of elongations including increased length or delay in one or more paths in the initial set of paths, wherein an elongation refers to changing a length or delay of a path of one or more connections that are subject to the constraint;
- generating, with one or more of the computer processors, a new set of topological paths by re-routing at least some paths in the initial set to reduce an overall estimated increased length or delay for the initial set of paths;
- estimating, with one or more of the computer processors, a new set of elongations that would, when applied to at least some paths based on the new set of paths, cause the paths based on the new set of paths to meet the elongation constraints;
- generating, with one or more of the computer processors, an elongated set of paths by applying, with one or more of the computer processors, the new set of elongations to the paths based on the new set of paths;
- storing path information based on the elongated set of paths in the computer-readable storage medium;
- and
- after generating the new set of paths and prior to estimating the new set of elongations, determining geometric paths based on the new set of paths.
5 more elements
A routing method comprising:
- for a set of connections subject to constraints including a set of elongation constraints, determining, by using a computer, an initial set of paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint;
- estimating, by computing using the computer, elongations that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the estimated elongations including increased length or delay of one or more paths in the initial set of paths;
- using the estimated elongations to select connections for further processing;
- using information regarding at least some of the selected connections to generate a new set of paths that includes new paths replacing at least some paths in the initial set of paths, wherein the new set of paths requires less elongation to meet the elongation constraints than the elongation required by the initial set of paths;
- elongating, by using the computer, at least some of the paths in the new set of paths;
- and
- after generating the new set of paths and prior to estimating the new set of elongations, determining geometric paths based on the new set of paths.
4 more elements
A routing method comprising:
- for a set of connections subject to constraints including a set of elongation constraints, generating, by using a computer, an initial set of topological paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint;
- estimating, by using the computer, an elongation for each of the initial set of paths that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the estimated elongations including increased length or delay for one or more paths in the initial set of paths, wherein an elongation refers to changing a length or delay of a path of one or more connections that are subject to the constraint;
- selecting a set of elongation goals, at least in part based on the estimated elongations;
- optimizing the elongation goals by generating a new set of topological paths that includes new paths replacing at least some paths in the initial set of paths, wherein generating the new set of paths including re-routing the initial set of paths in an order determined at least in part based on the estimated elongations;
- determining and applying elongation, by using the computer, to at least some of the paths in the new set of paths to cause the new set of paths to meet the elongation constraints;
- and
- after generating the new set of paths and prior to estimating the new set of elongations, determining geometric paths based on the new set of paths.
4 more elements
Routing apparatus comprising:
- a non-transitory storage medium containing program instructions;
- and
- a processor coupled to said storage medium for executing program instructions stored in said storage medium;
- wherein said program instructions are configured so that when said processor executes said program instructions, the routing apparatus is configured to:
- for a set of connections subject to constraints including a set of elongation constraints, generate an initial set of topological paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint;
- estimate an initial set of elongations that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the estimated elongations including increased length or delay for one or more paths in the initial set of paths, wherein an elongation refers to changing a length or delay of a path of one or more connections that are subject to the constraint;
- generate a new set of topological paths by re-routing, with one or more of the computer processors, at least some paths in the initial set to reduce an overall estimated elongation for the initial set of paths;
- estimate a new set of elongations that would, when applied to at least some paths based on the new set of paths, cause the paths based on the new set of paths to meet the elongation constraints;
- generate an elongated set of paths by applying, with one or more of the computer processors, the new set of elongations to the paths based on the new set of paths;
- and
- after generating the new set of paths and prior to estimating the new set of elongations, determining geometric paths based on the new set of paths.
8 more elements
Apparatus for routing a set of connections subject to constraints including a set of elongation constraints, the apparatus comprising:
- means for generating an initial set of topological paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint;
- means, responsive to the initial set of paths, for estimating elongations that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the estimated elongations including increased length or delay for one or more paths in the initial set of paths, wherein an elongation refers to changing a length or delay of a path of one or more connections that are subject to the constraint;
- means for generating a new set of topological paths including means for re-routing at least some paths in the initial set to reduce an overall estimated elongation for the initial set of paths;
- and
- means for estimating a new set of elongations that would, when applied to at least some paths based on the new set of paths, cause the paths based on the new set of paths to meet the elongation constraints;
- means for generating an elongated set of paths by applying the new set of elongations to the paths based on the new set of paths;
- and
- after generating the new set of paths and prior to estimating the new set of elongations, means for determining geometric paths based on the new set of paths.
5 more elements
Apparatus for routing a set of connections subject to constraints including a set of elongation constraints, the apparatus comprising:
- means for determining an initial set of topological paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint;
- means, responsive to the initial set of paths, for estimating elongations that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the estimated elongations including increased length or delay for one or more paths in the initial set of paths, wherein an elongation refers to changing a length or delay of a path of one or more connections that are subject to the constraint;
- means, responsive to the estimated elongations, for selecting connections for further processing;
- means, responsive to information regarding at least some of the selected connections, for generating a new set of topological paths that includes new paths replacing at least some paths in the initial set of paths, wherein the new set of paths requires less elongation to meet the elongation constraints than the elongation required by the initial set of paths;
- means for elongating at least some of the paths in the new set of paths;
- and
- after generating the new set of paths and prior to estimating the new set of elongations, means for determining geometric paths based on the new set of paths.
4 more elements
Apparatus for routing a set of connections subject to constraints including a set of elongation constraints, the apparatus comprising:
- means for generating an initial set of topological paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint;
- means, responsive to the initial set of paths, for estimating elongations that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the estimated elongations including increased length or delay for one or more paths in the initial set of paths, wherein an elongation refers to changing a length or delay of a path of one or more connections that are subject to the constraint;
- selecting a set of elongation goals, at least in part based on the estimated elongations;
- means for optimizing the elongation goals by generating a new set of topological paths that includes new paths replacing at least some paths in the initial set of paths;
- means, responsive to information regarding at least some of the new paths, for determining and applying elongation to at least some of the paths in the new set of paths to cause the new set of paths to meet the elongation constraints;
- and
- after generating the new set of paths and prior to estimating the new set of elongations, means for determining geometric paths based on the new set of paths.
4 more elements
A non-transitory computer-readable medium containing program instructions, which when executed by a computer system cause the computer system to execute a routing method, the program instructions including:
- code that when executed causes the computer system to generate, for a set of connections subject to constraints including a set of elongation constraints, an initial set of topological paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint;
- code that when executed causes the computer system to estimate an initial set of elongations that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the estimated elongations including increased length or delay for one or more paths in the initial set of paths, wherein an elongation refers to changing a length or delay of a path of one or more connections that are subject to the constraint;
- code that when executed causes the computer system to generate a new set of topological paths by re routing, with one or more of the computer processors, at least some paths in the initial set to reduce an overall estimated elongation for the initial set of paths;
- code that when executed causes the computer system to estimate a new set of elongations that would, when applied to at least some paths based on the new set of paths, cause the paths based on the new set of paths to meet the elongation constraints;
- code that when executed causes the computer system to generate an elongated set of paths by applying, with one or more of the computer processors, the new set of elongations to the paths based on the new set of paths;
- and
- after generating the new set of paths and prior to estimating the new set of elongations, that when executed causes the computer system to determine geometric paths based on the new set of paths.
4 more elements
Dependencies are inferred from the claim text.