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
Description
Summary: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.