Designing an optimal wiring topology for electromigration avoidance

Abstract

A method for designing an optimal wiring topology for electromigration avoidance is disclosed. The wiring topology includes multiple sources, multiple sinks and multiple wires. The method includes the following steps: A feasible wire, a wire of the shortest length connecting each pair of source and sink, is calculated, and the capacity of each feasible wire is decided. An initial feasible topology is found. A flow network is created based on the initial topology. Negative cycles are iteratively checked and removed until no more negative cycles.