Multi-threaded track assignment

• US 9,477,801 B2
• Filed: 01/28/2010
• Issued: 10/25/2016
• Est. Priority Date: 09/02/2009
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Chakanaker, Abhijit, Majhi, Jayanth, Gao, Tong
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US12/695,436
• Publication Number:
  US 20110055789A1
• Time in Patent Office: 2,462 Days
• Field of Search: 716/125, 716/126, 716/129, 716/130
• US Class Current: 1/1
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments provide techniques and systems for routing nets in a circuit design in parallel. During operation, the system can receive a first set of partitions for a circuit design, wherein each partition in the first set of partitions extends across the circuit design along a first direction. Next, the system can perform, in parallel, track assignment in the first direction on non-overlapping partitions in the first set of partitions. The system can then receive a second set of partitions for the circuit design, wherein each partition in the second set of partitions extends across the circuit design along a second direction which is different from the first direction. Next, the system can perform, in parallel, track assignment in the second direction on non-overlapping partitions in the second set of partitions. In some embodiments, each track assignment process being performed in parallel performs track assignment on a different net.

Claims

1. A computer-implemented method for performing multi-threaded track assignment in a circuit design, the method comprising:

a global routing process in a computer system determining paths for a first set of wires and a second set of wires;

a first thread in the computer system assigning horizontal tracks in a first horizontal partition to the first set of wires that passes through the first horizontal partition;

a second thread in the computer system assigning horizontal tracks in a second horizontal partition to a second set of wires that passes through the second horizontal partition; and

wherein the first thread and the second thread execute in parallel in the computer system, wherein the first horizontal partition and the second horizontal partition do not overlap with each other, wherein the first horizontal partition extends across an entire length of the circuit design along a horizontal direction, wherein the second horizontal partition extends across the entire length of the circuit design along the horizontal direction, and wherein the first thread and the second thread obtain a lock for a net associated with a wire before assigning a track to the wire.

2. A non-transitory computer-readable storage medium storing instructions that, when executed by a computer system, cause the computer system to perform a method for performing multi-threaded track assignment in a circuit design, the method comprising:

determining, by a global routing process, paths for a first set of wires and a second set of wires;

assigning, by a first thread, horizontal tracks in a first horizontal partition to a first set of wires that passes through the first horizontal partition;

assigning, by a second thread, horizontal tracks in a second horizontal partition to a second set of wires that passes through the second horizontal partition; and

wherein the first thread and the second thread execute in parallel, wherein the first horizontal partition and the second horizontal partition do not overlap with each other, wherein the first horizontal partition extends across an entire length of the circuit design along a horizontal direction, wherein the second horizontal partition extends across the entire length of the circuit design along the horizontal direction, and wherein each thread obtains a lock for a net associated with a wire before assigning a track to the wire.

3. A computer-implemented method for performing multi-threaded track assignment in a circuit design, the method comprising:

a global routing process in a computer system determining paths for a first set of wires and a second set of wires;

a first thread in the computer system assigning vertical tracks in a first vertical partition to the first set of wires that passes through the first vertical partition;

a second thread in the computer system assigning vertical tracks in a second vertical partition to a second set of wires that passes through the second vertical partition; and

wherein the first thread and the second thread execute in parallel in the computer system, wherein the first vertical partition and the second vertical partition do not overlap with each other, wherein the first vertical partition extends across an entire length of the circuit design along a vertical direction, wherein the second vertical partition extends across the entire length of the circuit design along the vertical direction, and wherein the first thread and the second thread obtain a lock for a net associated with a wire before assigning a track to the wire.

4. A non-transitory computer-readable storage medium storing instructions that, when executed by a computer system, cause the computer system to perform a method for performing multi-threaded track assignment in a circuit design, the method comprising:

determining, by a global routing process, paths for a first set of wires and a second set of wires;

assigning, by a first thread, vertical tracks in a first vertical partition to a first set of wires that passes through the first vertical partition;

assigning, by a second thread, vertical tracks in a second vertical partition to a second set of wires that passes through the second vertical partition; and

wherein the first thread and the second thread execute in parallel, wherein the first vertical partition and the second vertical partition do not overlap with each other, wherein the first vertical partition extends across an entire length of the circuit design along a vertical direction, wherein the second vertical partition extends across the entire length of the circuit design along the vertical direction, and wherein each thread obtains a lock for a net associated with a wire before assigning a track to the wire.