Files in this item



application/pdf9010946.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Geometric planning for VLSI routing and robot motion
Author(s):Maddila, Sanjeev Rao
Department / Program:Electrical and Computer Engineering
Discipline:Electrical and Computer Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Engineering, Electronics and Electrical
Computer Science
Abstract:This thesis proposes a decomposition-based algorithmic paradigm, called planning with local experts, where the given global planning problem is decomposed into a set of subproblems that are each solved efficiently in a prescribed sequence and then the solutions of the subproblems are merged together.
In the first part of the thesis, we investigate the problems of VLSI routing. In particular, we propose a way of decomposing the problem of routing in a general placement of rectangular modules into a set of subproblems of routing in junctions of L-, S-, T-, and X-shapes. We give non-trivial lower bounds on the channel widths of the associated channels of a junction. For example, we prove that $t\sb1$ + $t\sb2$ $\geq$ ${3\over2}$($d\sb1$ + $d\sb2$) for routing three-terminal nets in an L-shaped junction, where $t\sb1$ and $t\sb2$ are the widths, and $d\sb1$ and $d\sb2$ are the densities of the horizontal and vertical channels of the L-shaped junction, respectively. We also give routers for the general junctions, for the cases of routing two-, three-, and multi-terminal nets. For example, we prove that for routing two-terminal nets in an L-shaped junction $t\sb1$ + $t\sb2$ = $d\sb1$ + $d\sb2$, $t\sb1$ + $t\sb2$ $\leq$ ${3\over2}$($d\sb1$ + $d\sb2$) for the case of three-terminal nets, and $t\sb1$ + $t\sb2$ $\leq$ 2($d\sb1$ + $d\sb2$) for the case of multi-terminal nets.
In the second part of the thesis, we investigate the problems of robot motion planning. In particular, we consider a technique to decompose the problem of moving a robot among a set of rectangles into a set of subproblems of moving the robot in certain localites. We give local experts for the local planning problems of moving a polygonal robot around a corner, and moving through a junction of general shape. For example, we give an $O$($m$ log $m$) algorithm for moving a convex $m$-gon around the corner in a corridor. Thus, using our decomposition scheme we develop an $O$($mn$ log $m$ + $n$ log $n$) algorithm for moving a convex polygon with $m$ corners among $n$ iso-oriented rectangles.
Issue Date:1989
Rights Information:Copyright 1989 Maddila, Sanjeev Rao
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9010946
OCLC Identifier:(UMI)AAI9010946

This item appears in the following Collection(s)

Item Statistics