MSPA-MCS: Scalable Optimization Algorithms for VLSI Circuit Physical Design

MSPA-MCS：VLSI 电路物理设计的可扩展优化算法

• 批准号: 0528583
• 负责人: Jason Cong
• 金额: --
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-15 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0528583&HistoricalAwards=false
• 关键词: MSPA; MCS; Scalable; Optimization; Algorithms

ABSTRACT0528583Tony ChanUniversity of California-Los AngelesScalable Optimization Algorithms for VLSI Circuit Physical Design (NSF Proposal 0528583)Physical design is one of the most important and challenging steps in the synthesis of very-large scale integrated circuits (VLSI), as it directly determines the distribution and layout of the interconnects, i.e. the wires connecting millions or billions of transistors. These wires are the bottleneck of circuit and system performance, as transistors are now so fast that it takes more time to transmit signals than to compute them. Core problems in physical design include the shaping and placement of both circuit components ("modules") and the wires connecting them. As the size and complexity of integrated circuits continue to grow exponentially with Moore's Law to 10 to 100 million modules, so does the difficulty in achieving designs that meet required performance targets under various constraints, such as constraints on the maximum power or temperature. Sophisticated computer-aided design (CAD) software plays a vital role in VLSI design. The systematic procedures or "algorithms" from which this software is derived are at the center of efforts to improve the quality and efficiency of circuit designs. To be useful in practice, these algorithms must be scalable; i.e., their runtime increases at a modest rate, e.g., linearly, as the design size increases. Mathematical formulations have been used extensively for physical design problems, but most of them assume either that the modules are evenly distributed over the circuit or that they follow a pre-specified density profile. The focus of this research is on the development of mathematical models and techniques to support the development of practical algorithms for the more general physical-design setting in which no pre-specified density profile is available. Such a formulation is a much better reflection of the underlying physical design problem, as, for example, the temperature distribution will not be known a priori.The broader impact of a high-quality scalable algorithm for placement optimization under generalized density inequalities would be considerable. Improved design algorithms produce more powerful circuitry. A scalable high-quality solver with physically accurate constraint modeling allows designers to integrate diverse circuit elements in complex ways. The resulting increase in computing power ultimately translates into new products, new markets, and new science. Ultimately, the vast size and complexity of nano-scale design problems can realistically be approached only by generic, scalable algorithms yet to be developed. The successful formulation of a truly scalable methodology for physically realistic VLSI designs can be expected to have lasting and far-reaching impact on future design paradigms.

摘要0528583加利福尼亚 - 洛斯 - 洛斯无意尺度的vlsi电路物理设计（NSF提议0528583）物理设计的Chanuniversity是综合非常重要的，最重要的步骤之一数十亿个晶体管。 这些电线是电路和系统性能的瓶颈，因为晶体管现在如此之快，以至于传输信号比计算它们要花费更多的时间。 物理设计中的核心问题包括两个电路组件（“模块”）的塑形和放置以及连接它们的电线。 随着综合电路的规模和复杂性随着摩尔定律的指数增长到10至1亿个模块，因此实现在各种约束下满足所需性能目标的设计的困难也是如此，例如对最高功率或温度的约束。 复杂的计算机辅助设计（CAD）软件在VLSI设计中起着至关重要的作用。 该软件得出的系统过程或“算法”是提高电路设计质量和效率的努力的中心。 为了在实践中有用，这些算法必须可扩展。即，它们的运行时间以适度的速度增加，例如，随着设计尺寸的增加，它们的运行时间是线性的。 数学公式已广泛用于物理设计问题，但是大多数公式假设模块均匀分布在电路上，或者它们遵循预先指定的密度曲线。 这项研究的重点是开发数学模型和技术，以支持更一般的物理设计设置实用算法的开发，在该设置中，没有预先指定的密度曲线可用。 这样的公式是对基本物理设计问题的更好反映，例如，温度分布将是先验的。改进的设计算法会产生更强大的电路。具有物理上准确约束建模的可扩展高质量求解器使设计人员可以以复杂的方式整合不同的电路元素。随之而来的计算能力的增加最终转化为新产品，新市场和新科学。最终，只有通过尚待开发的通用，可扩展的算法才能真正解决纳米级设计问题的巨大规模和复杂性。可以预期，可以成功地为身体上现实的VLSI设计提供真正可扩展的方法，对未来的设计范式产生持久和深远的影响。