High Performance Solutions to VLSI CAD Problems

点击翻译按钮获取中文摘要

Three areas of computationaly efficient algorithms for design of IC's are under investigation. 1. Algorithms for display of VLSI artwork: Sequential and parallel algorithms to quickly display collections of polygons and lines on popular display devices are being investigated. 2. When a VLSI design can be modeled by graphs, it is often required to split or delete a set of vertices so that the resulting graph will satisfy design criteria. Classes of graphs for which the problems are polynomially solvable and methods for minimizing the number of components in the resulting digraph are being determined. 3. Module orientation and rotation problems for a variety of design styles are being examined to determine which are NP-hard and polynomially solvable. Approximation algorithms, heuristics, and polynomial algorithms are being developed for the NP-hard problems.