Optimal Double Via Insertion With On-Track Preference
| Autor: | Kai-Yuan Chao, Kuang-Yao Lee, Cheng-Kok Koh, Ting-Chi Wang |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Mathematical optimization
Linear programming Integrated circuit design Computer Graphics and Computer-Aided Design law.invention Capacitor law Hardware_INTEGRATEDCIRCUITS Bipartite graph Electrical and Electronic Engineering Routing (electronic design automation) Special case Integer programming Software Mathematics Integer (computer science) |
| Zdroj: | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 29:318-323 |
| ISSN: | 1937-4151 0278-0070 |
| DOI: | 10.1109/tcad.2009.2035581 |
| Popis: | As on-track double vias take less routing resources and have better electrical characteristics, we study in this paper the problem of double via insertion with a preference for on-track double vias (DVI/ON) in a postrouting stage. The primary goal is to insert as many double vias as possible, and maximizing the number of on-track double vias is a secondary objective. We present a zero-one integer linear program-based approach to optimally solve the DVI/ON problem. Moreover, we also discuss a special case of the DVI/ON problem and present a maximum-weighted bipartite matching-based optimal approach. Experimental results indicate that our approaches outperform existing algorithms in terms of solution quality. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|