Patent ID: 8386983

Claim:
A method of parallel routing of a circuit design, comprising: determining placement of a netlist of the circuit design on a target device; defining a plurality of regions of the target device; assigning the plurality of regions to respective sets of processors, each set including at least one processor; performing global routing of nets of the netlist on the target device, wherein a global route of each net restricts the net to one or more possible routes through a corresponding subset of the plurality of regions; concurrently performing local routing of the netlist within the plurality of regions by the respective sets of processors, wherein within each region the local routing of the netlist is performed by only the respective set of at least one processor; wherein for local routing a net of the netlist within a first region of the plurality of regions, the net having a destination outside the first region, the local routing includes: determining possible routes from a source of the net in the first region to one or more edge-pins on a boundary between the first region and an adjacent region in the subset of regions; and communicating messages that indicate one or more of the one or more edge-pins as options for continuing a route of the net to a destination, the messages communicated from a processor of the one or more processors assigned the first region to a processor of the one or more processors assigned the adjacent region; and in response to a failure to locally route a net within a first region of the subset of the plurality of regions: shifting boundaries between two or more regions including the first region and a second region of the plurality of regions; and locally rerouting the net within one or more regions in the corresponding subset of the plurality of regions.