Efficient timing-driven incremental routing for VLSI circuits using DFS and localized slack-satisfaction computations

ABSTRACT

In current very deep submicron (VDSM) circuits, incremental routing is crucial to incorporating engineering change orders (ECOs) late in the design cycle. In this paper, we address the important incremental routing objective of satisfying timing constraints in high-speed designs while minimizing wirelength, vias and routing layers. We develop an effective timing-driven (TD) incremental routing algorithm TIDE for ASIC circuits that addresses the dual goals of time-efficiency, and slack satisfaction coupled with effective optimizations. There are three main novelties in our approach: (i) a technique for locally determining slack satisfaction of the entire routing tree when either a new pin is added to the tree or an interconnect in it is re-routed---this technique is used in both the global and detailed routing phases; (ii) an interval-intersection and tree-truncation algorithm, used in global routing, for quickly determining a near-minimum-length slack-satisfying interconnection of a pin to a partial routing tree; (iii) a depth-first-search process, used in detailed routing, that allows new nets to bump and re-route existing nets in a controlled manner in order to obtain better optimized designs. Experimental results show that within the constraint of routing all nets in only two metal layers, TIDE succeeds in routing more than 94% of ECO-generated nets, and also that its failure rate is 7 and 6.7 times less than that of the TD versions of previous incremental routers Standard (Std) and Ripup&Reroute (R&R), respectively. It is also able to route nets with very little (3.4%) slack violations, while the other two methods have appreciable slack violations (16-19%). TIDE is about 2 times slower than the simple TD-Std method, but more than 3 times faster than TD-R&R.

REFERENCES

• 1: J. M. Emmert and D. Bhatia. "Incremental Routing in FPGAs". Proc. IEEE Int. ASIC Conference and Exhibit,' 98.
• 2: Jason Cong , Majid Sarrafzadeh, Incremental physical design, Proceedings of the 2000 international symposium on Physical design, p.84-92, May 2000, San Diego, California, United States [doi>10.1145/332357.332379]
• 3: Shantanu Dutt , Vinay Verma , Hasan Arslan, A search-based bump-and-refit approach to incremental routing for ECO applications in FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.664-693, October 2002 [doi>10.1145/605440.605449]
• 4: Shantanu Dutt , Vimalvel Shanmugavel , Steve Trimberger, Efficient incremental rerouting for fault reconfiguration in field programmable gate arrays, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.173-177, November 07-11, 1999, San Jose, California, United States
• 5: Hasan Arslan , Shantanu Dutt, A Depth-First-Search Controlled Gridless Incremental Routing Algorithm for VLSI Circuits, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.86-92, October 11-13, 2004
• 6: Huibo Hou , Sachin S. Sapatnekar, Routing tree topology construction to meet interconnect timing constraints, Proceedings of the 1998 international symposium on Physical design, p.205-210, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274565]
• 7: K. D. Boese and A. B. Kahng and B. A. McCoy and G. Robins, "Fidelity and Near-Optimality of Elmore-Based Routing Constructions", ICCD, pp. 81--84, 1993.
• 8: K. D. Boese and A. B. Kahng and B. A. McCoy and G. Robins. "Near-Optimal Critical Sink Routing Tree Constructions", IEEE-TCAD, pp. 1417--1436, 1995.
• 9: Dongsheng Wang , Ernest S. Kuh, A New Timing-Driven Multilayer MCM/IC Routing Algorithm, Proceedings of the 1997 Conference on IEEE Multi-Chip Module Conference, p.89, February 04-05, 1997
• 10: Hua Xiang , Kai-Yuan Chao , Martin D. F. Wong, An ECO algorithm for eliminating crosstalk violations, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981075]
• 11: J. Cong, "Challenges and Opportunities for Design Innovations in Nanometer Technologies," Frontiers in Semiconductor Research: A Collection of SRC Working Papers, SRC, 1997.