A polynomial time optimal diode insertion/routing algorithm for fixing antenna problem

Li Da Huang, Xiaoping Tang, Hua Xiang, D. F. Wong, I. Min Liu

Research output: Contribution to journalConference articlepeer-review


Antenna problem is a phenomenon of plasma induced gate oxide degradation. It directly affects manufacturability of 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 to find 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 /spl alpha/ /spl middot/ L + /spl beta/ /spl middot/ N where L is the total length of extension wires and N is the total number of Was on the extension wires. Experimental results show that our algorithm is very efficient.

Original languageEnglish (US)
Article number998315
Pages (from-to)470-475
Number of pages6
JournalProceedings -Design, Automation and Test in Europe, DATE
StatePublished - 2002
Externally publishedYes
Event2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002 - Paris, France
Duration: Mar 4 2002Mar 8 2002

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'A polynomial time optimal diode insertion/routing algorithm for fixing antenna problem'. Together they form a unique fingerprint.

Cite this