Method and apparatus for performing parallel routing using a multi-threaded routing procedure
AssigneeAltera Corporation
InventorsVaughn Betz, Jordan Swartz, Vadim Gouterman
Life of this patent
Estimating the term…
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.
Claims36
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.