Multi-layer channel routing

Abstract

A channel is a rectangular area of a VLSI (Very Large Scale Integrated) chip which is used to make electrical connections between circuits on the chip. Channel Routing is the problem of providing the interconnections for all circuits attached to the periphery of the channel such that the total area of the channel is minimized. Previous heuristics for solving the channel routing problem have focused on channels which have only two layers of interconnect available. Recent VLSI fabrication advances now allow more than two layers of interconnect. This dissertation is an investigation into channel routing using multiple layers of interconnection. A formal description of the multi-layer channel routing problem is presented. In the reserved z-layer model of channel routing adjacent layers of interconnect are reserved for wires which run in orthogonal directions. Thus there are three reserved z-layer models: the HiVi+l, HiVi and Hi+lVi models, where i > 0 denotes the number of horizontal (H) and vertical (V) layers of interconnect available. Previous techniques for modeling constraints which must be satisfied in order to produce a routing for a channel are unified by the definition of the channel constraint graph. r The intrinsic complexity of the channel routing problem is investigated and it is shown that channel routing using restricted-doglegs in the H2Vl model is NP-complete. Optimal algorithms for routing channels in the HiVi+ 1 model are presented which have runtime complexity linear in the size of the corresponding channel constraint graph. Heuristic algorithms are developed which route channels in the Hi Vi and Hi+ 1 Vi models. These heuristics are shown to have runtime linear in the size of the corresponding channel constraint graph. Upper bounds on the worst case performance of these heuristics are proved. Results of experiments which included routing many randomly generated channels having characteristics of channels found in industrial VLSI design environments are reported. These experiments show that the channel routing heuristics developed in this dissertation route almost 100% of these randomly generated channels using only two rows above the theoretic minimum in the Hi Vi and Hi+ 1 Vi models, i>2.

Notes

This item is only available in print in the UCF Libraries. If this is your thesis or dissertation, you can help us make it available online for use by researchers around the world by STARS for more information.

Graduation Date

1989

Semester

Spring

Advisor

Mukherjee, Amar

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Department

Computer Science

Format

PDF

Pages

257 p.

Language

English

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0027201

Subjects

Arts and Sciences -- Dissertations, Academic; Dissertations, Academic -- Arts and Sciences

Accessibility Status

Searchable text

This document is currently not available here.

Share

COinS