Patent ID: 6766502
Filing Date: 2004-07-20
Classification: G06F

Abstract:
A method comprising:identifying partial feasible routing solutions corresponding to each of a subset of a set of wires to be routed, each of the partial feasible routing solutions identifying a feasible route between fixed points in a layout, at least two partial feasible rounting solutions being identified for at least one of the wires to be routed; constructing a routing tree from the identified partial feasible routing solutions for each of the subset of wires to be routed; and following identification of the partial feasible routing solutions, merging the partial feasible routing trees to identify one or more feasible routing solutions for the set of wires to be routed, wherein merging includes selecting between the identified partial feasible routing solutions for each of the subset of wires to identify a partial feasible routing solution that does not conflict with a selected partial feasible routing solution for any of the other wires of the subset of wires.