# US 2010/0169858 A1 · Method and apparatus for performing parallel routing using a multi-threaded routing procedure

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169858 A1
- Document ID: US20100169858A1
- Status: Published application
- Kind: A1
- Application number: 12/317,789
- Filed: 2008-12-29
- Published: 2010-07-01
- Earliest claimed: 2008-12-29
- Assignees: Altera Corporation
- Inventors: Vaughn Betz; Jordan Swartz; Vadim Gouterman
- Web page: https://patentgrep.com/patent/US20100169858A1

## CPC

- G06F 30/394: Routing (G06F30/396 takes precedence)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for designing a system to be implemented on a target device includes 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. The nets in the system are assigned to a plurality of threads to be routed. The threads are executed so that a plurality of the nets are routed in parallel within their corresponding bounding box.

## Claims

### Claim 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 threads so that a plurality of the nets are routed in parallel within their corresponding bounding box.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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

### Claim 4

The method of Claim I, wherein 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.

### Claim 5 (depends on 1)

The method of claim 1, wherein 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 position of their corresponding bounding boxes to the partition line.

### Claim 6 (depends on 1)

The method of claim 1, wherein 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 position of their corresponding bounding boxes to the partition line.

### Claim 7 (depends on 1)

The method of claim 1, wherein 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 the fewest number of bounding boxes possible; and
assigning the nets in response to their position of their corresponding bounding boxes to the partition line.

### Claim 8 (depends on 1)

The method of claim 1, wherein assigning the nets comprises:
identifying dependencies of the nets;
identifying sets of nets such that there are no dependencies between the nets in the sets;
assigning a different thread to route each of the sets of nets; and
routing the sets in parallel.

### Claim 9 (depends on 8)

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

### Claim 10 (depends on 8)

The method of claim 8, wherein 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.

### Claim 11 (depends on 1)

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

### Claim 12

The method of Claim I, wherein each of the plurality of threads is executed by one of a separate processor or a separate processor core.

### Claim 13 (depends on 1)

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

### Claim 14 (depends on 1)

The method of claim 1, wherein 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;
partitioning the target device with a second partition line, where the second partition line is in a different location or direction than the first partition line;
assigning nets contained within each partition to be routed by one of the plurality of threads in parallel;
assigning remaining nets in the design to be routed to one of the plurality of threads to be routed serially.

### Claim 15 (depends on 1)

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.

### Claim 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 threads so that a plurality of the connections are routed in parallel within their corresponding bounding box.

### Claim 17 (depends on 16)

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

### Claim 18 (depends on 16)

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.

### Claim 19

A computer readable medium including sequences of instructions, the sequences of instructions including instructions which when executed causes a computer to perform:
generating bounding boxes on the target device for nets in the system where the bounding box defines routing resources that may be used for routing its corresponding net;
routing a plurality of nets in parallel where the plurality of nets routed in parallel have corresponding bounding boxes that are free from overlap.

### Claim 20 (depends on 19)

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

### Claim 21 (depends on 19)

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

### Claim 22 (depends on 21)

The computer readable medium of claim 21, wherein determining which nets in the system to route in parallel comprises:
partitioning the target device with a partition line;
assigning nets having bonding 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.

### Claim 23 (depends on 19)

The computer readable medium of claim 19, wherein 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.

### Claim 24 (depends on 19)

The computer readable medium of claim 19, wherein 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.

### Claim 25 (depends on 19)

The computer readable medium of claim 19, wherein 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 the fewest number of bounding boxes possible; and
assigning nets in a first partition to be routed in parallel with nets in a second partition.

### Claim 26 (depends on 19)

The computer readable medium of claim 19, wherein 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 the nets in the sets;
assigning a different thread to route each of the sets of nets; and
routing the sets in parallel.

### Claim 27 (depends on 26)

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

### Claim 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 may 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.

### Claim 29 (depends on 28)

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 the net.

### Claim 30 (depends on 28)

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.

### Claim 31 (depends on 30)

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

### Claim 32 (depends on 30)

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.

### Claim 33 (depends on 30)

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

### Claim 34 (depends on 28)

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

### Claim 35 (depends on 30)

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.

### Claim 36 (depends on 34)

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