WiT: Optimal Wiring Topology for Electromigration Avoidance

檔案

日期

2012-04-01

期刊名稱

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS

摘要

Due to excessive current densities, electromigration (EM) may trigger a permanent open- or short-circuit failure in signal wires or power networks in analog or mixed-signal circuits. As the feature size keeps shrinking, this effect becomes a key reliability concern. Hence, in this paper, we focus on wiring topology generation for avoiding EM at the routing stage. Prior works tended towards heuristics; on the contrary, we first claim this problem belongs to class P instead of class NP-hard. Our breakthrough is, via the proof of the greedy-choice property, we successfully model this problem on a multi-source multi-sink flow network and then solve it by a strongly polynomial time algorithm. Experimental results prove the effectiveness and efficiency of our algorithm.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料