An efficient tile-based ECO router with routing graph reduction and enhanced global routing flow

ABSTRACT

Engineering Change Order (ECO) routing is frequently requested in the later design stage for the purpose of delay and noise optimization. ECO routing is complicated by huge existing obstacles and the requests for various design rules. Tile-based routers have work with fewer nodes of the routing graph than grid and connection-based routers; however, the number of nodes of the tile-based routing graph has grown to over a thousand millions for SOC designs. This work depicts a new ECO routing design flow with routing graph reduction and enhanced global routing flow. Routing graph reduction reduces the complexity of nodes by removing redundant tiles and aligning neighboring tiles to merge adjacent block tiles. Routing graph reduction reduces tile fragmentation such that the ECO router can run twice as fast without sacrificing routing quality. Enhanced global routing flow incorporates ECO global routing with extended routing and GCell restructuring to prevent routing failure in a routable routing. The ECO router with new design flow can perform up to 20 times faster than the original tile-based router, at the cost of only a very small decline in routing quality.

REFERENCES

• 1: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 2: T. Ohtsuki, "Gridless routers" New wire routing algorithms based on computational geometry, in Proc. Int. Conf. Circuits and Systems, pp. 802--809, May 1985.
• 3: K. Clarkson , S. Kapoor , P. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)²) time, Proceedings of the third annual symposium on Computational geometry, p.251-257, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41985]
• 4: Ying-Fung Wu , Peter Widmayer , Martine D. F. Schlag , C. K. Wong, Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles, IEEE Transactions on Computers, v.36 n.3, p.321-331, March 1987 [doi>10.1109/TC.1987.1676904]
• 5: S.Zheng, J.S. Lim, and S. Iyengar, "Finding obstacle-avoiding shortest paths using implicit connection graphs,"IEEE Trans. Computer-Aided Design, vol. 15, no. 1, pp. 103--110, Jan. 1996.
• 6: Jason Cong , Jie Fang , Kei-Yong Khoo, An implicit connection graph maze routing algorithm for ECO routing, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.163-167, November 07-11, 1999, San Jose, California, United States
• 7: Jason Cong , Jie Fang , Kei-Yong Khoo, DUNE: a multi-layer gridless routing system with wire planning, Proceedings of the 2000 international symposium on Physical design, p.12-18, May 2000, San Diego, California, United States [doi>10.1145/332357.332367]
• 8: J. Cong, J. Fang, and K. Khoo,"DUNE - A multilayer gridless routing system,"IEEE Trans. Computer-Aided Design, vol. 20, no. 5, pp. 633--647, May. 2001.
• 9: M. Sato, J. Sakanaka, and T. Ohtsuki, "A fast line-search method based on a tile plane," in IEEE Int. Symp. Circuits and Systems, pp. 588--591, May 1987.
• 10: A. Margarino, A. Romano, A. De Gloria, F. Curatelli, and P. Antognetti, "A tile-expansion router,"IEEE Trans. Computer-Aided Design, vol. CAD-6, pp. 507--517, July 1987.
• 11: 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
• 12: Le-Chin Eugene Liu , Hsiao-Ping Tseng , Carl Sechen, Chip-level area routing, Proceedings of the 1998 international symposium on Physical design, p.197-204, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274564]
• 13: C. Tsai, S. Chen, and W. Feng, "An H-V Alternating Router," IEEE Trans. Computer-Aided Design, vol. 11, pp. 976--991, Aug. 1992.
• 14: J. Dion and L. M. Monier, "Contour: A tile-based gridless router," Western Research Laboratory, Palo Alto, CA, Research Report 95/3.
• 15: Zhaoyun Xing and Russell Kaog, "Shortest Path Search Using Tiles and Piecewise Linear Cost Propagation," IEEE Trans. Computer-Aided Design, vol. 21, no. 2, pp. 145--158, Feb. 2002.
• 16: J. K. Ousterhout, "Corner Stitching: Adata-structuring technique for VLSI layout tools," IEEE Trans. Computer-Aided Design, vol. CAD-3, pp. 87--100, Jan. 1984.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
ECO routing, connection-based router, global routing, gridless router, tile-based router