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
Copyright Date
2010
Language
en
Date Available
2012-04-30
File Format
application/pdf
File Size
45 pages
Recommended Citation
Ajwani, Gaurav, "Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction" (2010). Graduate Theses and Dissertations. 11196.
https://lib.dr.iastate.edu/etd/11196
