An optimal jumper-insertion algorithm for antenna avoidance/fixing

作者：Su Bor Yiing^*; Chang Yao Wen

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(10): 1818-1829.

DOI：10.1109/TCAD.2007.896307

• physical_design
• reliability
• routing

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-10
• 单位中国科学院电工研究所