Method and apparatus for performing parallel routing using a multi-threaded routing procedure

1. A method for designing a system to be implemented on a target device, comprising:

generating bounding boxes on the target device for nets in the system where a bounding box identifies routing resources available for routing its corresponding net;

assigning the nets in the system to a plurality of threads to be routed; and

executing the plurality of threads so that a plurality of the nets are routed in parallel within their corresponding bounding boxes, wherein at least one of the generating, assigning, and executing is performed by a processor.

2. The method of claim 1 , wherein the generating the bounding box comprises defining an area on the target device that include all terminals of a net.

3. The method of claim 1 , wherein the assigning the nets comprises assigning nets with overlapping bounding boxes to a same thread.

4. The method of claim 1 , wherein the assigning the nets comprises:

partitioning the target device with a partition line;

assigning nets having bonding boxes that cross the partition line to one of the plurality of threads to be routed serially; and

assigning remaining nets in each partition to be routed by one of the plurality of threads in parallel after routing the nets having bounding boxes that cross the partition line.

5. The method of claim 1 , wherein the assigning the nets comprises:

partitioning the target device with a partition line where the partition line partitions the target device into equally sized areas; and

assigning the nets in response to the positions of their corresponding bounding boxes relative to the partition line.

6. The method of claim 1 , wherein the assigning the nets comprises:

partitioning the target device with a partition line where the partition line partitions the target device such that an amount of routing work to be done for nets in each partition is balanced; and

assigning the nets in response to the positions of their corresponding bounding boxes relative to the partition line.

7. The method of claim 1 , wherein the assigning the nets comprises:

partitioning the target device with a partition line where the partition line partitions the target device such that an amount of routing work to be done for nets in each partition is balanced and the partition line intersect a fewest number of bounding boxes; and

assigning the nets in response to positions of their corresponding bounding boxes relative to the partition line.

8. The method of claim 1 , wherein the assigning the nets comprises:

identifying dependencies of the nets;

identifying sets of nets such that there are no dependencies between nets in different sets;

assigning a different thread to route each of the sets of nets; and

routing the sets in parallel.

9. The method of claim 8 , further comprising assigning nets with a greatest number of dependencies before nets with fewer or no dependencies.

10. The method of claim 8 , wherein the identifying dependencies of the nets comprises determining whether a bounding box corresponding to a first net overlaps with a bounding box corresponding to a second net.

11. The method of claim 1 , further comprising adjusting a size of a bounding box upon determining that a legal solution for routing a net in the bounding box could not be found.

12. The method of claim 1 , wherein each of the plurality of threads is executed by one of a separate processor or a separate processor core.

13. The method of claim 1 , wherein a net comprises a source and one or more sinks.

14. The method of claim 1 , wherein the assigning the nets comprises:

partitioning the target device with a first partition line;

assigning nets within each partition to be routed by one of the plurality of threads in parallel;

further partitioning the target device with a second partition line, where the second partition line is at a location or in a direction different from that of the first partition line;

assigning nets contained within each partition to be routed by one of the plurality of threads in parallel; and

assigning remaining nets in the system to be routed to one of the plurality of threads to be routed serially.

15. The method of claim 1 , wherein an order in which the nets are routed is chosen in a manner that is independent of a number of processors and a precise execution time of different threads such that results generated maintain determinism and sequential equivalence.

16. A method for designing a system to be implemented on a target device, comprising:

generating bounding boxes on the target device for connections in the system where a bounding box identifies routing resources available for routing its corresponding connection;

assigning the connections in the system to a plurality of threads to be routed; and

executing the plurality of threads so that a plurality of the connections are routed in parallel within their corresponding bounding boxes, wherein at least one of the generating, assigning, and executing is performed by a processor.

17. The method of claim 16 , wherein a connection comprises a source and a sink.

18. The method of claim 16 , further comprising routing a subset of the connections of a net serially to produce a partial routing tree divided into two or more portions, where each portion is within a partition of the target device and each of the partial routing tree portions is sent to a separate thread to route the subset of the remaining net connections within that partition in parallel, where routing of each thread is constrained to lie within a device partition it has been assigned.

19. A non-transitory computer readable medium including sequences of instructions, the sequences of instructions including instructions which when executed causes a computer to perform a method comprising:

generating bounding boxes on a target device for nets in a system where a bounding box defines routing resources that can be used for routing its corresponding net; and

routing a plurality of nets in parallel where the plurality of nets routed in parallel have corresponding bounding boxes that are free from overlap.

20. The non-transitory computer readable medium of claim 19 , wherein the generating the bounding box comprises defining an area on the target device that includes all terminals of a net.

21. The non-transitory computer readable medium of claim 19 , further comprising instructions which when executed causes the computer to further perform a method comprising determining which nets in the system to route in parallel.

22. The non-transitory computer readable medium of claim 21 , wherein the determining which nets in the system to route in parallel comprises:

partitioning the target device with a partition line;

assigning nets having bounding boxes that cross the partition line to be routed serially first; and

assigning remaining nets in a first partition to be routed in parallel with remaining nets in a second partition.

23. The non-transitory computer readable medium of claim 21 , wherein the determining which nets in the system to route in parallel comprises:

partitioning the target device with a partition line where the partition line partitions the target device into equally sized areas; and

assigning nets in a first partition to be routed in parallel with nets in a second partition.

24. The non-transitory computer readable medium of claim 21 , wherein the determining which nets in the system to route in parallel comprises:

partitioning the target device with a partition line where the partition line partitions the target device such that an amount of routing work to be done for nets in each partition is balanced; and

assigning nets in a first partition to be routed in parallel with nets in a second partition.

25. The non-transitory computer readable medium of claim 21 , wherein the determining which nets in the system to route in parallel comprises:

partitioning the target device with a partition line where the partition line partitions the target device such that an amount of routing work to be done for nets in each partition is balanced and the partition line intersect a fewest number of bounding boxes; and

assigning nets in a first partition to be routed in parallel with nets in a second partition.

26. The non-transitory computer readable medium of claim 21 , wherein the determining which nets in the system to route in parallel comprises:

identifying dependencies of the nets;

identifying sets of nets such that there are no dependencies between nets in different sets;

assigning a different thread to route each of the sets of nets; and

routing the sets in parallel.

27. The non-transitory computer readable medium of claim 26 , further comprising instructions which when executed causes the computer to further perform a method comprising assigning nets with a greatest number of dependencies to be routed before nets with fewer or no dependencies.

28. A routing unit, comprising:

a bounding box unit to generate a bounding box on a target device for each net to be routed where the bounding box defines routing resources on the target device that can be used for routing a net; and

a scheduling unit to schedule routing a plurality of nets in parallel where the plurality of nets routed in parallel have corresponding bounding boxes that are free from overlap.

29. The routing unit of claim 28 , further comprising a work assessment unit to estimate an amount of work required for routing each of the nets to be routed based upon a number of fanouts in each net.

30. The routing unit of claim 28 , further comprising a partitioning unit to partition the target device into a plurality of partitions with one or more partition lines.

31. The routing unit of claim 30 , wherein the one or more partition lines partitions the target device into equal areas.

32. The routing unit of claim 30 , wherein each of the plurality of partitions includes nets which require approximately a same amount of work for routing.

33. The routing unit of claim 30 , wherein the one or more partition lines are generated to reduce a number of nets with bounding boxes that cross one of the one or more partition lines.

34. The routing unit of claim 28 , further comprising a dependency identification unit to identify nets having bounding boxes which overlap one another as having dependencies.

35. The routing unit of claim 30 , wherein the scheduling unit schedules the plurality of nets to be routed based upon positions of the bounding boxes of the nets relative to the one or more partition lines.

36. The routing unit of claim 34 , wherein the scheduling unit schedules the plurality of nets based upon their dependencies.