Antenna problem is a phenomenon of plasma induced gateoxide degradation. It directly affects manufacturability of VLSIcircuits, especially in deep-submicron technology using high density plasma. Diode insertion is a very effective way to solve thisproblem. Ideally diodes are inserted directly under the wires thatviolate antenna rules. But in today's high-density VLSI layouts,there is simply not enough room for iounder-the-wirel. diode insertion for all wires. Thus it is necessary to insert many diodesat legal ieoff-wirel- locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously onlysimple heuristic algorithms were available for this diode insertionand routing problem. In this paper, we show that the diode insertion and routing problem for an arbitrary given number of routinglayers can be optimally solved in polynomial time. Our algorithmguarantees to find a feasible diode insertion and routing solutionwhenever one exists. Moreover, we can guarantee tofind a feasible solution to minimize a cost function of the form lphacdot L + etacdot Nwhere cdot L is the total length of extension wires andcdot N is the total number of vias on the extension wires. Experimental results showthat our algorithm is very efficient.
展开▼
