File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1629911.1630026
- Scopus: eid_2-s2.0-70350712438
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion
Title | A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion |
---|---|
Authors | |
Keywords | Buffer insertion Cost minimization Dynamic programming Fully polynomial time approximation scheme NP-complete |
Issue Date | 2009 |
Citation | Proceedings - Design Automation Conference, 2009, p. 424-429 How to Cite? |
Abstract | As VLSI technology enters the nanoscale regime, interconnect delay has become the bottleneck of the circuit timing. As one of the most powerful techniques for interconnect optimization, buffer insertion is indispensable in the physical synthesis flow. Buffering is known to be NP-complete and existing works either explore dynamic programming to compute optimal solution in the worst-case exponential time or design efficient heuristics without performance guarantee. Even if buffer insertion is one of the most studied problems in physical design, whether there is an efficient algorithm with provably good performance still remains unknown. This work settles this open problem. In the paper, the first fully polynomial time approximation scheme for the timing driven minimum cost buffer insertion problem is designed. The new algorithm can approximate the optimal buffering solution within a factor of 1 + ε running in O(m2n2b/ε3 + n3b 2/ε) time for any 0 < ε < 1, where n is the number of candidate buffer locations, m is the number of sinks in the tree, and b is the number of buffers in the buffer library. In addition to its theoretical guarantee, our experiments on 1000 industrial nets demonstrate that compared to the commonly-used dynamic programming algorithm, the new algorithm well approximates the optimal solution, with only 0.57% additional buffers and 4.6x speedup. This clearly demonstrates the practical value of the new algorithm. Copyright 2009 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/336077 |
ISSN | 2020 SCImago Journal Rankings: 0.518 |
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:23:14Z | - |
dc.date.available | 2024-01-15T08:23:14Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | Proceedings - Design Automation Conference, 2009, p. 424-429 | - |
dc.identifier.issn | 0738-100X | - |
dc.identifier.uri | http://hdl.handle.net/10722/336077 | - |
dc.description.abstract | As VLSI technology enters the nanoscale regime, interconnect delay has become the bottleneck of the circuit timing. As one of the most powerful techniques for interconnect optimization, buffer insertion is indispensable in the physical synthesis flow. Buffering is known to be NP-complete and existing works either explore dynamic programming to compute optimal solution in the worst-case exponential time or design efficient heuristics without performance guarantee. Even if buffer insertion is one of the most studied problems in physical design, whether there is an efficient algorithm with provably good performance still remains unknown. This work settles this open problem. In the paper, the first fully polynomial time approximation scheme for the timing driven minimum cost buffer insertion problem is designed. The new algorithm can approximate the optimal buffering solution within a factor of 1 + ε running in O(m2n2b/ε3 + n3b 2/ε) time for any 0 < ε < 1, where n is the number of candidate buffer locations, m is the number of sinks in the tree, and b is the number of buffers in the buffer library. In addition to its theoretical guarantee, our experiments on 1000 industrial nets demonstrate that compared to the commonly-used dynamic programming algorithm, the new algorithm well approximates the optimal solution, with only 0.57% additional buffers and 4.6x speedup. This clearly demonstrates the practical value of the new algorithm. Copyright 2009 ACM. | - |
dc.language | eng | - |
dc.relation.ispartof | Proceedings - Design Automation Conference | - |
dc.subject | Buffer insertion | - |
dc.subject | Cost minimization | - |
dc.subject | Dynamic programming | - |
dc.subject | Fully polynomial time approximation scheme | - |
dc.subject | NP-complete | - |
dc.title | A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/1629911.1630026 | - |
dc.identifier.scopus | eid_2-s2.0-70350712438 | - |
dc.identifier.spage | 424 | - |
dc.identifier.epage | 429 | - |