Doctoral Dissertations

Date of Award

8-1994

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Computer Science

Major Professor

Michael Allen Langston

Committee Members

Jean Blair, Heather Booth, Don Bouldin

Abstract

Layout permutation is a frequently used process in VLSI design whereby some of the circuit elements are arranged in order to obtain an optimum layout. Our aim is to develop practical algorithms for well-known layout permutation problems such as Gate Matrix Layout and Minimum Cut Linear Arrangement. Because these opti-mization problems are NP-Hard, and also because in practice the problems tend to be of bounded size, we address their fixed-parameter variants. Although recent advances in the field of algorithms have yielded powerful non-constructive tools to tackle these problems, such algorithms have remained imprac-tical. The main feature of these algorithms is their reliance on a finite set of for-bidden structures known as "obstructions" to determine whether a layout is feasible. We study the applicability of these novel techniques to problems in VLSI design and present a practical approach for finding optimal solutions for fixed-parameter versions of problems such as Gate Matrix Layout and Minimum Cut Linear Arrangement. We model circuits by graphs and transform layout optimization problems to graph width minimization problems. This transformation extends the applicability of our algorithms to a wide variety of problems in VLSI design and other domains. To demonstrate our approach, we design a linear-time decision algorithm for 3-track Gate Matrix Layout using only a few obstructions and devise fast self-reductions to find a layout if any exist. Ours is the first practical self-reduction algorithm based on obstruction sets. These algorithms have been implemented and experimental results show that they yield correct results "almost always." In an effort to extend this method for gate matrix layouts with more than 3 tracks, we present several lower and upper bounds for the treewidth and pathwidth metrics of a graph. We also present fast algorithms to compute some of the bounds in practice. These bounds give us a better understanding of the structure and number of obstruc-tions and we develop a general method to construct some of the dense obstructions for gate matrix layout. We find that there are numerous dense obstructions and explore ways to devise tests for them. Based on the cutwidth metric of graphs, we also develop algorithms for the Mini-mum Cut Linear Arrangement problem.

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

Share

COinS