Circuit-simulated obstacle-aware Steiner routing
This article develops circuit-simulated routing algorithms. We model the routing graph by an RC network with terminals as inputs, and show that the faster an output reaches its peak, the higher the possibility for the corresponding Hanan or escape node to become a Steiner point. This enables...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2012
|
Online Access: | https://hdl.handle.net/10356/94322 http://hdl.handle.net/10220/8742 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-94322 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-943222020-03-07T14:02:44Z Circuit-simulated obstacle-aware Steiner routing Shi, Yiyu Mesa, Paul Yu, Hao He, Lei School of Electrical and Electronic Engineering This article develops circuit-simulated routing algorithms. We model the routing graph by an RC network with terminals as inputs, and show that the faster an output reaches its peak, the higher the possibility for the corresponding Hanan or escape node to become a Steiner point. This enables us to select Steiner points and then apply any minimum spanning tree algorithm to obtain obstaclefree or obstacle-aware Steiner routing. Compared with existing algorithms, our algorithms have significant gain on either wirelength or runtime for obstacle-free routing, and on both wirelength and runtime for obstacle-aware routing. Accepted version 2012-10-10T06:57:35Z 2019-12-06T18:54:10Z 2012-10-10T06:57:35Z 2019-12-06T18:54:10Z 2007 2007 Journal Article Shi, Y., Mesa, P., Yu, H., & He, L. (2007). Circuit-simulated obstacle-aware Steiner routing. ACM Transactions on Design Automation of Electronic Systems, 12(3). 1084-4309 https://hdl.handle.net/10356/94322 http://hdl.handle.net/10220/8742 10.1145/1255456.1255465 148334 en ACM transactions on design automation of electronic systems © 2007 ACM. This is the author created version of a work that has been peer reviewed and accepted for publication by ACMTransactions onDesign Automation of Electronic Systems, ACM. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1145/1255456.1255465]. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
description |
This article develops circuit-simulated routing algorithms. We model the routing graph by an RC
network with terminals as inputs, and show that the faster an output reaches its peak, the higher
the possibility for the corresponding Hanan or escape node to become a Steiner point. This enables
us to select Steiner points and then apply any minimum spanning tree algorithm to obtain obstaclefree
or obstacle-aware Steiner routing. Compared with existing algorithms, our algorithms have
significant gain on either wirelength or runtime for obstacle-free routing, and on both wirelength
and runtime for obstacle-aware routing. |
author2 |
School of Electrical and Electronic Engineering |
author_facet |
School of Electrical and Electronic Engineering Shi, Yiyu Mesa, Paul Yu, Hao He, Lei |
format |
Article |
author |
Shi, Yiyu Mesa, Paul Yu, Hao He, Lei |
spellingShingle |
Shi, Yiyu Mesa, Paul Yu, Hao He, Lei Circuit-simulated obstacle-aware Steiner routing |
author_sort |
Shi, Yiyu |
title |
Circuit-simulated obstacle-aware Steiner routing |
title_short |
Circuit-simulated obstacle-aware Steiner routing |
title_full |
Circuit-simulated obstacle-aware Steiner routing |
title_fullStr |
Circuit-simulated obstacle-aware Steiner routing |
title_full_unstemmed |
Circuit-simulated obstacle-aware Steiner routing |
title_sort |
circuit-simulated obstacle-aware steiner routing |
publishDate |
2012 |
url |
https://hdl.handle.net/10356/94322 http://hdl.handle.net/10220/8742 |
_version_ |
1681047948300910592 |