Mohamed KHALIL-HANI, Chessda UTTRAPHAN, Nasir SHAIKH-HUSIN

An optimized buffer insertion algorithm with delay-power constraints for VLSIlayouts

We propose a grid-graph algorithm for interconnect routing and buffer insertion in nanometer VLSI layoutdesigns. The algorithm is designed to handle multiconstraint optimizations, namely timing performance and powerdissipation. The proposed algorithm is called HRTB-LA, which stands for hybrid routing tree and buffer insertion withlook-ahead. In recent VLSI designs, interconnect delay has become a dominant factor compared to gate delay. Thewell-known technique to minimize the interconnect delay is by inserting buffers along the interconnect wires. However,the buffer itself consumes power and it has been shown that power dissipation overhead due to buffer insertions issigni cantly high. Many methodologies to optimize timing performance with power constraint have been proposed,and no algorithm is based on dynamic programing technique using a grid graph. In addition, most of the algorithmsfor buffer insertion use a postrouting buffer insertion approach. In the presence of buffer obstacles, these postroutingalgorithms may produce poor solutions. On the other hand, the simultaneous routing and buffer insertion algorithmoffers a better solution, but it was proven to be NP complete. Hence, our main contribution is an efficient algorithmusing a hybrid approach for multiconstraint optimization for multisink nets. The algorithm uses dynamic programmingto compute incrementally the interconnect delay and power dissipation of the inserted buffers while an effective runtimeis achieved with the aid of novel look-ahead and graph pruning schemes. Experimental results prove that HRTB-LA isable to handle multiconstraint optimizations and produces a solution up to 30% better compared to a postrouting bufferinsertion algorithm in comparable runtime.

PDF

___

[1]Ekekwe N. Power dissipation and interconnect noise challenges in nanometer CMOS technologies. IEEE Potentials2010; 29: 26-31.
[2]van Ginneken LPPP. Buffer placement in distributed RC-tree networks for minimal Elmore delay. In: IEEEInternational Symposium on Circuit and System; 1{3 May 1990; New Orleans, LA, USA: IEEE. pp. 865-868.
[3]Rubinstein J, Pen eld P, Horowitz MA. Signal delay in RC tree networks. IEEE T Comput Aid D 1983; 2: 202-211.
[4]Dasgupta S, Papadimitriou CH, Vazirani UV. Algorithms. New York, NY, USA: McGraw-Hill, 2006.
[5]Alpert CJ, Mehta DP, Sapatnekar SS. Handbook of algorithms for physical design automation. Boca Raton, FL,USA: Auerbach Publications, 2009.
[6]Nalamalpu A, Burleson W. A practical approach to DSM repeater insertion- satisfying delay constraints whileminimizing area and power. In: IEEE ASIC/SOC Conference; 12{15 September 2001; Arlington, VA, USA: IEEE.pp. 152-156.
[7]Saxena P, Menezes N, Cocchini P, Kirkpatrick DA. Repeater scaling and its impact on CAD. IEEE T Comput AidD 2004; 23: 451-463.
[8]Li R, Zhou D, Liu J, Zeng X. Power-optimal simultaneous buffer insertion/sizing and wire sizing for two-pin nets.IEEE T Comput Aid D 2005; 24: 1915-1924.
[9]Narasimhan A, Sridhar R. Variability aware low-power delay optimal buffer insertion for global interconnects. IEEET Circuits-I 2010; 57: 3055-3063.
[10]Shi W, Li Z. AnO(nlogn) time algorithm for optimal buffer insertion. In: IEEE Design Automation Conference;2{6 June 2003: IEEE. pp. 580-585.
[11]Shi W, Li Z. A fast algorithm for optimal buffer insertion. IEEE T Comput Aid D 2005; 24: 879-891.
[12]Li Z, Shi W. AnO(bn2) time algorithm for optimal buffer insertion withbbuffer types. IEEE T Comput Aid D2006; 25: 484-489.
[13]Li Z, Zhou Y, Shi W. AnO(mn) time algorithm for optimal buffer insertion of nets withmsinks. IEEE T ComputAid D 2012; 31: 437-441.
[14]Zhou H, Wong DF, Liu I-M, Aziz A. Simultaneous routing and buffer insertion with restrictions on buffer locations.IEEE T Comput Aid D 2000; 19: 819-824.
[15]Cong J, Yuan X. Routing tree construction under xed buffer locations. In: Design Automation Conference; 5{9June 2000; Los Angeles, CA, USA: IEEE. pp. 379-384.
[16]Hu S, Li S, Alpert CJ. A fully polynomial time approximation scheme for timing driven minimum cost bufferinsertion. In: Design Automation Conference; 26{31 July 2009; San Francisco, CA, USA: IEEE. pp. 424-429.
[17]Khalil-Hani M, Shaikh-Husin N. An optimization algorithm based on grid-graphs for minimizing interconnect delayin VLSI layout design. Malayas J Comput Sci 2009; 22: 19-33.
[18]Hu J, Alpert CJ, Quay ST, Gandham G. Buffer insertion with adaptive blockage avoidance. IEEE T Comput AidD 2003; 22: 492-498.
[19]Uttraphan C, Shaikh-Husin N, Khalil-Hani M. An optimization algorithm for simultaneous routing and bufferinsertion with delay-power constraints in VLSI Layout Design. In: International Symposium on Quality ElectronicDesign; 3{5 March 2014; Santa Clara, CA, USA: IEEE. pp. 357-364.
[20]Lai M, Wong DF. Maze routing with buffer insertion and wiresizing. IEEE T Comput Aid D 2002; 21: 1205-1209.
[21]Lee CY. An algorithm for path connections and its applications. IEEE T Comput 1961; 10: 346-365.
[22]Md-Yusof Z, Khalil-Hani M, Marsono MN, Shaikh-Husin N. Optimizing multi-constraint VLSI interconnect routing.In: International Symposium on Integrated Circuits; 14{16 December 2009; Singapore: IEEE. pp 655-658.
[23]van Mieghem P, Kuipers F. Concepts of exact QoS routing algorithms. IEEE Acm T Network 2004; 12: 851-864.
[24]Alpert CJ, Karandikar SK, Li Z, Joon Nam G, Quay ST, Sze CN, Villarrubia PG, Yildiz MC. Techniques for fastphysical synthesis. Proceeding of the IEEE 2007; 95: 573-599.
[25]Gupta R, Tutuianu B, Pileggi LT. The Elmore delay as a bound for RC trees with generalized input signals. IEEET Comput Aid D 1997; 16: 95-104.
[26]Uttraphan C, Shaikh-Husin N. Hybrid Routing Tree with Buffer Insertion under Obstacle Constraints. In: StudentConference on Research and Development; 16{17 December 2013; Kuala Lumpur, Malaysia: IEEE. pp. 411-416.
[27]Cormen TH, Leiserson CE, Rivest RL. Introduction to Algorithms. 3rd ed. Boston, MA, USA: McGraw-Hill, 2009.