Patent ID: 6412103
Filing Date: 2002-06-25
Classification: G06F

Abstract:
A method for routing a number of nets (A, B, C, D) in tracks of a channel (100) of an electronic device for the interconnection of terminals (A1-A4; B1-B2; C1-C2; D1-D3) of said nets, said method comprising the steps ofa) generating a vertical constraints graph (200) for said channel; b) selecting a critical node (A) of said vertical constraints graph being a node having a maximum number of cycles; c) generating an enhanced vertical constraints graph (300) by expanding said critical node to contain a subnode (1-4) for each said terminal (A1-A4) belonging to said net (A) which said critical node (A) represents; d) generating a terminal graph (400) comprising said subnodes, a first and a second one of said subnodes being connected by an edge (401-405) in said terminal graph if there is a path between said first subnode and said second subnode in said enhanced vertical constraints graph; e) splitting said critical node into new nodes (Aâ€², Aâ€³, Aâ€²â€³) to break all of said edges (401-405) in said terminal graph to thereby produce a transformed vertical constraints graph (600) wherein the split critical node has no more cycles; f) repeating steps b) to e) until all cycles in said transformed vertical constraints graph are removed; g) assigning of said tracks according to said transformed vertical constraints graph.