High Performance Solutions to VLSI CAD Problems

VLSI CAD 问题的高性能解决方案

• 批准号: 9103379
• 负责人: Sartaj Sahni
• 金额: $ 27.73万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-01-01 至 1997-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9103379&HistoricalAwards=false
• 关键词: Performance; Solutions; 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.

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