Abstract

The custom integrated circuit routing problem normally requires partitioning into rectangular routing regions. Natural partitions usually result in regions that form both "channels" and "areas". This dissertation introduces several new channel and area routing algorithms and measures their performance.

A formal description of the channel routing problem is presented and a relationship is established between the selection of intervals for each track and the number of tracks in the completed channel. This relationship is used as an analysis tool that leads to the development of two new and highly effective channel routing algorithms: the Revised and LCP algorithms. The performance of these algorithms is compared against the Dogleg, Greedy, and several area routing algorithms over sets of randomly generated channels. The results indicate performance increases ranging from 2.74 to 34 times, depending on the characteristics of the channel.

In area routing, a new Degree of Freedom (DOF) based algorithm is developed that is straightforward to implement, is extensible to multipoint nets and reports if a path does not exist to complete the net. The quality of area routing algorithms is measured by the difficulty of the areas that can be successfully routed over sets of randomly generated areas. An extended definition of Manhattan Area Measure (MAM) is introduced as a measure of the difficulty of completing the wiring for areas with multipoint nets.

The results show that the DOF algorithm has higher completion rates than the Lee algorithm. This difference is greatest in areas with high aspect ratios. A new measure of the difficulty of an area is developed that places upper bounds on the performance of area routing algorithms. In areas with low aspect ratios, the drop in algorithm completion rates is closely related to this upper bound.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

1986

Semester

Fall

Advisor

Cottrell, Larry K.

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Department

Computer Science

Format

PDF

Pages

186 p.

Language

English

Rights

Public Domain

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0021483

Contributor (Linked data)

Larry K. Cottrell (Q57978539)

Accessibility Status

Searchable text

Download

Share

COinS