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

Full description

Saved in:
Bibliographic Details
Main Authors: Shi, Yiyu, Mesa, Paul, Yu, Hao, He, Lei
Other Authors: School of Electrical and Electronic Engineering
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