Patent Document ID: 8239808
Application ID: 12630791
Patent Flag: 1

Claim One:
1. A method for routing from a source to a sink on a chip with a chip dimension, comprising: identifying a first bounding box on the chip defining a first search region, wherein said first bounding box has a size which is smaller than said chip dimension; performing graph traversal solely within the first search region using a source-sink routing path estimator to find a shortest path for a given net of a source sink list according to a shortest path algorithm by identifying a source sink routing path; determining by a routing processor whether the shortest path has been found; if so, then completing routing for a net; if not, incrementing the size of the first search region according to a defined factor of an increment index to identify a second bounding box defining a second search region which contains the first search region; and performing graph traversal again using a source-sink routing path estimator but only in an incremented portion of the second search region which is outside of the first search region.