Geometric planning for VLSI routing and robot motion

Maddila, Sanjeev Rao

Permalink

https://hdl.handle.net/2142/22372 Copy

Description

Title

Geometric planning for VLSI routing and robot motion

Author(s)

Maddila, Sanjeev Rao

Issue Date

1989

Department of Study

Electrical and Computer Engineering

Discipline

Electrical and Computer Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Mathematics
• Engineering, Electronics and Electrical
• Computer Science

Language

eng

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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/22372

Copyright and License Information

Copyright 1989 Maddila, Sanjeev Rao

Owning Collections