This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/21770
Description
Title
VLSI routing on the hexagonal grid
Author(s)
Powers, Kris Dee
Issue Date
1993
Doctoral Committee Chair(s)
Brown, Donna J.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
The hexagonal grid consists of vertical columns, and positive and negative diagonal tracks with slopes +30$\sp\circ$ and $-$30$\sp\circ$, respectively. The goal of this thesis research has been to investigate the potential of the hexagonal grid for VLSI detailed routing. We have studied the layout geometry of the hexagonal grid and shown it to be compatible with standard VLSI implementation. This distinguishes the hexagonal routing models developed in this work as the first consistent environments on which to base comparative study of diagonal and traditional rectilinear routing.
A major portion of this work has been devoted to assessing the potential of hexagonal routing in terms of the specific problem of channel routing. We have considered algorithms for arbitrary channel routing problems (CRP's), as well as algorithms specifically designed for those problems most appropriate to diagonal interconnection. More specifically, for a CRP with density d, the availability of the diagonal tracks leads to a lower bound of ${d\over\sqrt{3}}$ for routing without overlap. We present three algorithms for routing CRP's on the hexagonal grid in widths which approach or achieve this lower bound. Our algorithms route in three, four, and five layers, respectively, and as is the case on the square grid, the less restrictive models better approximate the lower bound. The CRP's best suited to diagonal interconnection are those in which the maximum net span is small, relative to channel density. In particular, for a CRP having maximum net span $s\sp*$, the maximum possible density is 2$s\sp*$. We give an algorithm which routes every (2-terminal or multiterminal) 2-sided net CRP in width ${2\over\sqrt{3}}s\sp*$ + O(1) in three layers. For problems having density d near the 2$s\sp*$ upper bound, a routing of width $s\sp*$ is essentially optimal on the hexagonal grid. Further, for a CRP having $s\sp* < {\sqrt{3}\over 2}d$, a hexagonal routing of width $s\sp*$ hu is less than the square grid lower bound for routing without overlap.
We have also investigated hexagonal routing in more general frameworks. Specifically, we have examined relations between traditional rectilinear and hexagonal layouts, and in doing so, provide a comparative basis which is independent of any particular class of routing problems. Finally, we have considered the effect of the geometry of the hexagonal grid on the requisite conditions for layout of more general instances of the detailed routing problem.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
