The principal investigator's approach is to develop and study mathematical models of typical VLSI/ULSI design problems, including array compaction and circuit layout problems. Predictions of the new models will be checked with real design data and problems. Professor Hu's approach is to concentrate on three topics: (1) Find new graph models of VLSI/ULSI design problems and from them develop heuristic algorithms with error bounds which give performance analysis. Previous graph models the principal investigator has developed can be generalized to design problems and he will develop linear heuristic algorithms with error bounds. (2) Find advanced mathematical programming techniques that can achieve circuit layouts that meet any of a variety of optimization criteria. (3) Study a special class of geometric programming problems where optimum solutions are integers, or are approximated with bounded error, by integer solutions. This approach will rely on a powerful mathematical assumption called the uniform smoothness assumption which permits a divide-and-conquer approach to design algorithms and an associated analysis. This research addresses the need to produce rapidly successful layouts of very and ultra large-scale integrated (VLSI/ULSI) circuits. It is a need that has become of paramount importance as such devices become increasingly complex and the industry more competitive. There are many approaches to problems in VLSI/ULSI design; however they suffer from one of two problems. Either the design methods are heuristic and can fail unexpectedly because analysis methods are not well developed; or formal algorithms, which are well understood, take too much time when very large circuits are involved. The basic need is for more realistic and sophisticated models of computation and new analysis methods that will lead to efficient VLSI/ULSI design methods. The principal investigator will bring to bear his excellent theoretical and mathematical background to the solution of these problems.
