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

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

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.