Distributed autorouting of conductive paths

• US 20050114821A1
• Filed: 06/18/2004
• Published: 05/26/2005
• Est. Priority Date: 11/21/2003
• Status: Active Grant

• Current Assignee: Siemens Industry Software Inc. (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Petunin, Vladimir V., Natarajan, Venkat, Pfeil, Charles L., Smith, Edwin Franklin, Starkov, Alexander N.
• Granted Patent: US 7,305,648 B2
• Time in Patent Office: Days
• US Class Current: 716/126
• CPC Class Codes: G06F 2111/02 CAD in a network environment, e.g. collaborative CAD or distributed simulation
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A server computer maintains a master database for a PCB design, and a copy of the PCB design is provided to multiple client computers. The server assigns each client a different pair of pins for which a connection must be routed. When a client completes an assigned routing task, it requests that the server update the PCB master design with the route found by the client for its assigned pin pair. After forwarding the request, the client does not update its copy of the PCB design to reflect the found route. Instead, the client returns its copy to the state occupied prior to assignment of the pin pair by the server. Upon receiving notification that the server incorporated the found route, the client updates its copy of the design to include that route.

Claims

1. A method for routing conductive paths for a printed circuit board (PCB), comprising:

(a) assigning a component pin pair to each of a plurality of client computers configured to automatically route a conductive path between two component pins;

(b) receiving, from each client of the plurality, a proposed route for a conductive path connecting the pin pair assigned to the client;

(c) incorporating the proposed routes into a master PCB design; and

(d) repeating steps (a) through (c).

2. The method of claim 1, further comprising:

(e) forwarding update messages to the clients of the plurality, the update messages indicating incorporation of proposed routes into a master copy of a PCB design and permitting the clients to include the incorporated routes into local copies of the PCB design maintained by the clients.

3. The method of claim 2, wherein step (e) comprises forwarding update messages to a client of the plurality permitting said client to include incorporated routes into the local PCB design copy for said client, said incorporated routes being previously proposed by said client.

4. The method of claim 1, further comprising:

(e) generating, upon incorporation of a proposed route into the master PCB design, an update indicating incorporation of the route; and

(f) forwarding the update to each client of the plurality when said client is not routing an assigned pin pair.

5. The method of claim 4, wherein:

step (e) comprises generating a separate update message upon incorporation of each of multiple proposed routes into the PCB master design copy,

step (e) further comprises placing each update in update queues for the clients of the plurality, and

step (f) comprises forwarding the contents of the update queue for the client when the client is not currently routing an assigned pin pair.

6. The method of claim 1, wherein:

step (a) comprises assigning component pin pairs from a list of component pins pairs for an electronic circuit, and

step (d) comprises repeating steps (a) through (c) in multiple passes through the list.

7. The method of claim 6, wherein:

step (a) comprises, during one of the passes through the list, instructing clients to route assigned pin pairs and imposing a limit upon the number of vias permitted in a proposed route, and

step (a) further comprises, during subsequent passes through the list, instructing clients to route assigned pin pairs and imposing different limits upon the number of vias permitted in a proposed route.

8. The method of claim 1, wherein:

step (a) comprises assigning component pin pairs from a list of component pins pairs for an electronic circuit, and

step (a) further comprises assigning pin pairs from the list based at least in part on distances separating the pins within the pin pairs.

9. The method of claim 1, wherein:

step (a) comprises assigning component pin pairs from a list of component pins pairs for an electronic circuit, and

step (a) further comprises assigning pin pairs from the list based at least in part on relative locations of different pin pairs.

10. The method of claim 9, wherein step (a) further comprises assigning pin pairs from the list based at least in part on the amount of overlap between polygons formed from pin locations of different pin pairs.

11. The method of claim 1, wherein:

step (a) comprises assigning component pin pairs from a list of component pins pairs for an electronic circuit,

step (a) further comprises assigning pin pairs from the list based at least in part on distances separating the pins within the pin pairs, and

step (a) further comprises assigning pin pairs from the list based at least in part on relative locations of different pin pairs.

12. The method of claim 1, wherein step (a) comprises assigning a component pin pair to a first client of the plurality and assigning the same pin pair to a second client of the plurality such that the first and second clients simultaneously attempt to route a conductive path between the pins of the assigned pin pair.

13. The method of claim 12, wherein step (a) comprises assigning the pin pair to the first client with a first set of routing parameters and assigning the pin pair to the second client with a second set of routing parameters.

14. A method for routing conductive paths for a printed circuit board (PCB), comprising:

(a) receiving a pin pair assignment, the assignment identifying pins of one or more components of an electronic circuit for which a connecting conductive path is to be routed;

(b) automatically finding a route for a conductive path between the identified pins;

(c) transmitting an edit request, the edit request proposing the found route;

(d) receiving an indication that the proposed route is incorporated into a PCB design; and

(e) updating, subsequent to receipt of the indication, a local copy of the PCB design to include the found route.

15. The method of claim 14, further comprising:

(f) receiving, subsequent to receipt of the indication in step (d), a second pin pair assignment identifying pins of one or more components of the circuit;

(g) automatically finding a route for a conductive path between the pins of the second pin pair assignment;

(h) transmitting an edit request proposing the route found in step (g);

(i) receiving an indication that the route proposed in step (h) is incorporated into the PCB design; and

(j) updating, subsequent to receipt of the indication in step (i), the local copy of the PCB design to include the route found in step (g).

16. The method of claim 14, further comprising:

(f) receiving, subsequent to receipt of the indication in step (d), a second pin pair assignment identifying pins of one or more components of the circuit;

(g) automatically finding a route for a conductive path between the pins of the second pin pair assignment;

(h) transmitting an edit request proposing the route found in step (g);

(i) receiving an instruction to find another route between the pins of the second pin pair assignment;

(j) automatically finding a second route between the pins of the second pin pair assignment; and

(k) transmitting an edit request proposing the second route.

17. The method of claim 14, wherein:

step (d) comprises receiving one or more indications that other routes are incorporated into the PCB design, the other routes found by one or more computers other than a computer performing steps (a) through (e), and

step (e) comprises updating the local copy of the PCB design to include the other routes.

18. The method of step 14, further comprising:

(f) receiving, subsequent to receipt of the indication in step (d), a second pin pair assignment identifying pins of one or more components of the circuit;

(g) receiving an indication of a limit upon the number of vias permitted in a conductive path routed between the pins of the second pin pair assignment;

(h) automatically seeking a route for a conductive path between the pins of the second pin pair assignment; and

(i) transmitting an indication of an inability to route a connection between the pins of the second pin pair assignment.

19. A machine-readable medium having stored thereon data representing sequences of instructions which, when executed by a processor, cause the processor to perform steps comprising:

(a) assigning a component pin pair to each of a plurality of client computers configured to automatically route a conductive path between two component pins;

(b) receiving, from each client of the plurality, a proposed route for a conductive path connecting the pin pair assigned to the client;

(c) incorporating the proposed routes into a master PCB design; and

(d) repeating steps (a) through (c).

20. The machine-readable medium of claim 19, comprising further instructions for performing steps comprising:

(e) forwarding update messages to the clients of the plurality, the update messages indicating incorporation of proposed routes into a master copy of a PCB design and permitting the clients to include the incorporated routes into local copies of the PCB design maintained by the clients.

21. The machine-readable medium of claim 20, wherein step (e) comprises forwarding update messages to a client of the plurality permitting said client to include incorporated routes into the local PCB design copy for said client, said incorporated routes being previously proposed by said client.

22. The machine-readable medium of claim 19, comprising further instructions for performing steps comprising:

(e) generating, upon incorporation of a proposed route into the master PCB design, an update indicating incorporation of the route; and

(f) forwarding the update to each client of the plurality when said client is not routing an assigned pin pair.

23. The machine-readable medium of claim 22, wherein:

step (e) comprises generating a separate update message upon incorporation of each of multiple proposed routes into the PCB master design copy,

step (e) further comprises placing each update in update queues for the clients of the plurality, and

step (f) comprises forwarding the contents of the update queue for the client when the client is not currently routing an assigned pin pair.

24. The machine-readable medium of claim 19, wherein:

step (a) comprises assigning component pin pairs from a list of component pins pairs for an electronic circuit, and

step (d) comprises repeating steps (a) through (c) in multiple passes through the list.

25. The machine-readable medium of claim 24, wherein:

step (a) comprises, during one of the passes through the list, instructing clients to route assigned pin pairs and imposing a limit upon the number of vias permitted in a proposed route, and

step (a) further comprises, during subsequent passes through the list, instructing clients to route assigned pin pairs and imposing different limits upon the number of vias permitted in a proposed route.

26. The machine-readable medium of claim 19, wherein:

step (a) comprises assigning component pin pairs from a list of component pins pairs for an electronic circuit, and

step (a) further comprises assigning pin pairs from the list based at least in part on distances separating the pins within the pin pairs.

27. The machine-readable medium of claim 19, wherein:

step (a) comprises assigning component pin pairs from a list of component pins pairs for an electronic circuit, and

step (a) further comprises assigning pin pairs from the list based at least in part on relative locations of different pin pairs.

28. The machine-readable medium of claim 27, wherein step (a) further comprises assigning pin pairs from the list based at least in part on the amount of overlap between polygons formed from pin locations of different pin pairs.

29. The machine-readable medium of claim 19, wherein:

step (a) comprises assigning component pin pairs from a list of component pins pairs for an electronic circuit,

step (a) further comprises assigning pin pairs from the list based at least in part on distances separating the pins within the pin pairs, and

step (a) further comprises assigning pin pairs from the list based at least in part on relative locations of different pin pairs.

30. The machine-readable medium of claim 19, wherein step (a) comprises assigning a component pin pair to a first client of the plurality and assigning the same pin pair to a second client of the plurality such that the first and second clients simultaneously attempt to route a conductive path between the pins of the assigned pin pair.

31. The machine-readable medium of claim 30, wherein step (a) comprises assigning the pin pair to the first client with a first set of routing parameters and assigning the pin pair to the second client with a second set of routing parameters.

32. A machine-readable medium having stored thereon data representing sequences of instructions which, when executed by a processor, cause the processor to perform steps comprising:

(a) receiving a pin pair assignment, the assignment identifying pins of one or more components of an electronic circuit for which a connecting conductive path is to be routed;

(b) automatically finding a route for a conductive path between the identified pins;

(c) transmitting an edit request, the edit request proposing the found route;

(d) receiving an indication that the proposed route is incorporated into a PCB design; and

(e) updating, subsequent to receipt of the indication, a local copy of the PCB design to include the found route.

33. The machine-readable medium of claim 32, comprising further instructions for performing steps comprising:

(f) receiving, subsequent to receipt of the indication in step (d), a second pin pair assignment identifying pins of one or more components of the circuit;

(g) automatically finding a route for a conductive path between the pins of the second pin pair assignment;

(h) transmitting an edit request proposing the route found in step (g);

(i) receiving an indication that the route proposed in step (h) is incorporated into the PCB design; and

(j) updating, subsequent to receipt of the indication in step (i), the local copy of the PCB design to include the route found in step (g).

34. The machine-readable medium of claim 32, comprising further instructions for performing steps comprising:

(f) receiving, subsequent to receipt of the indication in step (d), a second pin pair assignment identifying pins of one or more components of the circuit;

(g) automatically finding a route for a conductive path between the pins of the second pin pair assignment;

(h) transmitting an edit request proposing the route found in step (g);

(i) receiving an instruction to find another route between the pins of the second pin pair assignment;

(j) automatically finding a second route between the pins of the second pin pair assignment; and

(k) transmitting an edit request proposing the second route.

35. The machine-readable medium of claim 32, wherein:

step (d) comprises receiving one or more indications that other routes are incorporated into the PCB design, the other routes found by one or more computers other than a computer performing steps (a) through (e), and

step (e) comprises updating the local copy of the PCB design to include the other routes.

36. The machine-readable medium of claim 32, comprising further instructions for performing steps comprising:

(f) receiving, subsequent to receipt of the indication in step (d), a second pin pair assignment identifying pins of one or more components of the circuit;

(g) receiving an indication of a limit upon the number of vias permitted in a conductive path routed between the pins of the second pin pair assignment;

(h) automatically seeking a route for a conductive path between the pins of the second pin pair assignment; and

(i) transmitting an indication of an inability to route a connection between the pins of the second pin pair assignment.