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.

摘要0528583Tony Chan加州大学洛杉矶分校超大规模集成电路物理设计的可扩展优化算法（NSF提案0528583）物理设计是超大规模集成电路（VLSI）综合中最重要和最具挑战性的步骤之一，因为它直接决定分布和互连的布局，即连接数百万或数十亿个晶体管的电线。 这些电线是电路和系统性能的瓶颈，因为晶体管现在速度如此之快，传输信号所需的时间比计算信号所需的时间还要多。 物理设计的核心问题包括电路元件（“模块”）以及连接它们的电线的成形和放置。 随着集成电路的尺寸和复杂性随着摩尔定律继续呈指数级增长，达到 10 至 1 亿个模块，在各种约束（例如最大功率或温度的约束）下实现满足所需性能目标的设计的难度也随之增加。 先进的计算机辅助设计 (CAD) 软件在 VLSI 设计中发挥着至关重要的作用。 该软件所源自的系统程序或“算法”是提高电路设计质量和效率的核心。 为了在实践中有用，这些算法必须是可扩展的；即，随着设计尺寸的增加，它们的运行时间以适度的速率（例如线性）增加。 数学公式已广泛用于物理设计问题，但大多数数学公式都假设模块均匀分布在电路上，或者遵循预先指定的密度分布。 这项研究的重点是数学模型和技术的开发，以支持针对更通用的物理设计设置（其中没有预先指定的密度分布）开发实用算法。 这样的公式可以更好地反映潜在的物理设计问题，例如，温度分布不会先验地知道。在广义密度不等式下，用于布局优化的高质量可扩展算法的更广泛影响将是相当大的。改进的设计算法产生更强大的电路。可扩展的高质量求解器具有物理上精确的约束建模，使设计人员能够以复杂的方式集成不同的电路元件。由此产生的计算能力的提高最终转化为新产品、新市场和新科学。最终，纳米级设计问题的巨大规模和复杂性实际上只能通过尚未开发的通用、可扩展算法来解决。成功制定用于物理现实的 VLSI 设计的真正可扩展的方法预计将对未来的设计范例产生持久而深远的影响。