Layout-aware gate duplication and buffer insertion

ABSTRACT

An approach for layout-aware interconnect optimization is presented. It is based on the combination of three sub-problems into the same framework: gate duplication, buffer insertion and placement. Different techniques to control the combinatorial explosion are proposed.

The experimental results show tangible benefits in delay that endorse the suitability of integrating the three sub-problems in the same framework. The results also corroborate the increasing relevance of interconnect optimization in future semiconductor technologies.

REFERENCES

• 1: Kanwar Jit Singh , Alberto Sangiovanni-Vincentelli, A heuristic algorithm for the fanout problem, Proceedings of the 27th ACM/IEEE conference on Design automation, p.357-360, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123303]
• 2: Rajeev Murgai, Efficient global fanout optimization algorithms, Proceedings of the 2001 conference on Asia South Pacific design automation, p.571-576, January 2001, Yokohama, Japan [doi>10.1145/370155.370536]
• 3: C.-H. Chen and C.-Y. Tsui, "Timing optimization of logic network using gate duplication," in Proc. of Asia and South Pacific Design Automation Conference, Jan. 1999, pp. 233--236.
• 4: Ankur Srivastava , Ryan Kastner , Chunhong Chen , Majid Sarrafzadeh, Timing driven gate duplication, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.1, p.42-51, January 2004 [doi>10.1109/TVLSL2003.820527]
• 5: Qinghua Liu , Malgorzata Marek-Sadowska, Wire length prediction-based technology mapping and fanout optimization, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055167]
• 6: L. van Ginneken, "Buffer placement in distributed re-tree networks for minimal elmore delay," in Proc. International Symposium on Circuits and Systems, 1990, pp. 865--868.
• 7: Charles J. Alpert , Miloš Hrkić , Stephen T. Quay, A fast algorithm for identifying good buffer insertion candidate locations, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981076]
• 8: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Optimal wire sizing and buffer insertion for low power and a generalized delay model, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.138-143, November 05-09, 1995, San Jose, California, United States
• 9: W. Shi and Z. Li, "A fast algorithm for optimal buffer insertion." IEEE Transactions on Computer-Aided Design, vol. 24, no. 6, pp. 879--891, 2005.
• 10: Jason Cong , Kwok-Shing Leung , Dian Zhou, Performance-driven interconnect design based on distributed RC delay model, Proceedings of the 30th international conference on Design automation, p.606-611, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165065]
• 11: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin , Ching-Yen Ho, New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing, Proceedings of the 33rd annual conference on Design automation, p.395-400, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240594]
• 12: Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, California, United States
• 13: Amir H. Salek , Jinan Lou , Massoud Pedram, A simultaneous routing tree construction and fanout optimization algorithm, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.625-630, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289098]
• 14: Hervé J. Touati , Cho W. Moon , Robert K. Brayton , Albert Wang, Performance-oriented technology mapping, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.79-97, March 1990, Boston, Massachusetts, United States
• 15: Xiaoping Tang , Ruiqi Tian , Hua Xiang , D. F. Wong, A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 16: Gang Chen , Jason Cong, Simultaneous timing-driven placement and duplication, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046200]
• 17: Hosung (Leo) Kim , John Lillis , Miloš Hrkić , Miloš Hrkić, Techniques for improved placement-coupled logic replication, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA [doi>10.1145/1127908.1127959]
• 18: J. B. MacQueen, "Some methods for classification and analysis of multivariate observations," in Proc. of 5th Berkeley Symp. on Mathematical Statistics and Probability, vol. 1. Berkeley: University of California Press, 1967, pp. 281--297.
• 19: W. C. Elmore, "The transient response of damped linear networks," Journal of Applied Physics, vol. 19, pp. 55--63, Jan. 1948.
• 20: M. Borah, R. M. Owens, and M. Irwin, "An edge-based heuristic for steiner routing," IEEE Transactions on Computer-Aided Design, vol. 13, no. 12, pp. 1563--1568, Dec. 1994.
• 21: R. Kastner, A. Srivastava, and M. Sarrafzadeh, "On the complexity of gate duplication," IEEE Transactions on Computer-Aided Design, vol. 20, no. 9, pp. 1170--1176, Sept. 2001.
• 22: Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, An Efficient k-Means Clustering Algorithm: Analysis and Implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.881-892, July 2002 [doi>10.1109/TPAMI.2002.1017616]
• 23: H. B. Bakoglu, Circuits, Interconnections, and Packaging forl VLSI. Addison-Wesley, 1990.
• 24: Alliance library, www.vlsitechnology.org/html/vx_description.html
• 25: Interconnection calculator, www.eas.asu.edu/~ptm/cgi-bin/interconnect/local.cgi.
• 26: P. Bai, C. Auth, and et al., A 65nm Logic Technology Featuring 35nm Gate Lengths, Enhanced Channel Strain, 8 Cu Interconnect Layers, Low-k ILD and 0.57μm² SRAM Cell, Intel Developer Forum, Aug. 2005.
• 27: N. Viswanathan and C.-N. Chu, "Fastplace: efficient analytical placement using cell shifting, iterative local refinement, and a hybrid net model," IEEE Transactions on Computer-Aided Design, vol. 24, no. 5, pp. 722--733, May 2005.
• 28: R. Kastner and M. Sarrafzadeh, "Labyrinth: A global router and routing development tool," www.ece.ucsb.edu/~kastner/labyrinth.