Patent ID: 6877146
Filing Date: 2005-04-05
Classification: G06F

Abstract:
1. A method of specifying routes for a group of at least two nets, the method comprising: a) specifying a total cost; b) performing a first depth-first search to identify, for the group of at least two nets, a complete routing solution that has a cost that does not exceed the total cost, wherein a routing solution for a group of nets includes a route for each net in the group, wherein performing said first depth-first search comprises: identifying a first set of routes for a first net in the group, wherein each route has a cost; individually examining the first-set routes until the complete routing solution is identified or until all first-set routes have been examined without identifying the complete routing solution; and wherein individually examining a particular first-set route includes determining whether, in the region with the particular first-set route embedded, a first partial routing solution for the nets other than the first net exists such that the cost of the particular first-set route plus the first partial solution does not exceed the total cost; and c) if the search cannot find the complete routing solution, incrementing the total cost and performing a second depth-first search to identify a complete routing solution for the group of nets that has a cost that does not exceed the incremented total cost.