Abstract routing of logic networks for custom module generation

ABSTRACT

This paper describes a switchbox-type router for custom VLSI module generation as performed by a module planner. A module is decomposed into abstract cells consisting of global routes and Boolean functional specifications. Each abstract cell is given to a cell synthesizer which generates the circuit layout and through-the-cell routing. Abstract routing for a module planner is in some sense similar to switchbox routing to the degree that all of the routes are generated internally within a rectangular boundary (routes are coming from four sides). The principle difference with respect to standard switchbox routing is at the geometric level, where a cell synthesizer generates the routing conduction layers along with circuit devices for each abstract cell within this rectangular region. The aspects of this paper which are thought to be novel contributions are 1) a relative pin assignment algorithm for the abstract cells; 2) a global routing penalty function which not only considers previous routes, but also considers gate complexity within the cells; 3) an efficient optimization algorithm for minimizing the number of tracks running through the module.

REFERENCES

• Bern86: M W Bern, Two probabilistic results on rectilinear Steiner trees, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.433-441, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12175]
• BrFu85: F. Brglez, H. Fujiwara, "A Neutral Netlist of 10 Combinational Benchmark Circuits and a Target Translator in Fortran, Proceedings of the lnternatior*al Symposium on Circuit8 and 3:,jstems, Vol. 2, June 1985, pp. 695-698.
• BuPe83: M. Burstein, R. Pelavin, "Hierarchical Wire Routing", IEEE Transactions o~ Computer-Aided DesigN, Vol. CAD-2, No. 4, October 1983, pp. 223-234.
• Ceda86: Cedar-32, Control Logic Specifications from the Center for Supercomputing l~esearch and Development, University of Illinois &t Urbana-Champaign, 1986.
• Deut76: David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804843]
• DoHi83: W. E. I)onath, J. B. Hicksoa, Jr., "Procedure for Connetting N Points with Near-Minimum Cost", IBM Technical Disclosure Bulletin, Vol. 25, No. I1A, April 1983, pp. 5571-5575.
• DuKe85: A. E. Dunlop, B. W. Kernighan, "A Procedure for Placement of Standard-Cell VLSI Circuits", IEEE Transactions or, Computer-Aided Design, Vol. CAD-4, No. 1, January 1985, pp. 92- 98.
• FiMa82: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• Fish78: Robert S. Fisher, A multi-pass, multi-algorithm approach to PCB routing, Proceedings of the 15th conference on Design automation, p.82-91, June 19-21, 1978, Las Vegas, Nevada, United States
• GaJo77: M. R. Garry, D. S. Johnson, "The Rectilinear Steiaer Tree Problem Is NP-Complete", SIAM Journal of Applied Mathemat. its, "Col. 32, No. 4, June 1977, pp. 82{}-834.
• GiOt85: L. P. P. P. van Ginneken, R. H. J. M. Otten, "Global Wiring for Custom Layout Design", Proceedings of the International Symposium on Cireuit~ and Systems, Vol. 1, June 1985, pp. 207-208.
• Hana66: M. Hanan, "On Steiner's Problem with Rectilinear Distance", SIAM Journal of Applied Mathematics, Vol. 14, No. 2. March 1966, pp. 255-265.
• HaSt71: Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
• HeGa85: Steven T. Healey , Daniel D. Gajski, Decomposition of logic networks into silicon, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.162-168, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317852]
• Heal87: S. T. }.qealey, "Abstract Partitioning and Routing of Logic Networks for Custom Module Generation", University of Illinois at Urbana-Chanapaign, Department of Computer Science Report UIUCDCS-R-87-1326, 1987.
• HeKu85: S. T. l-lenity, W. J. Kubitz, "Abstract Partitioning of Logic Networks for Custom Module Generation", Proceedin9s of the fn~ernational Conference or~ Computer-Aided Design, November 1985, pp. 140-142.
• Hitc69: R. B. Hitchcock, Cellular wiring and the cellular modeling technique, Proceedings of the 6th annual conference on Design Automation, p.25-41, January 1969 [doi>10.1145/800260.809015]
• KeLi70: B. W. Kernighan, S. Lin, "An Efficient Heuristic Proordure for Partitioning Graphs", The Bell System Technical Jodrnal, Vol. 49, No. 2, February 1970, pp. 291-307. I
• KeSP73: B. W. Kernighan , D. G. Schweikert , G. Persky, An optimum channel-routing algorithm for polycell layouts of integrated circuits, Proceedings of the 10th workshop on Design automation, p.50-59, June 25-27, 1973
• KiMS84: J. H. Kim, J. McDermott, D. P. Siewiorek "Expldlting Domain Knowledge in IC Cell Layout", {EEE Design and Tes~,.I Vol. I, No. 3, August 1984, pp. 52-64.
• KoWe85: P. W. Kollaritsch, N. H. E. Weste, "TOPOLOGIgER: An Expert System Translator of Tran:dstor Connectivity to Syn~bolic Cell Layout", IEEE Journal of Solid-State Cireuita, Vol. SC--20i No. 3, June t985, pp. 799-804.
• LeBH76: J. H. Lee, N. K. Bose, F. K. Hwang, "Use of Ste~er's Problem in Suboptimal Routing in Rectilinear Metric", IEEE Transactions on Circuits and Systems, Vol. CAS-23, No. 7. July 1976, pp. 470--476.
• LiMa84: J. T. Li, M..Marek-Sadowska, "Global Routing for Gate Array", IEEE Transaetion~ on Computer-Aided De~t'gnt Vol. CAD-3, No. 4, October 1984, pp. 298-307.
• Lins84: 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
• LuGa84: Chidchanok Lursinsap , Daniel Gajski, Cell compilation with constraints, Proceedings of the 21st conference on Design automation, p.103-108, June 25-27, 1984, Albuquerque, New Mexico, United States
• LuGa85: C. Lursinsap, D. Gajski, "Methods of Cell Compilation with Constraints", Proeeedinfs of the IEEE International Conference on Computer Design: VLSI ig Computers, October 1985, pp. 303~307.
• MeCo80: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• PaSK85: A. M. Patel, N. L. Soong, R. K. Korn, "Hierarchical VLS{ Routing - An Approximate Routing Procedure", IEEE Transactions on Computer-Aided Design, Vol. CAD-4, No. 2, April 1985, pp. 121-12~}.
• Pers76: G. Persky, PRO - an automatic string placement program for polycell layout, Proceedings of the 13th conference on Design automation, p.417-424, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804842]
• Reck87: W. A. Reckwerdt, Master's Thesis - in preparation, Department of Computer Science, University of Illinois at Urbana- Champaign, 1987.
• Souk81: J. Soukup, "Circuit Layout", Proceedlngs of the 1EEE, Vol. {~9, No. 10, October 198l, pp. 1281-1304.
• Tera85: M. Terai, "A Method of Improving the Terminal Assignment in the Channel Routing for Gate Arrays", IEEE Transactions o~z Computer-Aided Design, Vol. CAD-4, No. 3, July 1985, pp. 329-336.
• TiTi83: B. S. Ting, B. N. Tien, "Routing Techniques for Gate Array", IEEE Transactions on Computer-Aided Design, Vol. CAD-2, No. 4, October 1983, pp. 301-312.
• VeKi83: M. P. Vecchi, S. Kirkpatrick, "Global Wiring by Simulated Annealing", {EEE Transaetior~s on Computer-Aided Design, Vol. CAD-2, No. 4, October 1983~ pp. 215-222.
• XiTo81: Xiong Ji-Guang , Tokinori Kozawa, An algorithm for searching shortest path by propagating wave fronts in four quadrants, Proceedings of the 18th conference on Design automation, p.29-36, June 29-July 01, 1981, Nashville, Tennessee, United States
• YuKu85: M. L. Yu, W. J. Kubitz, "Linear-Time Heuristics for Cell Layout Synthesis Under Constraints", Proceedings of the International Conference on Computer-Aided Design, November 1985, pp. B4-66.
• YuKu86: M. L. Yu, W. J. Kubitz, "Characterization of an Automatic Random Logic Layout Synthesizer", Proeeedino~ ~f the Ir~ternatior~al Coa{erenee on Computer-Aided Desifn, November 1988, pp. 70-73.
• Yu86: M. L. Yu, "Automatic Random Logic Layout Synthesis - A Module Generator Approach", University of Illinois at Urbana- Champaign, Department of Computer Science Report UIUCDGS-R- 86-1244, 1986.

INDEX TERMS

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

General Terms:
Design