A Polynomial Time-Optimal Diode Insertion/Routing Algorithm for Fixing Antenna Problem

Antenna problem is a phenomenon of plasma-induced gate-oxide degradation. It directly affects manufacturability of very large scale integration (VLSI) circuits, especially in deep submicron technology using high-density plasma. Diode insertion is a very effective way to solve this problem. Ideally, diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus, it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously, only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper, we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees finding a feasible diode insertion and routing solution whenever one exists. Moreover, we can guarantee to find a feasible solution to minimize a cost function of the form α · L + β · N, where L is the total length of extension wires and N is the total number of vias on the extension wires. Experimental results show that our algorithm is very efficient.