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

物理设计是超大规模集成电路（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.