×

Method and apparatus for routing groups of paths

  • US 7,069,530 B1
  • Filed: 01/31/2002
  • Issued: 06/27/2006
  • Est. Priority Date: 06/03/2001
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method of routing a net by identifying a set of paths between a set of source routable elements of a net and a set of target routable elements of the net, wherein the set of paths has to have a minimum acceptable number of paths, the method comprising:

  • a) identifying a set of an acceptable number of at least two paths between the set of source routable elements and the set of target routable elements, said identifying comprising;

    1) specifying a first total cost;

    2) performing a first depth-first search to identify the set of at least two paths that each have a cost that does not exceed the first total cost, wherein each path in the set includes a set of expansions from the set of routable-element sources to the set of routable-element targets;

    3) if the search cannot find the acceptable number of paths, incrementing the total cost and performing a second depth-first search to identify the set of paths that each have a cost that does not exceed the incremented total cost, wherein the acceptable number of paths is at least two paths; and

    b) when the acceptable number of paths is identified, using one of the paths to define a route for the net.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×