Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
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).