https://scholars.lib.ntu.edu.tw/handle/123456789/332282
Title: | An optimal jumper-insertion algorithm for antenna avoidance/fixing | Authors: | Su, B.-Y. YAO-WEN CHANG |
Keywords: | Physical_design; Reliability; Routing | Issue Date: | 2007 | Journal Volume: | 26 | Journal Issue: | 10 | Start page/Pages: | 1818-1829 | Source: | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems | Abstract: | As the process technology enters the nanometer era, reliability has become a major concern in the design and manufacturing of very large-scale integration circuits. In this paper, we focus on one reliability issue - jumper insertion in routing trees for avoiding/fixing antenna-effect violations at the routing/postlayout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem and present the first optimal algorithm for the tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an O (V) -time optimal jumper-insertion algorithm that uses the minimum number of jumpers to avoid/fix the antenna violations in a routing tree with V vertices. Experimental results show the superior effectiveness and efficiency of our algorithm. © 2007 IEEE. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-34748887657&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/332282 |
ISSN: | 02780070 | DOI: | 10.1109/TCAD.2007.896307 | SDG/Keyword: | Antennas; Design aids; LSI circuits; Nanosystems; Reliability; Nanometer era; Optimal jumper-insertion algorithm; Tree-cutting problem; Computer aided design |
Appears in Collections: | 電子工程學研究所 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.