VLSI (Very Large-Scale Integrated): Models, Computation andAlgorithms

VLSI（超大规模集成）：模型、计算和算法

• 批准号: 8700767
• 负责人: Te Chiang Hu
• 金额: $ 10.86万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-07-01 至 1989-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8700767&HistoricalAwards=false
• 关键词: VLSI; Very; Large; Scale; Integrated

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.

首席研究员的方法是开发和研究 典型VLSI/ULSI设计问题的数学模型，包括 阵列压缩和电路布局问题。 新的预测 将用真实的设计数据和问题检查模型。 教授 胡锦涛的方法是集中在三个主题上： (1)发现VLSI/ULSI设计问题的新的图模型， 开发具有误差界的启发式算法， 分析. 先前的图表模型， 开发可以推广到设计问题，他将开发 具有误差界的线性启发式算法。 (2)找到高级数学编程技术，可以实现 满足各种优化标准中的任何一种的电路布局。 (3)研究一类特殊的几何规划问题， 最优解是整数，或者用有界误差近似， 整数解。 这种方法将依赖于一个强大的 数学假设称为均匀平滑假设， 允许分而治之的方法来设计算法， 相关分析。 这项研究解决了需要产生快速成功的布局 超大规模集成电路（VLSI/ULSI）。 这是一个 这一需求已经变得至关重要，因为这些设备已经成为 行业越来越复杂，竞争越来越激烈。 有很多 解决VLSI/ULSI设计中的问题的方法;然而，它们遭受一个 两个问题。 要么设计方法是启发式的，可能会失败 由于分析方法不完善而意外;或 算法，这是很好地理解，需要太多的时间时， 涉及大电路。 基本需要是更加现实和 复杂的计算模型和新的分析方法， 从而导致有效VLSI/ULSI设计方法。 主要研究者 将运用他优秀的理论和数学背景 来解决这些问题。