UI-route: An ultra-fast incremental maze routing algorithm

Tsung-Wei Huang, Pei Ci Wu, Martin D F Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Grid-based maze routing is a fundamental problem in electronic-design- automation (EDA) domain. A core primitive deals with a large query set about route connectivity subject to incremental changes on grid graph. Existing approaches pertain to batch processing, where each route query is independently and repeatedly solved by a routing procedure. Few researches so far discuss an efficient utilization of search knowledge in incremental fashion, which could dramatically speed up the search. Unfortunately, existing algorithms nearly rely on irregular and highly divergent search space, imposing acceleration challenges on refitting them to incremental version. Consequently, in this paper we present UI-Route, an ultra-fast incremental maze routing algorithm in grid environment. UI-Route is unique in breaking route equivalence, proving that a huge amount of equivalent search efforts can be optimally and incrementally eliminated. Equivalence breaking enables regularized search space, delivering well-tabulated search knowledge through the incremental processing. Moreover UI-Route is largely orthogonal to many applications built upon maze routing and therefore can seamlessly substitute for speedup. Experimental results on a set of modern circuit benchmarks demonstrate that UI-Route achieves prominent speedup over existing algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014
PublisherAssociation for Computing Machinery
ISBN (Print)9781450330534
DOIs
StatePublished - Jan 1 2014
EventInternational Workshop on System-Level Interconnect Prediction, SLIP 2014 - San Francisco, CA, United States
Duration: Jun 1 2014Jun 2 2014

Publication series

NameProceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014

Other

OtherInternational Workshop on System-Level Interconnect Prediction, SLIP 2014
CountryUnited States
CitySan Francisco, CA
Period6/1/146/2/14

ASJC Scopus subject areas

  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'UI-route: An ultra-fast incremental maze routing algorithm'. Together they form a unique fingerprint.

  • Cite this

    Huang, T-W., Wu, P. C., & Wong, M. D. F. (2014). UI-route: An ultra-fast incremental maze routing algorithm. In Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014 (Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014). Association for Computing Machinery. https://doi.org/10.1145/2633948.2633952