Efficient construction of minimal spanning tree avoiding rectilinear directional obstacles

Kyosun Kim, Ramesh Karri

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

Abstract

Recently, the obstacle avoidance in the Minimum Spanning Tree (MST) problem, which is one of the most important CAD problems, has been received a great deal of attention. In general, this Obstacle Avoiding MST (OAMST) can be efficiently found as a sub-graph of a Spanning Graph (OASG) which is constructed by connecting neighboring pins and obstacle corners. Unfortunately, its application was quite limited since obstacles were restricted to be rectangular, and prohibit wiring routes from passing through them in both horizontal and vertical dimensions. In this paper! the problem is extended so that the obstacles may have rectilinear shapes, and allow wiring routes passing through them either in the horizontal or vertical dimension. A finite state machine-based approach is proposed to recognize the complicated obstacle patterns, and precisely create edges that construct the OASG. Two algorithms from previous work have been modified to include this approach without increasing the computational complexity. The roposed approach and algorithm have been implemented and validated on a comprehensible set of nets that are sampled from an industrial strength system-on-chip design.

Original languageEnglish (US)
Title of host publication2008 International SoC Design Conference, ISOCC 2008
PagesI196-I199
DOIs
StatePublished - 2008
Event2008 International SoC Design Conference, ISOCC 2008 - Busan, Korea, Republic of
Duration: Nov 24 2008Nov 25 2008

Publication series

Name2008 International SoC Design Conference, ISOCC 2008
Volume1

Other

Other2008 International SoC Design Conference, ISOCC 2008
CountryKorea, Republic of
CityBusan
Period11/24/0811/25/08

Keywords

  • Minimum Spanning Tree
  • Obstacle-Avoidong
  • Rectilinear Directional
  • Spanning Graph

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'Efficient construction of minimal spanning tree avoiding rectilinear directional obstacles'. Together they form a unique fingerprint.

Cite this