Degree Type

Thesis

Date of Award

2010

Degree Name

Master of Science

Department

Electrical and Computer Engineering

First Advisor

Chris Chu

Abstract

Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction

is becoming one of the most sought after problems in modern design

flow. In this thesis we present an algorithm to route a

multi-terminal net in the presence of obstacles. Ours is a top down

approach which includes partitioning the initial solution into

subproblems and using obstacle aware version of Fast Lookup Table based Wirelength Estimation (OA-FLUTE) at a lower level to generate an OAST followed by recombining them with some backend refinement. To construct an initial connectivity graph we use a novel obstacle-avoiding

spanning graph (OASG) algorithm which is a generalization of Zhou's

spanning graph algorithm without obstacle presented in ASPDAC 2001. The runtime complexity of our algorithm is O(n log n).

DOI

https://doi.org/10.31274/etd-180810-2776

Copyright Owner

Gaurav Ajwani

Language

en

Date Available

2012-04-30

File Format

application/pdf

File Size

45 pages

Share

COinS