NDLI: Maze routing with buffer insertion under transition time constraints

Content Provider	IEEE Xplore Digital Library
Author	Li-Da Huang Minghorng Lai Wong, D.F. Youxin Gao
Copyright Year	2002
Description	Author affiliation: Dept. of Comput. Sci., Texas Univ., Austin, TX, USA (Li-Da Huang)
Abstract	In this paper we address the problem of simultaneous routing and buffer insertion. Simultaneous maze routing and buffer insertion under the Elmore delay model have been reported in the literature previously. Such algorithms can take into account both routing obstacles and restrictions on buffer locations. It is well known that Elmore delay is only a first-order approximation of signal delay and hence could be very inaccurate. Moreover, we cannot impose constraints on the transition times of the output signal waveform at the sink or at the buffers on the route. In this paper we extend previously reported algorithm so that accurate delay models (e.g., transmission line model, delay look-up table from SPICE, etc.) can be used We show that the problem of finding a minimum-delay buffered routing path can be formulated as a shortest path problem in a specially constructed weighted graph. By including only the vertices with qualifying transition times in the graph, we guarantee that all transition time constraints are satisfied. Our algorithm can be easily extended to handle buffer sizing and wire sizing. It can be applied iteratively to improve any given routing tree solution. Experimental results show that our algorithm performs well.
Sponsorship	EDAA
Starting Page	702
Ending Page	707
File Size	372768
Page Count	6
File Format	PDF
ISBN	0769514715
ISSN	15301591
DOI	10.1109/DATE.2002.998376
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-03-04
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Iterative algorithms Transmission lines Delay lines Table lookup SPICE Shortest path problem Time factors Wire Tree graphs
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

Maze routing with buffer insertion under transition time constraints

Maze routing with buffer insertion under transition time constraints (2002).

Maze routing with buffer insertion and wiresizing (2000).

Maze routing with buffer insertion and wiresizing

A graph based algorithm for optimal buffer insertion under accurate delay models

Maze Routing with Buffer Insertion under Transition Time Constraints

A graph based algorithm for optimal buffer insertion under accurate delay models ∗.

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

Clock tree synthesis under aggressive buffer insertion

Maze routing with buffer insertion under transition time constraints

Similar Documents

Maze routing with buffer insertion under transition time constraints

Maze routing with buffer insertion under transition time constraints (2002).

Maze routing with buffer insertion and wiresizing (2000).

Maze routing with buffer insertion and wiresizing

A graph based algorithm for optimal buffer insertion under accurate delay models

Maze Routing with Buffer Insertion under Transition Time Constraints

A graph based algorithm for optimal buffer insertion under accurate delay models ∗.

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

Clock tree synthesis under aggressive buffer insertion

Maze routing with buffer insertion under transition time constraints