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

doi:10.1109/DATE.2002.998315

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

7 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002
Editors	Carlos Delgado Kloos, Jose da Franca
Place of Publication	United States
Publisher	IEEE
Pages	470-475
Number of pages	6
DOIs	https://doi.org/10.1109/DATE.2002.998315
Publication status	Published - Mar 2002
Event	2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002 - Le Palais des Congrès, Paris, France Duration: 4 Mar 2002 → 8 Mar 2002 https://past.date-conference.com/proceedings-archive/2002/YEAR.HTM (Conference proceedings)

Publication series

Name	Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE
ISSN (Print)	1530-1591

Conference

Conference	2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002
Country/Territory	France
City	Paris
Period	4/03/02 → 8/03/02
Internet address	https://past.date-conference.com/proceedings-archive/2002/YEAR.HTM (Conference proceedings)

Access to Document

10.1109/DATE.2002.998315

Cite this

Huang, L. D., Tang, X., Xiang, H., Wong, D. F., & Liu, I. M. (2002). A polynomial time optimal diode insertion/routing algorithm for fixing antenna problem. In C. D. Kloos, & J. da Franca (Eds.), Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002 (pp. 470-475). (Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE). IEEE. https://doi.org/10.1109/DATE.2002.998315

Huang, Li Da ; Tang, Xiaoping ; Xiang, Hua et al. / A polynomial time optimal diode insertion/routing algorithm for fixing antenna problem. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002. editor / Carlos Delgado Kloos ; Jose da Franca. United States : IEEE, 2002. pp. 470-475 (Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE).

@inproceedings{9ca39695391f41cea822cc955bad45b6,

title = "A polynomial time optimal diode insertion/routing algorithm for fixing antenna problem",

abstract = "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.",

author = "Huang, {Li Da} and Xiaoping Tang and Hua Xiang and Wong, {D. F.} and Liu, {I Min}",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCR-9912390. Publisher copyright: {\textcopyright} 2002 IEEE; 2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002 ; Conference date: 04-03-2002 Through 08-03-2002",

year = "2002",

month = mar,

doi = "10.1109/DATE.2002.998315",

language = "English",

series = "Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE",

publisher = "IEEE",

pages = "470--475",

editor = "Kloos, {Carlos Delgado} and {da Franca}, Jose",

booktitle = "Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002",

address = "United States",

url = "https://past.date-conference.com/proceedings-archive/2002/YEAR.HTM",

}

Huang, LD, Tang, X, Xiang, H, Wong, DF & Liu, IM 2002, A polynomial time optimal diode insertion/routing algorithm for fixing antenna problem. in CD Kloos & J da Franca (eds), Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002. Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE, IEEE, United States, pp. 470-475, 2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002, Paris, France, 4/03/02. https://doi.org/10.1109/DATE.2002.998315

A polynomial time optimal diode insertion/routing algorithm for fixing antenna problem. / Huang, Li Da; Tang, Xiaoping; Xiang, Hua et al.
Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002. ed. / Carlos Delgado Kloos; Jose da Franca. United States: IEEE, 2002. p. 470-475 (Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

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

AU - Huang, Li Da

AU - Tang, Xiaoping

AU - Xiang, Hua

AU - Wong, D. F.

AU - Liu, I Min

PY - 2002/3

Y1 - 2002/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893751802&partnerID=8YFLogxK

U2 - 10.1109/DATE.2002.998315

DO - 10.1109/DATE.2002.998315

M3 - Conference proceeding

T3 - Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE

SP - 470

EP - 475

BT - Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002

A2 - Kloos, Carlos Delgado

A2 - da Franca, Jose

PB - IEEE

CY - United States

T2 - 2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002

Y2 - 4 March 2002 through 8 March 2002

ER -

Huang LD, Tang X, Xiang H, Wong DF, Liu IM. A polynomial time optimal diode insertion/routing algorithm for fixing antenna problem. In Kloos CD, da Franca J, editors, Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002. United States: IEEE. 2002. p. 470-475. (Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE). doi: 10.1109/DATE.2002.998315

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this