Method and apparatus for performing routability checking
AssigneeCadence Design Systems, Inc.
InventorsSteven Teig, Etienne Jacques
Life of this patent
Estimating the term…
Abstract
Some embodiments of the invention provide a method of determining whether a set of routes can be geometrically embedded in a region according to a particular wiring model. The method identifies a congestion graph that has a set of edges, where at least two edges are neither orthogonal nor parallel. For each edge, the method identifies the set of routes that intersect the edge. It then determines whether any edge is overcongested.
Claims19
A method of determining whether a set of routes can be geometrically embedded in a region according to a particular wiring model, the method comprising:
- a) identifying a congestion graph having a set of edges, wherein at least two edges are neither orthogonal nor parallel;
- b) for each edge:
- identifying a set of routes that intersect the edge;
- and
- determining whether said edge is overcongested based on said identified set of routes.
A computer readable medium that stores a computer program having executable code, the computer program for determining whether a set of routes can be geometrically embedded in a region according to a particular wiring model, the computer program comprising sets of instructions for:
- a) identifying a congestion graph having a set of edges, wherein at least two edges are neither orthogonal nor parallel;
- b) for each edge;
- identifying a set of routes that intersect the edge;
- and
- determining whether said edge is overcongested based on said identified set of routes.
Dependencies are inferred from the claim text.