Patent US6678876B2 successfully refreshed from Google Patents.
US6678876B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Process and apparatus for finding paths through a routing space
Assignee: FormFactor Inc
•
Filing: 2001-08-24
•
Granted: 2004-01-13
•
Expires: 2021-08-24
Abstract
Abstract An initial graph of nodes is created within a routing space, and the number and locations of the nodes in the graph are adjusted. Links are created between nodes of the graph, and traces between specified nodes are created through the linked graph.
Inventors
- 👤 Mac Stevens
- 👤 Yves Parent
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 15:56
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
165 words
A computer-executable process for finding a path for electrically conductive traces to be routed within a routing space, said process comprising: receiving computer readable data comprising parameters defining said routing space, beginning and ending locations for said traces to be routed, design rules for said traces, and at least two obstacles through which said traces may not pass; creating a graph of nodes within said routing space; adjusting a number of nodes of said graph located between pairs of said at least two obstacles; adjusting locations of said nodes of said graph by applying directional forces to said nodes in accordance with locations of said nodes with respect to each other and said at least two obstacles; linking said graph by creating links between pairs of said nodes without creating links that cross; and finding paths for said traces through said linked graph by creating a plurality of path segments between nodes of said linked graph and calculating a routing cost associated with said nodes.
Claim 2
Dependent Claim
165 words
A computer-executable process for finding a path for electrically conductive traces to be routed within a routing space, said process comprising: receiving computer readable data comprising parameters defining said routing space, beginning and ending locations for said traces to be routed, design rules for said traces, and at least two obstacles through which said traces may not pass; creating a graph of nodes within said routing space; adjusting a number of nodes of said graph located between pairs of said at least two obstacles; adjusting locations of said nodes of said graph by applying directional forces to said nodes in accordance with locations of said nodes with respect to each other and said at least two obstacles; linking said graph by creating links between pairs of said nodes without creating links that cross; and finding paths for said traces through said linked graph by creating a plurality of path segments between nodes of said linked graph and calculating a routing cost associated with said nodes.
Claim 3
Independent Claim
71 words
A method for finding a path within a routing space from a start location to an end location, said method comprising: creating an initial array of nodes within said routing space; adjusting said initial array of nodes; and selecting said path through said adjusted array of nodes, wherein said step of adjusting said initial array of nodes comprises adjusting nodes between at least a pair of obstacles in said routing space.
Claim 4
Independent Claim
71 words
A method for finding a path within a routing space from a start location to an end location, said method comprising: creating an initial array of nodes within said routing space; adjusting said initial array of nodes; and selecting said path through said adjusted array of nodes, wherein said step of adjusting said initial array of nodes comprises adjusting nodes between at least a pair of obstacles in said routing space.
Claim 5
Dependent Claim
52 words
The method of claim 2 , wherein said step of adjusting nodes between at least a pair of obstacles comprises: determining a number of paths that may pass between said pair of obstacles; and adjusting a number of nodes between said pair of obstacles to be equal to said number of paths.
Claim 6
Dependent Claim
40 words
The method of claim 3 , wherein said step of determining a number of paths that may pass between said pair of obstacles comprises determining a number of paths that may cross a line segment between said pair of obstacles.
Claim 7
Dependent Claim
44 words
The method of claim 4 , wherein said step of adjusting a number of nodes located between said pair of obstacles to be equal to said number of paths comprises adjusting nodes along said line segment to be equal to said number of paths.
Claim 8
Dependent Claim
32 words
The method of claim 2 , wherein said step of adjusting nodes between at least a pair of obstacles further comprises adjusting locations of said nodes located between said pair of obstacles.
Claim 9
Dependent Claim
41 words
The method of claim 6 , wherein said step of adjusting locations of said nodes located between said pair of obstacles comprises positioning said nodes located between said pair of obstacles to correspond to permissible locations of paths between said obstacles.
Claim 10
Dependent Claim
45 words
The method of claim 2 , wherein said step of adjusting said initial array of nodes further comprises: adjusting a location of each of at least one of said nodes in accordance with a proximity of said node to an object in said routing space.
Claim 11
Dependent Claim
14 words
The method of claim 2 further comprising linking said adjusted initial array of nodes.
Claim 12
Dependent Claim
43 words
The method of claim 9 , wherein said step of linking said adjusted initial array of nodes comprises creating a link between each node in said array of nodes within a predetermined proximity of said each node without crossing any of said links.
Claim 13
Dependent Claim
14 words
The method of claim 9 , wherein said path traverses ones of said links.
Claim 14
Independent Claim
85 words
A method for finding a path within a routing space from a start location to an end location, said method comprising: creating an initial array of nodes within said routing space; adjusting said initial array of nodes; and selecting said path through said adjusted array of nodes, wherein said step of adjusting said initial array of nodes comprises adjusting a location of each of at least one of said nodes in accordance with a proximity of said node to an obstacle in said routing space.
Claim 15
Independent Claim
85 words
A method for finding a path within a routing space from a start location to an end location, said method comprising: creating an initial array of nodes within said routing space; adjusting said initial array of nodes; and selecting said path through said adjusted array of nodes, wherein said step of adjusting said initial array of nodes comprises adjusting a location of each of at least one of said nodes in accordance with a proximity of said node to an obstacle in said routing space.
Claim 16
Dependent Claim
65 words
The method of claim 12 , wherein said step of adjusting a location of each of at least one of said nodes in accordance with a proximity of said node to an obstacles comprises: applying a force to said node, wherein a magnitude of said force corresponds to said proximity of said node to said obstacles; and moving said node in accordance with said force.
Claim 17
Dependent Claim
48 words
The method of claim 12 , wherein said step of adjusting said initial array of nodes further comprises adjusting a location of each of at least one of said nodes in accordance with a proximity of said node to a plurality of said objects in said routing space.
Claim 18
Dependent Claim
82 words
The method of claim 14 , wherein said step of adjusting a location of each of at least one of said nodes in accordance with a proximity of said node to a plurality of obstacles comprises: applying a plurality of forces to said node, wherein a magnitude of each of said plurality of forces corresponds to said proximity of said node to one of said plurality of obstacles; and moving said node in accordance with a sum of said plurality of forces.
Claim 19
Independent Claim
150 words
A method for finding a path within a routing space from a start location to an end location, said method comprising: providing an array of linked nodes within said routing space, said array including a source node corresponding to said start location, a destination node corresponding to said end location, and a plurality of intermediate nodes; and determining a path from said source node to said destination node through said linked nodes, wherein said step of determining a path from said source node to said destination node comprises: iteratively creating a plurality of partial paths, each said partial path extending to an intermediate node in said array; determining a routing cost of each said partial path; and if more than one partial path extends to one intermediate node, discarding all of said partial paths that extend to said one intermediate node except the partial path with the lowest routing cost.
Claim 20
Independent Claim
150 words
A method for finding a path within a routing space from a start location to an end location, said method comprising: providing an array of linked nodes within said routing space, said array including a source node corresponding to said start location, a destination node corresponding to said end location, and a plurality of intermediate nodes; and determining a path from said source node to said destination node through said linked nodes, wherein said step of determining a path from said source node to said destination node comprises: iteratively creating a plurality of partial paths, each said partial path extending to an intermediate node in said array; determining a routing cost of each said partial path; and if more than one partial path extends to one intermediate node, discarding all of said partial paths that extend to said one intermediate node except the partial path with the lowest routing cost.
Claim 21
Dependent Claim
33 words
The method of claim 16 , wherein said step of iteratively creating a plurality of partial paths comprises creating initial paths from said source node to first nodes linked to said source node.
Claim 22
Dependent Claim
34 words
The method of claim 17 , wherein said step of iteratively creating a plurality of partial paths further comprises extending said initial paths from said first nodes to nodes linked to said first nodes.
Claim 23
Dependent Claim
46 words
The method of claim 16 , wherein said step of providing an array of linked nodes comprises, for each node in said array, creating a link between said each node and nodes within a predetermined proximity of said each node without crossing any of said links.
Claim 24
Dependent Claim
46 words
The method of claim 16 , wherein said step of providing an array of linked nodes comprises, for each node in said array, creating shortest links between said each node and nodes within a predetermined proximity of said each node without crossing any of said links.
Claim 25
Dependent Claim
59 words
The method of claim 16 , wherein said step of providing an array of linked nodes comprises: selecting one of said nodes of said array; creating a link to another node of said array that is within a predetermined distance of said selected node; and if said created link crosses another link, deleting a longest of said crossed links.
Claim 26
Dependent Claim
44 words
The method of claim 16 , wherein said step of determining a routing cost of each said partial path comprises estimating a length of a path from said source node to said destination node through the intermediate node to which said partial path extends.
References Cited (Backward Citations)
US4500963A
Cited
US4642890A
Cited
US5245550A
Cited
US5657242A
Cited
US5717600A
Cited
US5636129A
Cited
US6385758B1
Cited
US6256769B1
Cited
US6490713B2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-01-12 | 2007-07-14 | 2008-01-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-01-12 | 2011-07-14 | 2012-01-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-01-12 | 2015-07-14 | 2016-01-13 | $7700.00 | Window Closed / Lapsed |