File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1514932.1514969
- Scopus: eid_2-s2.0-70349131994
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: A faster approximation scheme for timing driven minimum cost layer assignment
Title | A faster approximation scheme for timing driven minimum cost layer assignment |
---|---|
Authors | |
Keywords | Dynamic programming Fully polynomial time approximation scheme Layer assignment NP-Complete Oracle |
Issue Date | 2009 |
Citation | Proceedings of the International Symposium on Physical Design, 2009, p. 167-174 How to Cite? |
Abstract | As VLSI technology moves to the 65nm node and beyond, interconnect delay greatly limits the circuit performance. As a critical component in interconnect synthesis, layer assignment manifests enormous potential in drastically reducing wire delay. This is due the fact that wires on thick metals are much less resistive than those on thin metals. Nevertheless, it is not desired to assign all wires to thick metals and the right strategy is to only use minimal thick-metal routing resources for meeting the timing constraints. This timing driven minimum cost layer assignment problem is NP-Complete, and a fast algorithm with provable approximation bound is highly desired. In this paper, a new fully polynomial time approximation scheme is proposed. It is based on a linear-time dynamic programming algorithm for bounded-cost layer assignment and efficient oracle queries. The proposed algorithm can approximate the optimal layer assignment solution in O(mn2/ε) time within a factor of 1 + ε for any ε > 0, where n is the tree size and m is the number of routing layers. This significantly improves the previous work. The new algorithm is also highly practical. Our experiments on industrial netlists demonstrate that the new algorithm runs up to 6.5 × faster than the optimal dynamic programming with few percent additional wire as guaranteed theoretically. This gives another > 2× speedup over the previous work. Copyright 2009 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/336037 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hu, Shiyan | - |
dc.contributor.author | Li, Zhuo | - |
dc.contributor.author | Alpert, Charles J. | - |
dc.date.accessioned | 2024-01-15T08:22:14Z | - |
dc.date.available | 2024-01-15T08:22:14Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | Proceedings of the International Symposium on Physical Design, 2009, p. 167-174 | - |
dc.identifier.uri | http://hdl.handle.net/10722/336037 | - |
dc.description.abstract | As VLSI technology moves to the 65nm node and beyond, interconnect delay greatly limits the circuit performance. As a critical component in interconnect synthesis, layer assignment manifests enormous potential in drastically reducing wire delay. This is due the fact that wires on thick metals are much less resistive than those on thin metals. Nevertheless, it is not desired to assign all wires to thick metals and the right strategy is to only use minimal thick-metal routing resources for meeting the timing constraints. This timing driven minimum cost layer assignment problem is NP-Complete, and a fast algorithm with provable approximation bound is highly desired. In this paper, a new fully polynomial time approximation scheme is proposed. It is based on a linear-time dynamic programming algorithm for bounded-cost layer assignment and efficient oracle queries. The proposed algorithm can approximate the optimal layer assignment solution in O(mn2/ε) time within a factor of 1 + ε for any ε > 0, where n is the tree size and m is the number of routing layers. This significantly improves the previous work. The new algorithm is also highly practical. Our experiments on industrial netlists demonstrate that the new algorithm runs up to 6.5 × faster than the optimal dynamic programming with few percent additional wire as guaranteed theoretically. This gives another > 2× speedup over the previous work. Copyright 2009 ACM. | - |
dc.language | eng | - |
dc.relation.ispartof | Proceedings of the International Symposium on Physical Design | - |
dc.subject | Dynamic programming | - |
dc.subject | Fully polynomial time approximation scheme | - |
dc.subject | Layer assignment | - |
dc.subject | NP-Complete | - |
dc.subject | Oracle | - |
dc.title | A faster approximation scheme for timing driven minimum cost layer assignment | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/1514932.1514969 | - |
dc.identifier.scopus | eid_2-s2.0-70349131994 | - |
dc.identifier.spage | 167 | - |
dc.identifier.epage | 174 | - |