A new interactive supply/demand router with rip-up capability for printed circuit boards

ABSTRACT

In this router, an iterative, non-sequential “supply/demand” router attempts to find conflict-free (non-crossing or overlapping) paths for each net. If 100% interconnection is not achieved with supply/demand routing, the rip-up procedure removes enough nets to eliminate all conflicts. Nets that are ripped-up are returned to the supply/demand router for re-routing. The new router was compared to a Lee-type router on six double-sided boards, and on average obtained 6.8% higher completion.

REFERENCES

• 1: V. Chvatal, ~A Greedy Heuristic for the Set-Covering Problem~, Mathematics of Operation~ Research, 4, (1979) 233-235.
• 2: William A. Dees, Jr. , Patrick G. Karger, Automated rip-up and reroute techniques, Proceedings of the 19th conference on Design automation, p.432-439, January 1982
• 3: T. A. Feo and D. S. Hochbaum, "A Lagrangian Relaxation Method for Testing the Infe~ibility of Certain VLSI Routing Problems', unpublished manuscript, November, 1985.
• 4: M. L. Fisher, "The Lagrangian Relaxation Method for Solving Integer Programming Problems", Management Science, ~7, (1081) 1- 18.
• 5: M. Held, P. Wolfe, and H. Crowder, "Validation of Subgradient Optimization", Mathematical Programming, 6, (1974) 62-88.
• 6: T. C. Hu and M. T. Shing, "A Decomposition Algorithm for Circuit Routing", in Mathematical Procrammin~ Studll e4 (R. W. Cottte, ed., North Holland, Amsterdam, 1985), pp. 87-103.
• 7: L. Kou, G. Markowsky, and L. Berman, "A Fast Algorithm for Steiner Trees', Acta }nformatica, 15, (1981) 141-145.
• 8: C. Y. Lee, "An Algorithm for Path Connections and its Applications", IRE Trans. Electron. Comput., EC-IO, (1901)346-355.
• 9: Ralph Linsker, An iterative-improvement penalty-function-driven wire routing system, IBM Journal of Research and Development, v.28 n.5, p.613-624, September 1984
• 10: A. Moore and C. Ravitz, "Weighted and Iterative Multi-Wire Routing", IBM Technical Disclosure Bulletin, ~5, (1982) 3619-3628.
• 11: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 12: Frank Rubin, An iterative technique for printed wire routing, Proceedings of the 11th workshop on Design automation, p.308-313, January 1974
• 13: H. M. Salkin, Integer Programming, (Addison-Wesley, Reading, MA, 1975).
• 14: J. F. Shapiro, "A Survey of Lagrangian Techniques for Discrete Optimization", Annals of Discrete Mathematics, 5, (1979) 113-138.
• 15: J. Soukup, Global router, Proceedings of the 16th Conference on Design automation, p.481-484, June 25-27, 1979, San Diego, CA, United States
• 16: M. P. Veeehi and S. Kirpatrick, "Global Wiring by Simulated Annealing", IEEE Trans. Computer-Aided Design CAD-~, (1983) 215- 222.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  C. Computer Systems Organization

General Terms:
Design