Masters Theses

Date of Award

5-2000

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Dinish P. Mehta

Committee Members

Bruce Whitehead, Bruce Bomar

Abstract

This thesis presents a new algorithm for the global routing of M3-layer single-trunk Steiner trees. The new algorithm,called selective sequential trunk locking (SSTL), works by selecting a trunk from a set of trunks,then locking the trunk in place. The remainder of the trunks in the set are adjusted according to their relationships to the locked trunk. An input file provides the selection criteria along with the chip and circuit layout information. SSTL is compared to a divide and conquer algorithm, which works by recursively dividing the area the trunks exist in then moving trunks from more highly congested areas to less highly congested areas. When the size of an area is at or below a threshold size, an attempt is made to lock down all trunks in the area. The experimental results show that, although the divide and conquer algorithm has some advantages over SSTL, SSTL wins in the most important area SSTL will lock down all trunks in the chip under a wider variety of conditions than divide and conquer.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS