Method and apparatus for performing routability checking
First Claim
Patent Images
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
140 Citations
19 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
Specification