An exact jumper insertion algorithm for antenna effect avoidance/fixing.

As the process technology enters the nanometer era, reliability has become a major concern in the design and manufacturing of VLSI circuits. In this paper we focus on one reliability issue-jumper insertion in routing trees for avoiding/fixing antenna effect violations at the routing/post-layout stages. We formulate the jumper insertion for antenna avoidance/fixing as a 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 lg V)-time exact jumper insertion algorithm that uses the optimum 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. Copyright 2005 ACM.