High Performance Solutions to VLSI CAD Problems

三个领域的计算有效的算法设计的IC的正在调查中。 1. 超大规模集成电路图形显示的算法：正在研究在流行的显示设备上快速显示多边形和线条集合的顺序和并行算法。 2. 当一个VLSI设计可以用图来建模时，通常需要分裂或删除一组顶点，以便得到的图将满足设计标准。 类的图形，其中的问题是多项式可解的和方法，以尽量减少所产生的有向图的组件的数量正在确定。 3. 正在研究各种设计风格的模块定向和旋转问题，以确定哪些是NP难和多项式可解的。 近似算法、启发式算法和多项式算法正在针对NP难问题进行开发。

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.