NDLI: A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion

Content Provider	IEEE Xplore Digital Library
Author	Shiyan Hu Zhuo Li Alpert, C.J.
Copyright Year	2009
Description	Author affiliation: IBM Austin Research Laboratory, 11501 Burnet Road, Texas 78758, USA (Zhuo Li; Alpert, C.J.) \|\| Dept. of Electrical and Computer Engineering, Michigan Technological University, Houghton, 49931, USA (Shiyan Hu)
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(m^{2}n^{2}b/ε^{3}$ + $n^{3}b^{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.6× speedup. This clearly demonstrates the practical value of the new algorithm.
Starting Page	424
Ending Page	429
File Size	516985
Page Count	6
File Format	PDF
ISBN	9781605584973
ISSN	0738100X
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-07-26
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Association for Computing Machinery, Inc. (ACM)
Subject Keyword	Polynomials Timing Costs Integrated circuit interconnections Dynamic programming Very large scale integration Delay Circuit synthesis Algorithm design and analysis Libraries Dynamic Programming Buffer Insertion Fully Polynomial Time Approximation Scheme NP-complete Cost Minimization
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion

A Fully Polynomial-Time Approximation Scheme for Timing-Constrained Minimum Cost Layer Assignment

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

A faster approximation scheme for timing driven minimum cost layer assignment

A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion (2009).

Fast Min-Cost Buffer Insertion under Process Variations

Performance-Driven Routing Tree Construction with Buffer Insertion, Wire Sizing under RLC Delay Model

An Efficient Analytical Approach to Path-Based Buffer Insertion

Performance-driven interconnection allocation

A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion

Similar Documents

A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion

A Fully Polynomial-Time Approximation Scheme for Timing-Constrained Minimum Cost Layer Assignment

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

A faster approximation scheme for timing driven minimum cost layer assignment

A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion (2009).

Fast Min-Cost Buffer Insertion under Process Variations

Performance-Driven Routing Tree Construction with Buffer Insertion, Wire Sizing under RLC Delay Model

An Efficient Analytical Approach to Path-Based Buffer Insertion

Performance-driven interconnection allocation

A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion