DocumentCode :
3486396
Title :
A polynomial time approximation scheme for timing constrained minimum cost layer assignment
Author :
Hu, Shiyan ; Li, Zhuo ; Alpert, Charles J.
Author_Institution :
Dept. of Electr. & Comput. Eng., Michigan Technol. Univ., Houghton, MI
fYear :
2008
fDate :
10-13 Nov. 2008
Firstpage :
112
Lastpage :
115
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 (65 nm and 45 nm) 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 + isin in O(mlog logm ldr n3/isin2) time for 0 < isin < 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 test cases demonstrate that the new algorithm can run 2times faster than the optimal dynamic programming algorithm with only 2% additional wire.
Keywords :
VLSI; delays; integrated circuit interconnections; network routing; polynomial approximation; VLSI technology; interconnect delay; nanoscale regime; polynomial time approximation scheme; routing layers; timing-driven minimum cost layer assignment problem; upper metal layers; wire sizing problem; Circuit optimization; Costs; Integrated circuit interconnections; NP-complete problem; Polynomials; Propagation delay; Routing; Timing; Very large scale integration; Wires;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer-Aided Design, 2008. ICCAD 2008. IEEE/ACM International Conference on
Conference_Location :
San Jose, CA
ISSN :
1092-3152
Print_ISBN :
978-1-4244-2819-9
Electronic_ISBN :
1092-3152
Type :
conf
DOI :
10.1109/ICCAD.2008.4681560
Filename :
4681560
Link To Document :
بازگشت