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

Copyright Owner

Gaurav Ajwani

Language

en

Date Available

2012-04-30

File Format

application/pdf

File Size

45 pages

Share

COinS