Chip-level area routing

ABSTRACT

We present a chip-level area router for modern VLSI technologies. The gridless area router can handle any number of layers, as well as rectilinear blockage areas on any layer. A two-stage divide-and-conquer strategy is applied so that the area router can handle very large chips. The first stage includes an area-minimization loop by using an efficient and accurate multi-layer global router. The global router minimizes the chip area while performing the global routing. According to the global routing results, switchboxes are generated for the whole chip area. Then the switchboxes are sent to the second stage for detailed routing, in which a tile-expansion based switchbox router is used. With multi-level rip-up and re-route techniques, the detailed router is shown to be able to complete many difficult switchboxes. The router was tested on the MCNC building block circuits. Our results show better chip areas than the best previously published results.

REFERENCES

• 1: L.E. Liu, "Global Routing and Pin Assignment for Multilayer Chip-level Layout," Ph.D. Thesis, University of Washington, Seattle, Nov. 1997.
• 2: W. Swartz and C. Sechen, "'New Algorithms for the Placement and Routing of Macro Cells" IEEE International Conference on Computer Aided Design, pp. 336-339, Nov. 1990.
• 3: Hidetoshi Onodera , Yo Taniguchi , Keikichi Tamaru, Branch-and-bound placement for building block layout, Proceedings of the 28th conference on ACM/IEEE design automation, p.433-439, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127708]
• 4: Hsiao-Ping Tseng , Carl M. Sechen, Detailed routing algorithms for vlsi circuits, 1997
• 5: Lyle R. Smith, eta/, "~ New Area Router, The LRS Algorithm" Proceedings of IEEE International Conference on Circuits and Computers, pp. 256-259, 1982.
• 6: M. Burstein and R. Pelavin, "Hierarchical Wire Routing" IEEE Transactions on Computer-Aided Design, Vol. CAD- 2, No. 4, pp. 223-233, October 1983.
• 7: Hyunchul Shin and Alberto Sangiovanni-VincenteUi, "MIGHTY: A 'Rip-up and Reroute" Detailed Router:' Pro-. ceedings of IEEE International Conference on Computer- Aided Design (ICCAD), pp. 2-5, 1986.
• 8: J.M. Jou, et al, "'A New Three-Layer Detailed Router for VLSI Layout," Proceedings of IEEE InL Conference on Computer-Aided Design flCCAD), pp. 382-385, 1987.
• 9: C.S. Ying, et al, "'DRAFT: An Efficient Area Router Based on Global Analysis,' Proc. of IEEE int. Conference on Computer-Aided Design flCCAD), pp. 386-389, 1987.
• 10: A. Margarino, A. Romano, A. De Gloria, F. Curatelli and P. Antognetti, "'A Tile-Expansion Router" IEEE Transactions on Computer-Aided Design, Vol. CAD-6, No. 4, pp. 507- 517, July 1987.
• 11: Michael H. Arnold , Walter S. Scott, An interactive maze router with hints, Proceedings of the 25th ACM/IEEE conference on Design automation, p.672-676, June 12-15, 1988, Atlantic City, New Jersey, United States
• 12: S. H. Gerez and O. E. Herrmann, "CRACKER: A General Area Router Bases on Stepwise Reshaping" Proceedings of IEEE International Conference on Computer-Aided Design (ICCAD), pp. 44-47, 1989.
• 13: K. Mikami and K. Tabuchi, "A Computer Program for Optimal Routing of Printed Circuit Connectors," IFIPS Proceedings, Vol. H47, pp. 1475-1478, 1968.
• 14: David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
• 15: N. Katoh, et al, "Multi-layer Gddless Routing Method Based on Line-Expansion Algorithm:' VLSI Logic Synthesis and Design, pp. 279-285, 1990.
• 16: Chia-Chun Tsai, Sao-Jie Chen and Wu-Shiung Feng, "An H- V Alternating Router;' IEEE Transactions on Computer- Aided Design, Vol. 11, No. 8, pp. 976-991, August 1992.
• 17: Robi Dutta, et al, "Multi-layer Area Routing Algorithm as an Optimization Problem,' Proceedings of IEEE Custom Integrated Circuits Conference, pp. 27.4.1-27.4.4, 1990.
• 18: J. M. Cohn, et al, "KOAN/ANAGRAM II: New Tools for Device-Level Analog Placement and Routing" IEEE Journal of Solid-State Circuits, Vol. 26, No.3, pp. 330-42. March 1991.
• 19: Enrico Malavasi and Alberto Sangiovanni-Vincentelli, 'Tkrea Routing for Analog Layout," IEEE Transactions on Computer-Aided Design, Vol. 12, No. 8, August 1993.
• 20: Mohankumar Guruswamy , D. F. Wong, A general multi-layer area router, Proceedings of the 28th conference on ACM/IEEE design automation, p.335-340, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127690]
• 21: N. K. Sehgal, et al, "A Gridless Multi-layer Area Router," Proceedings of Fourth Great Lakes Symposium on VLSI. Design Automation of High Performance VLSI Systems, pp. 158-161, 1994.
• 22: Jeremy Dion and Louis M. Monier, "Contour: A Tile-based Gridless Router" Westem Research Laboratory Research Report 95/3, Palo Alto, California.
• 23: P.S. Tzeng and C. H. Sequin, "Codar: A Congested-Directed General Area Router" Proceedings of IEEE International Conference on Computer-Aided Design OCCAD), pp. 30-33, 1988.
• 24: R. Eric Lunow, A channelless, multilayer router, Proceedings of the 25th ACM/IEEE conference on Design automation, p.667-671, June 12-15, 1988, Atlantic City, New Jersey, United States
• 25: Y. L. Lin, et al, "Hybrid Routing:' IEEE Transactions on Computer-Aided Design, Vol.9, No.2, pp. 151-157, February 1990.
• 26: Kenneth M. McDonald and Joseph G. Peters, "Smallest Paths in Simple Rectilinear Polygons," IEEE Transactions on Computer-Aided Design, Vol. 11, No. 7, pp. 976-991, July 1992.
• 27: Charles J. Poirier, "EXCELLERATOR: Automatic Leaf Cell Layout Agent," Proceedings of IEEE Int. Conference on Computer-Aided Design (ICCAD), pp. 176-179, 1987.
• 28: John K. Ousterhout, "Comer Stitching: A Data-Structuring Technique for VLSI Layout Tools?' IEEE Transactions on Computer-Aided Design, Vol. CAD-3, NO. 1, pp. 87-100, January 1984.
• 29: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 30: W.-M. Dai , M. Sato , E. S. Kuh, A dynamic and efficient representation of building-block layout, Proceedings of the 24th ACM/IEEE conference on Design automation, p.376-384, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37945]
• 31: Wen-Chung Kao, et al, "Cross Point Assignment with Global Rerouting for General-Architecture Designs" IEEE Transactions on Computer-Aided Design, Vol 14, No 3, Mar. 1995.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Performance