Non-tree routing for reliability and yield improvement

ABSTRACT

We propose to introduce redundant interconnects for manufacturing yield and reliability improvement. By introducing redundant interconnects, the potential for open faults is reduced at the cost of increased potential for short faults; overall, manufacturing yield and fault tolerance can be improved. We focus on a post-processing, tree augmentation approach which can be easily integrated in current physical design flows. Our contributions are as follows:• We formulate the problem as a variant of the classical 2-edge-connectivity augmentation problem in which we take into account such practical issues as wirelength increase budget, routing obstacles, and use of Steiner points.• We show that an optimum solution can always be found on the Hanan grid defined by the terminals and the corners of the feasible routing region.• We give a compact integer program formulation which, for up to 100 terminal nets, is solved in practical runtime by the commercial optimization package CPLEX.• We give a well-scaling greedy algorithm which has practical runtime up to 1,000 terminals, and comes on the average within 1--2% of the optimum computed by CPLEX.• We give a comprehensive experimental study comparing the solution quality and runtime of our methods with the best reported methods for 2-edge-connectivity augmentation, including a sophisticated heuristic based on minimum-weight branchings [9] and a recent genetic algorithm [14].Experiments on randomly generated and industry testcases show that our greedy augmentation method achieves significant increase in reliability (as measured by the percentage of biconnected tree edges) with very small increase in wirelength. For example, on 1,000 terminal nets the average percentage of biconnected tree edges is 34.19% for a wire-length increase of only 1%, and 87.73% for a wirelength increase of 20%. SPICE simulations on industry routed nets show that non-tree routing has the additional benefit of reducing maximum sink delay by an average of 28.26% compared to Steiner routing, and by an average of 3.72% compared to timing optimized routing. SPICE simulations further imply that non-tree routing has smaller delay variation due to process variability.

REFERENCES

• 1: Manjit Borah , Robert Michael Owens , Mary Jane Irwin, A fast and simple Steiner routing heuristic, Discrete Applied Mathematics, v.90 n.1-3, p.51-67, Jan. 15, 1999 [doi>10.1016/S0166-218X(98)00085-7]
• 2: V.K.R. Chiluvuri. Yield optimization in physical design: a review. In Proceedings of the Fifth ACM/SIGDA Physical Design Workshop, pages 198--206, 1996.
• 3: José Pineda de Gyvez, Yield modeling and BEOL fundamentals, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.135-163, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368821]
• 4: K.P. Eswaran and R.E. Tarjan. Augmentation problems. SIAM Journal on Computing, 5:653--665, 1976.
• 5: M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization. Second edition. Springer-Verlag, Berlin, 1993.
• 6: M. Grötschel, C.L. Monma, and M.Stoer. Design of survivable networks. In Handbooks in Operations Research and Management Science, vol. 7: Network Models, pages 617--672, Amsterdam, 1995. North-Holland.
• 7: Tsan-Sheng Hsu, Graph augmentation and related problems: theory and practice, University of Texas at Austin, Austin, TX, 1993
• 8: http://www-device.eecs.berkeley.edu/~ptm/.
• 9: Samir Khuller , Balaji Raghavachari , An Zhu, A uniform framework for approximating weighted connectivity problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.937-938, January 17-19, 1999, Baltimore, Maryland, United States
• 10: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin , Ching-Yen Ho, New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing, Proceedings of the 33rd annual conference on Design automation, p.395-400, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240594]
• 11: B. A. McCoy and G. Robins. Non-tree routing. IEEE Transactions on Computer-Aided Design, 14(6):790--784, June 1995.
• 12: M. Orshansky. Personal Communication. April 2002.
• 13: Michael Orshansky , Linda Milor , Pinhong Chen , Kurt Keutzer , Chenming Hu, Impact of systematic spatial intra-chip gate length variability on performance of high-speed digital circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 14: Günther R. Raidl , Ivana Ljubić, Evolutionary local search for the edge-biconnectivity augmentation problem, Information Processing Letters, v.82 n.1, p.39-45, April 15, 2002 [doi>10.1016/S0020-0190(01)00285-X]
• 15: S.-C. Wong, G.-Y. Lee, and D.-J. Ma. Modeling of interconnect capacitance, delay, and crosstalk in vlsi. IEEE Trans. on Semiconductor Manufacturing, 13(1):753--782, 2000.
• 16: Tianxiong Xue , Ernest S. Kuh, Post routing performance optimization via multi-link insertion and non-uniform wiresizing, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.575-580, November 05-09, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Performance, Theory