Patent Document ID: 20120060137
Application ID: 12926505
Patent Flag: 0

Claim One:
1. A method for designing wiring topology for electromigration avoidance, applied for selecting an optimal wiring topology among a plurality of wiring topologies on a chip set, wherein each of the wiring topologies has a plurality of sources, a plurality of sinks and a plurality of wires, each of the wires is directly connected between one of the sources and one of the sinks, each of the sources provides a source current, each of the sinks receives a sink current, an effective current flows from one of the sources into one of the sinks through each of the wires, the method comprising the steps of: calculating the length of all the wires to choose the minimum among the wires as a feasible wire; deciding a capacity of the feasible wire, wherein the capacity is the maximum of the effective current through the feasible wire; deciding the capacity of each of the other wires according to the capacity, the source current and the sink current of the feasible wire; comparing the length of the other wires to choose another feasible wire; repeating said steps until finding all feasible wires to construct a feasible wiring topology; creating a flow network according to the feasible wiring topology; executing an algorithm to iteratively check if a negative cycle existing in the flow network; and removing the negative cycle if existing in the flow network to obtain the optimal wiring topology.