Maze Routing with Buffer Insertion and Wiresizing

Minghorng Lai, D. F. Wong

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

32 Citations (Scopus)


We propose an elegant formulation of the Maze Routing with Buffer Insertion and Wiresizing problem as a graph-theoretic shortest path problem. This formulation provides time and space performance improvements over previously proposed dynamic-programming based techniques. Routing constraints such as wiring obstacles and restrictions on buffer locations and types are easily incorporated in the formulation. Furthermore, efficient software routines solving shortest path problems in existing graph application libraries can be applied. We construct a BP-Graph such that the length of every path in this graph is equal to the Elmore delay. Therefore, finding the minimum Elmore delay path becomes a finite shortest path problem. The buffer choices and insertion locations are represented as the vertices in the BP-Graph. The interconnect wires are sized by constructing a look-up table for buffer-to-buffer wiresizing solutions. We also provide a technique that is able to tremendously improve the runtime. Experiments show improvements over previously proposed methods.

Original languageEnglish
Title of host publication37th ACM/IEEE Design Automation Conference - Proceedings 2000
PublisherAssociation for Computing Machinery (ACM)
Number of pages5
ISBN (Print)9781581131871, 1581131879
Publication statusPublished - 5 Jun 2000
Event37th ACM/IEEE-CAS/EDAC Design Automation Conference, DAC 2000 - Los Angeles, United States
Duration: 5 Jun 20009 Jun 2000 (Conference proceedings) (Conference proceedings)

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)0738-100X


Conference37th ACM/IEEE-CAS/EDAC Design Automation Conference, DAC 2000
Country/TerritoryUnited States
CityLos Angeles
Internet address

Scopus Subject Areas

  • Hardware and Architecture
  • Control and Systems Engineering


Dive into the research topics of 'Maze Routing with Buffer Insertion and Wiresizing'. Together they form a unique fingerprint.

Cite this