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 journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)141-147
Number of pages7
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume23
Issue number1
DOIs
StatePublished - Jan 2004

Keywords

  • Deep submicron
  • Detailed routing
  • Layout
  • Optimization
  • Very large scale integration (VLSI)

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint 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