Process and apparatus for finding paths through a routing space

• US 7,814,453 B2
• Filed: 10/23/2003
• Issued: 10/12/2010
• Est. Priority Date: 08/24/2001
• Status: Expired due to Fees

• Current Assignee: FormFactor Incorporated
• Original Assignee: FormFactor Incorporated
• Inventors: Stevens, Mac, Parent, Yves
• Primary Examiner(s): Shah; Kamini S
• Assistant Examiner(s): GEBRESILASSIE, KIBROM K
• Application Number:
  US10/693,484
• Publication Number:
  US 20040088670A1
• Time in Patent Office: 2,546 Days
• Field of Search: 709/238, 709/239, 709/242, 716/1, 716/12, 716/13, 716/14, 716/15, 703/13, 717/128
• US Class Current: 716/126
• 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. An apparatus comprising computer hardware for use in generating paths for electrically conductive traces within a routing space comprising:

means for receiving computer readable information representing a proposed physical layout of a routing space of an electronics system including locations of a first electronic component, a second electronic component, and obstacles within said proposed physical layout;

means for creating an initial array of nodes within the proposed physical layout;

means for adjusting within said proposed physical layout said initial array of nodes, said means for adjusting include locating a particular number of nodes between a pair of said obstacles, said particular number corresponding to a maximum number of traces that can pass between said obstacles, each of said nodes positioned between said pair of said obstacles representing a possible location of one of said traces that can pass between said obstacles;

means for applying forces to ones of said nodes, wherein a magnitude of one of said forces applied to one of said nodes is proportional to a proximity of said one of said nodes to one of said obstacles;

means for moving within said proposed physical layout each of said ones of said nodes in accordance with said forces applied to said one of said nodes; and

means for creating a computer generated representation of a trace within said proposed physical layout of said routing space that connects the first electronic component to the second electronic component and passes between said pair of obstacles by selecting a path through said adjusted array of nodes, said trace comprising said path.

2. The apparatus of claim 1, wherein said means for adjusting comprises means for determining said particular number of traces that may pass between said pair of obstacles.

3. The apparatus of claim 1, wherein said means for adjusting locates said particular number of nodes along a line segment between said pair of obstacles.

4. The apparatus of claim 3, wherein said line segment is a shortest line segment between said pair of obstacles.

5. The apparatus of claim 1, wherein said means for adjusting adjusts 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.

6. The apparatus of claim 1 further comprising means for linking said adjusted initial array of nodes.

7. The apparatus of claim 6, wherein said means for linking creates a link between each node in said array and nodes within a predetermined proximity of said each node without crossing any of said links.

8. The apparatus of claim 7, wherein said path traverses ones of said links.

9. The apparatus of claim 1, wherein said computer generated representation of said trace is stored within said apparatus.

10. The apparatus of claim 1, wherein said means for creating an initial array of nodes creates the initial array of nodes in a honeycombed pattern.

11. The apparatus of claim 1, wherein said means for creating an initial array of nodes creates the initial array of nodes wherein a random location of at least one node is generated.

12. An apparatus comprising computer hardware for use in generating paths for electrically conductive traces within a routing space comprising:

means for receiving information representing a proposed physical layout of a routing space of an electronics system including locations of obstacles within said proposed physical layout;

means for creating an initial array of nodes within said proposed physical layout of said routing space;

means for applying forces to ones of said nodes, wherein a magnitude of one of said forces applied to one of said nodes is proportional to a proximity of said one of said nodes to one of said obstacles;

means for moving within said proposed physical layout each of said ones of said nodes in accordance with said force applied to said one of said nodes; and

means for creating a computer generated representation of a trace within said proposed physical layout of said routing space by selecting a path through said array of nodes, said trace comprising said path.

13. The apparatus of claim 12, wherein said means for applying applies a plurality of forces to one of said nodes, wherein a magnitude of each of said plurality of forces corresponds to a proximity of said node to one of said obstacles;

and

said means for moving moves one of said nodes in accordance with a vector sum of said plurality of forces applied to said one of said nodes.

14. The apparatus of claim 12, wherein said computer generated representation of said trace is stored within said apparatus.

15. The apparatus of claim 12, wherein said means for creating an initial array of nodes comprises means for selecting spacings of the initial array of nodes to form a honeycombed pattern.

16. The apparatus of claim 12, wherein said means for creating an initial array of nodes comprises means for generating a random location for at least one node.