Process and apparatus for finding paths through a routing space

• US 20040088670A1
• Filed: 10/23/2003
• Published: 05/06/2004
• Est. Priority Date: 08/24/2001
• Status: Active Grant

• Current Assignee: FormFactor Incorporated
• Original Assignee: FormFactor Incorporated
• Inventors: Stevens, Mac, Parent, Yves
• Granted Patent: US 7,814,453 B2
• Time in Patent Office: Days
• US Class Current: 716/13
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

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.

Claims

1. 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.