Maze routing with buffer insertion under transition time constraints

Li Da Huang, Minghorng Lai, D. F. Wong, Youxin Gao

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationProceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2002
EditorsCarlos Delgado Kloos, Jose da Franca
Place of PublicationUnited States
PublisherIEEE
Pages702-707
Number of pages6
DOIs
Publication statusPublished - Mar 2002
Event2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002 - Le Palais des Congrès, Paris, France
Duration: 4 Mar 20028 Mar 2002
https://past.date-conference.com/proceedings-archive/2002/YEAR.HTM (Conference proceedings)

Publication series

NameProceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE
ISSN (Print)1530-1591

Conference

Conference2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002
Country/TerritoryFrance
CityParis
Period4/03/028/03/02
Internet address

Scopus Subject Areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Maze routing with buffer insertion under transition time constraints'. Together they form a unique fingerprint.

Cite this