NDLI: Provably good global buffering by multiterminal multicommodity flow approximation

Content Provider	IEEE Xplore Digital Library
Author	Dragan, F.F. Kahng, A.B. Mandoiu, I. Muddu, S. Zelikovsky, A.
Copyright Year	2001
Description	Author affiliation: Dept. of Math. & Comput. Sci., Kent State Univ., OH, USA (Dragan, F.F.)
Abstract	To implement high-performance global interconnect without impacting the placement and performance of existing blocks, the use of buffer blocks is becoming increasingly popular in structured-custom and block-based ASIC methodologies. Recent works by Cong, Kong and Pan (1999) and Tang and Wong (2000) give algorithms to solve the buffer block planning problem. In this paper, we address the problem of how to perform buffering of global multiterminal nets given an existing buffer block plan. We give a provably good algorithm based on a recent approach of Garg and Konemann (1998) and Fleischer (1999) [see also Albrecht (2000) and Dragan et al. (2000)]. Our method routes connections using available buffer blocks, such that required upper and lower bounds on buffer intervals-as well as wirelength upper bounds per connection-are satisfied. In addition, our algorithm allows more than one buffer to be inserted into any given connection and observes buffer parity constraints. Most importantly, and unlike previous works on the problem, we take into account multiterminal nets. Our algorithm outperforms existing algorithms for the problem, which are based on 2-pin decompositions of the nets. The algorithm has been validated on top-level layouts extracted from a recent high-end microprocessor design.
Sponsorship	IEEE Circuits & Syst. Soc.
Starting Page	120
Ending Page	125
File Size	725360
Page Count	6
File Format	PDF
ISBN	0780366336
DOI	10.1109/ASPDAC.2001.913291
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-02-02
Publisher Place	Japan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Repeaters Inverters Routing Computer science Application specific integrated circuits Upper bound Algorithm design and analysis Mathematics Educational institutions High performance computing
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

Provably good global buffering by generalized multiterminal multicommodity flow approximation

Provably Good Global Buffering by Generalized Multiterminal Multicommodity Flow Approximation

Provably good global buffering by multiterminal multicommodity flow approximation (2001)

Provably good global buffering by multiterminal multicommodity flow approximation (2001)

Provably good global buffering by multiterminal multicommodity flow approximation (2004).

Provably Good Global Buffering by Generalized Multiterminal Multicommodity Flow Approximation (2002)

Provably good global buffering by multiterminal multicommodity flow approximation (2001).

Provably good global buffering using an available buffer block plan

Provably good global buffering by multi-terminal multicommodity flow approximation

Provably good global buffering by multiterminal multicommodity flow approximation

Similar Documents

Provably good global buffering by generalized multiterminal multicommodity flow approximation

Provably Good Global Buffering by Generalized Multiterminal Multicommodity Flow Approximation

Provably good global buffering by multiterminal multicommodity flow approximation (2001)

Provably good global buffering by multiterminal multicommodity flow approximation (2001)

Provably good global buffering by multiterminal multicommodity flow approximation (2004).

Provably Good Global Buffering by Generalized Multiterminal Multicommodity Flow Approximation (2002)

Provably good global buffering by multiterminal multicommodity flow approximation (2001).

Provably good global buffering using an available buffer block plan

Provably good global buffering by multi-terminal multicommodity flow approximation

Provably good global buffering by multiterminal multicommodity flow approximation