Distributed autorouting of conductive paths in printed circuit boards

• US 7,305,648 B2
• Filed: 06/18/2004
• Issued: 12/04/2007
• Est. Priority Date: 11/21/2003
• Status: Active Grant

• Current Assignee: Siemens Industry Software Limited (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Petunin, Vladimir V., Natarajan, Venkat, Pfeil, Charles L., Smith, Edwin Franklin, Starkov, Alexander N.
• Primary Examiner(s): Chiang; Jack
• Assistant Examiner(s): Dimyan; Magid Y.
• Application Number:
  US10/870,072
• Publication Number:
  US 20050114821A1
• Time in Patent Office: 1,264 Days
• Field of Search: 716/15, 716/11, 715/748, 715/751, 709/203, 709/205
• 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) automatically assigning, from a list of component pin pairs for an electronic circuit, a different 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 of clients, 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) so as to receive from the clients and incorporate into said master PCB design proposed routes for additional component pin pairs from the list of component pin pairs.

2. The method of claim 1, further comprising:

(e) forwarding update messages to the clients of the plurality of clients, 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 of clients 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 of clients when that 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 message in update queues for the clients of the plurality of clients, and

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

6. The method of claim 1, further comprising:

(e) repeating steps (a) through (c) as part of making multiple passes throught the list of component pin pairs.

7. The method of claim 6, wherein

step (a) comprises, during one of the passes through the list of component pin pairs, 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 of component pin pairs, 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 pin pairs from the list of component pin pairs 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 pin pairs from the list of component pin pairs 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 of component pin pairs 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 pin pairs from the list of component pin pairs 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 of component pin pairs based at least in part on relative locations of different pin pairs.

12. The method of claim 1, further comprising:

(e) assigning a component pin pair to a first client of the plurality of clients and assigning the same pin pair to a second client of the plurality of clients 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 (e) 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. The method of claim 1, further comprising:

(e) receiving, from a client X of the plurality of clients, a proposed route for a conductive path connecting pin pair N assigned to client X;

(f) rejecting the proposed route received in step (e);

(g) forwarding an update message to client X indicating rejection of the proposed route received in step (e);

(h) receiving a different proposed route for pin pair N from client X; and

(i) incorporating the proposed route received in step (h) into the master PCB design.

15. The method of claim 14, further comprising:

(j) receiving, from a client Y of the plurality of clients and prior to (e), a proposed route for a conductive path connecting pin pair M assigned to client Y;

(k) incorporating the proposed route received in step (j) into the master PCB design; and

(l) generating an update message indicating incorporation of the proposed route in step (k), and wherein

step (g) includes forwarding the update message indicating rejection of the proposed route received in step (e) with the update message indicating incorporation of the proposed route in step (k).

16. 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) automatically assigning, from a list of component pin pairs for an electronic circuit, a different 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 of clients, 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) so as to receive from the clients and incorporate into said master PCB design propose routes for additional component pin pairs from the list of component pin pairs.

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

(e) forwarding update messages to the clients of the plurality of clients, 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.

18. The machine-readable medium of claim 17, wherein step (e) comprises forwarding update messages to a client of the plurality of clients 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.

19. The machine-readable medium of claim 16, 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 of clients when that client is not routing an assigned pin pair.

20. The machine-readable medium of claim 19, 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 massage in update queues for the clients of the plurality of clients, and

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

21. The machine readable medium of claim 16, comprising further instructions for performing steps comprising:

(e) repeating steps (a) through (c) as part of making multiple passes through the list of component pin pairs.

22. The machine-readable medium of claim 21, wherein

step (a) comprises, during one of the passes through the list of component pin pairs, 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 of component pin pairs, instructing clients to route assigned pin pairs and imposing different limits upon the number of vias permitted in a proposed route.

23. The machine-readable medium of claim 16, wherein

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

24. The machine-readable medium of claim 16, wherein

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

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

26. The machine-readable medium of claim 16, wherein

step (a) comprises assigning pin pairs from the list of component pin pairs 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 of component pin pairs based at least in part on relative locations of different pin pairs.

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

(e) assigning a component pin pair to a first client of the plurality of clients and assigning the same pin pair to a second client of the plurality of clients such that the first and second clients simultaneously attempt to route a conductive path between the pins of the assigned pin pair.

28. The machine-readable medium of claim 27, wherein step (e) 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.

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

(e) receiving, from a client X of the plurality of clients, a proposed route for a conductive path connecting pin pair N assigned to client X;

(f) rejecting the proposed route received in step (e);

(g) forwarding an update message to client X indicating rejection of the proposed route received in step (e);

(h) receiving a different proposed route for pin pair N from client X; and

(i) incorporating the proposed route received in step (h) into the master PCB design.

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

(j) receiving, from a client Y of the plurality of clients and prior to (e), a proposed route for a conductive path connecting pin pair M assigned to client Y;

(k) incorporating the proposed route received in step (j) into the master PCB design; and

(l) generating an update message indicating incorporation of the proposed route in step (k), and wherein

step (g) includes forwarding the update message indicating rejection of the proposed route received in step (e) with the update message indicating incorporation of the proposed route in step (k).