Doctoral Dissertations

Date of Award

5-1998

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Computer Science

Major Professor

Michael A. Langston

Committee Members

Booth, Bouldin. Raghavan

Abstract

Automating the physical design of VLSI circuits is a very hard problem that has increased in significance as circuits have grown in size and complexity. Several vari-ations of the general problem exist, depending mainly on the underlying technology. Many attempts to automate circuit layout begin with modeling circuits as graphs or hypergraphs. Laying out the circuit so that some objective function is optimized then corresponds to laying out its graph so that some graph metric is optimized. We begin by considering pathwidth. This metric is directly related to the area of circuits laid out in Gate Matrix and Weinberger array styles. It is NP-hard to determine pathwidth, even on severely restricted classes of graphs. We present algorithms to approximate the pathwidth of several related classes of graphs, such as k-chordal, outerplanar, series-parallel and Halin graphs. Our algorithms work in O(nlognn) time on graphs of order n, and produce solutions within small constant factors of the optimum. Next we focus on a different aspect of the circuit layout problem, one that arises during design using multiple field-programmable gate arrays (FPGAs). .A critical step during multiple-FPGA design is the partitioning of a circuit into pieces that satisfy size and pin-count constraints. We examine variants of partitioning with these constraints, and develop complexity results and algorithms for the general and fixed-parameter versions of each problem. We conclude on a more theoretical note, designing some foundational graph tests that can be used in a circuit layout library. We develop an algorithm to decide whether AT, the complete graph on four vertices, is immersed in an arbitrary input graph. We also devise an algorithm to decide whether the k-bond, the graph consisting of two vertices joined by k edges, is immersed in a series-parallel graph. Both algorithms work in linear time. Finally, we present a fast algorithm that may be useful as a preprocessing step in immersion tests.

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

Share

COinS