Method and apparatus for parallel routing locking mechanism

• US 6,269,469 B1
• Filed: 04/17/1998
• Issued: 07/31/2001
• Est. Priority Date: 04/17/1998
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Scepanovic, Ranko, Pavisic, Ivan, Raspopovic, Pedja
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): DO, THUAN V
• Application Number:
  US09/062,418
• Time in Patent Office: 1,201 Days
• Field of Search: 395/500.08, 716/12
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A method for implementing net routing for an integrated circuit design with parallel processors, said method comprising the steps of creating a character array, filling said character array with a first character, dividing a plurality of nets into groups, supplying a plurality of locks and assigning each said group its own individual lock, assigning for each net in said plurality of nets a position in the character array; and placing a second character in the position of a particular net in said character array when the net is operated on by a processor and replacing said second character with the first character after said operation is completed.

Claims

1. A method for implementing net routing for an integrated circuit design with parallel processors, said method comprising the following steps:

a. creating a character array that includes plural positions, each position capable of holding a character;

b. filling said character array with a first character;

c. dividing a plurality of nets into groups;

d. supplying a plurality of locks and assigning each said group its own individual lock, wherein each lock allows multiple processors to synchronize their operations with respect to the nets in the group assigned to the lock;

e. assigning to each net in said plurality of nets a position in the character array; and

f. placing a second character in the position of a particular net in said character array when the net is operated on by a processor and replacing said second character with the first character after said operation is completed.

2. The method of claim 1 wherein said first character is a zero.

3. The method of claim 2 wherein said second character is one.

4. The method of claim 3 wherein, in step c, said plurality of nets is divided into groups of a predetermined size.

5. The method of claim 4 wherein said predetermined size is approximately 10.

6. The method of claim 1 wherein said locks are mutex locks.

7. The method of claim 1 wherein the additional step is taken where each of said parallel processors is assigned to a specific region in the integrated circuit design.

8. An apparatus for implementing net routing for an integrated circuit design with parallel processors, said apparatus comprising:

a. means for creating a character array that includes plural positions, each position capable of holding a character;

b. means for filling said character array with a first character;

c. means for dividing a plurality of nets into groups;

d. means for supplying a plurality of locks and assigning each said group its own individual lock, wherein each lock allows multiple processors to synchronize their operations with respect to the nets in the group assigned to the lock;

e. means for assigning to each net in said plurality of nets a position in the character array; and

f. means for placing a second character in the position of a particular net in said character array when the net is operated on by a processor and replacing said second character with the first character after said operation is completed.

9. The apparatus of claim 8 wherein said first character is a zero.

10. The apparatus of claim 8 wherein said second character is one.

11. The apparatus of claim 10 wherein said means for dividing a plurality of nets into groups divides nets into groups of a predetermined size.

12. The apparatus of claim 11 wherein said predetermined size is approximately 10.

13. The apparatus of claim 8 wherein said locks are mutex locks.

14. The apparatus of claim 8 further comprising means for assigning each of said parallel processors to a specific region in the integrated circuit design.

15. A computer storage device with computer encoded instructions thereon for implementing net routing for an integrated circuit design with parallel processors, said method comprising the following steps:

a. a computer encoded instruction for creating a character array that includes plural positions, each position capable of holding a character;

b. a computer encoded instruction for filling said character array with a first character;

c. a computer encoded instruction for dividing a plurality of nets into groups;

d. a computer encoded instruction for supplying a plurality of locks and assigning each said group its own individual lock, wherein each lock allows multiple processors to synchronize their operations with respect to the nets in the group assigned to the lock;

e. a computer encoded instruction for assigning to each net in said plurality of nets a position in the character array; and

f. a computer encoded instruction for placing a second character in the position of a particular net in said character array when the net is operated on by a processor and replacing said second character with the first character after said operation is completed.

16. A method for routing nets in a circuit, said method comprising:

defining a character array that includes plural positions, including a position for each of plural nets in the circuit, wherein each position is capable of holding a character;

dividing the plural nets into groups of nets;

supplying a plurality of locks and assigning each said group its own lock, wherein each lock allows multiple processors to synchronize their operations with respect to the nets in the group assigned to the lock; and

routing said plural nets using parallel processors,

wherein in order for one of the parallel processors to route a portion of a net selected from said plural nets, said one of the parallel processors must first;

(a) obtain the lock corresponding to the group to which the net belongs, and

(b) alter a character at the position in the character array that corresponds to the net from a first character to a second character.

17. A method according to claim 16, wherein each of said groups includes a same number of nets.

18. A method according to claim 16, wherein said locks are mutex locks.

19. A method according to claim 16, wherein said one of the parallel processors releases the lock after performing step (b).

20. A method according to claim 19, wherein said one of the parallel processors, upon completion of routing for the net, alters the character at the position in the character array that corresponds to the net back to the first character.

21. An apparatus for routing nets in a circuit, said apparatus comprising:

defining a character array that includes plural positions, including a position for each of plural nets in the circuit, wherein each position is capable of holding a character;

means for dividing the plural nets into groups of nets;

means for supplying a plurality of locks and assigning each said group its own lock, wherein each lock allows multiple processors to synchronize their operations with respect to the nets in the group assigned to the lock; and

means for routing said plural nets using parallel processors,

wherein in order for one of the parallel processors to route a portion of a net selected from said plural nets, said one of the parallel processors must first;

(a) obtain the lock corresponding to the group to which the net belongs, and

(b) alter a character at the position in the character array that corresponds to the net from a first character to a second character.

22. A computer-readable medium storing computer-executable process steps for routing nets in a circuit, process steps comprising steps to:

define a character array that includes plural positions, including a position for each of plural nets in the circuit, wherein each position is capable of holding a character;

divide the plural nets into groups of nets;

supply a plurality of locks and assigning each said group its own lock, wherein each lock allows multiple processors to synchronize their operations with respect to the nets in the group assigned to the lock; and

route said plural nets using parallel processors,

wherein in order for one of the parallel processors to route a portion of a net selected from said plural nets, said one of the parallel processors must first;

(a) obtain the lock corresponding to the group to which the net belongs, and

(b) alter a character at the position in the character array that corresponds to the net from a first character to a second character.