Files in this item



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


Title:VLSI routing on the hexagonal grid
Author(s):Powers, Kris Dee
Doctoral Committee Chair(s):Brown, Donna J.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
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.
Issue Date:1993
Rights Information:Copyright 1993 Powers, Kris Dee
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9411752
OCLC Identifier:(UMI)AAI9411752

This item appears in the following Collection(s)

Item Statistics