A polynomial time approximation scheme for timing constrained minimum cost layer assignment

ABSTRACT

As VLSI technology enters the nanoscale regime, interconnect delay becomes the bottleneck of circuit performance. Compared to gate delays, wires are becoming increasingly resistive which makes it more difficult to propagate signals across the chip. However, more advanced technologies (65nm and 45nm) provide relief as the number of metal layers continues to increase. The wires on the upper metal layers are much less resistive and can be used to drive further and faster than on thin metals. This provides an entirely new dimension to the traditional wire sizing problem, namely, layer assignment for efficient timing closure. Assigning all wires to thick metals improves timing, however, routability of the design may be hurt. The challenge is to assign minimal amount of wires to thick metals to meet timing constraints.

In this paper, the minimum cost layer assignment problem is proven to be NP-Complete. As a theoretical solution for NP-complete problems, a polynomial time approximation scheme is proposed. The new algorithm can approximate the optimal layer assignment solution by a factor of 1 + ε in O(m log log m · n³/ε²) time for 0 < ε < 1, where n is the number of nodes in the tree and m is the number of routing layers. This work presents the first theoretical advance for the timing-driven minimum cost layer assignment problem. In addition to its theoretical guarantee, the new algorithm is highly practical. Our experiments on 500 testcases demonstrate that the new algorithm can run 2x faster than the optimal dynamic programming algorithm with only 2% additional wire.

REFERENCES

• 1: Zhuo Li , Charles J. Alpert , Shiyan Hu , Tuhin Muhmud , Stephen T. Quay , Paul G. Villarrubia, Fast interconnect synthesis with layer assignment, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA [doi>10.1145/1353629.1353648]
• 2: J. Fishburn and C. Schevon, "Shaping a distributed-rc line to minimize elmore delay," IEEE Trans. on Circuits and Systems-I, vol. 42, no. 12, pp. 1020--1022, 1995.
• 3: C.-P. Chen, C. Chu, and D. Wong, "Fast and exact simultaneous gate and wire sizing by lagrangian relaxation," IEEE Transactions on Computer-Aided Design, vol. 18, no. 7, pp. 1014--1025, 1999.
• 4: 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]
• 5: J. Cong and K.-S. Leung, "Optimal wire sizing under elmore delay model," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 3, pp. 321--336, 1995.
• 6: C. Alpert, A. Devgan, J. P. Fishburn, and S. T. Quay, "Interconnect synthesis without wire tapering," IEEE Transactions on Computer-Aided Design, vol. 20, no. 1, pp. 90--104, 2001.
• 7: J. Lillis and C.-K. Cheng and T.-T.Y. Lin, "Optimal wire sizing and buffer insertion for low power and a generalized delay model," IEEE Journal of Solid State Circuits, vol. 31, no. 3, pp. 437--447, 1996.
• 8: C. Alpert, S. Karandikar, Z. Li, G.-J. Nam, S. Quay, H. Ren, C. Sze, P. Villarrubia, and M. Yildiz, "Techniques for fast physical synthesis," Proceedings of IEEE, vol. 95, no. 3, pp. 573--599, 2007.
• 9: Refael Hassin, Approximation schemes for the restricted shortest path problem, Mathematics of Operations Research, v.17 n.1, p.36-42, Feb. 1992 [doi>10.1287/moor.17.1.36]
• 10: M. Marek-Sadowska, "An unconstrained topological via minimization problem for two-layer routing," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 3, no. 3, pp. 184--190, 1984.
• 11: S. Hu, C. J. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi, and C. N. Sze, "Fast algorithms for slew constrained minimum cost buffering," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 26, no. 11, pp. 2009--2022, 2007.
• 12: Z. Li and W. Shi, "An O(bn²) time algorithm for optimal buffer insertion with b buffer types," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 3, pp. 484--489, 2006.
• 13: Weiping Shi , Zhuo Li , Charles J. Alpert, Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Guoliang Xue , Weiyi Zhang , Jian Tang , Krishnaiyan Thulasiraman, Polynomial time approximation algorithms for multi-constrained QoS routing, IEEE/ACM Transactions on Networking (TON), v.16 n.3, p.656-669, June 2008 [doi>10.1109/TNET.2007.900712]