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

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

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

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
Title of host publication2014 ACM/IEEE International Workshop on System Level Interconnect Prediction (SLIP)
PublisherIEEE
Pages1-8
Number of pages8
ISBN (Electronic)9781450330534
DOIs
Publication statusPublished - Jun 2014
Event2014 ACM/IEEE International Workshop on System Level Interconnect Prediction (SLIP) - San Francisco, CA, USA
Duration: 1 Jun 20141 Jun 2014

Publication series

NameProceedings of ACM/IEEE International Workshop on System Level Interconnect Prediction (SLIP)

Conference

Conference2014 ACM/IEEE International Workshop on System Level Interconnect Prediction (SLIP)
Period1/06/141/06/14

Fingerprint

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

Cite this