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

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

Fingerprint

Routing algorithms
Networks (circuits)
Processing
Electronic design automation

ASJC Scopus subject areas

  • Control and Systems Engineering

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

UI-route : An ultra-fast incremental maze routing algorithm. / Huang, Tsung-Wei; Wu, Pei Ci; Wong, Martin D F.

Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014. Association for Computing Machinery, 2014. (Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014).

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

Huang, T-W, Wu, PC & Wong, MDF 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, International Workshop on System-Level Interconnect Prediction, SLIP 2014, San Francisco, CA, United States, 6/1/14. https://doi.org/10.1145/2633948.2633952
Huang T-W, Wu PC, Wong MDF. UI-route: An ultra-fast incremental maze routing algorithm. In Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014. Association for Computing Machinery. 2014. (Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014). https://doi.org/10.1145/2633948.2633952
Huang, Tsung-Wei ; Wu, Pei Ci ; Wong, Martin D F. / UI-route : An ultra-fast incremental maze routing algorithm. Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014. Association for Computing Machinery, 2014. (Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014).
@inproceedings{95c76d652ef84d62a8ea3b2261635226,
title = "UI-route: An ultra-fast incremental maze routing algorithm",
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.",
author = "Tsung-Wei Huang and Wu, {Pei Ci} and Wong, {Martin D F}",
year = "2014",
month = "1",
day = "1",
doi = "10.1145/2633948.2633952",
language = "English (US)",
isbn = "9781450330534",
series = "Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014",
publisher = "Association for Computing Machinery",
booktitle = "Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014",

}

TY - GEN

T1 - UI-route

T2 - An ultra-fast incremental maze routing algorithm

AU - Huang, Tsung-Wei

AU - Wu, Pei Ci

AU - Wong, Martin D F

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84907346342&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84907346342&partnerID=8YFLogxK

U2 - 10.1145/2633948.2633952

DO - 10.1145/2633948.2633952

M3 - Conference contribution

AN - SCOPUS:84907346342

SN - 9781450330534

T3 - Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014

BT - Proceedings of SLIP - System Level Interconnect Prediction Workshop, SLIP 2014

PB - Association for Computing Machinery

ER -