超大规模集成电路仿真验证中的模型降阶及稀疏表示

Discovering, exploiting, and representing sparsity of the problem is a fundamental approach for solving large-scale problems as well as current research focus in applied mathematics and other disciplines. Aiming at fulfilling the major national demands, we have extracted three problems in computational mathematics which rise from VLSI simulation and are closely related to sparsity: model reduction of linear systems, sparse representation of multi-variant model, and fast VLSI ODE solver exploiting the sparsity of solutions. Through crossing the boundaries of mathematical science and electronic engineering, we will.1. develop innovative theories and algorithms in aggregation-based model order reduction method,.2. study the sparse representation of multi-variant model based on compressed sensing methods,.3. establish novel theories and algorithms in solving VLSI ODE systems exploiting the sparsity of solutions, and.4. apply all of these theories and algorithms to the simulation and verification in VLSI..The preliminary results have demonstrated that the proposed aggregation-based model order reduction method has superior accuracy and efficiency over the existing methods. The project team members include experts from various academic and engineering disciplines such as numerical linear algebra, approximation theory, numerical optimization, and electronic design automation. We are equipped with the knowledge, research foundations, and years of experience in computational mathematics, EE, interdisciplinary as well as research results industrialization. The results of this project will enrich the theories and algorithms on sparsity in computational mathematics and lay a solid foundation for the development of electronic design automation tools in our nation.

发现、利用、表示问题中的稀疏性是求解大规模问题的根本手段，也是当前应用数学及其他多个学科的研究热点。本项目面向国家重大需求，从集成电路仿真验证中提炼了与稀疏性密切相关的三个计算数学的研究内容：线性系统的模型降阶、多参数模型的稀疏表示、利用解的稀疏性快速求解电路系统。本项目将通过数学与微电子学科的交叉，深入研究基于聚合的模型降阶创新理论及算法，研究基于压缩感知的多参数模型的稀疏表示、利用解的稀疏性快速求解电路系统的新理论及新算法，并将这些理论及算法应用于超大规模集成电路仿真验证。前期研究表明，我们提出的基于聚合的模型降阶新算法相比已有算法在精度和效率上具有显著优势。项目组成员具有数值代数、逼近论、数值优化以及电子设计自动化等项目必需的研究基础，具有研究成果产业化经验。本项目成果将在计算数学领域内丰富关于稀疏性的理论与算法，也将为我国电子设计自动化产业提供具有自主知识产权的工具奠定基础。

本项目对于模型降阶及稀疏表示的理论与算法及其在集成电路仿真验证中的应用开展了研究，取得了较丰硕的成果。..模型降阶的理论及算法。二阶Krylov子空间方法是苏仰锋及柏兆俊在2005年针对于大规模二阶系统模型降阶及二次特征值问题提出的方法，该方法已经成为二阶系统模型降阶的标准方法。该方法中构造投影子空间的SOAR过程对于几乎所有的实际应用都表现良好，但可以人工构造一个例子说明SOAR过程的不稳定性。为此，我们设计了一个新的TOAR过程。该过程具有如下优点：1. 我们严格证明了该过程的数值稳定性； 2. 非常容易推广到高次特征值问题及高阶系统模型降阶。TOAR也已经被写入多个软件包，用于求解包括时滞系统模型降阶，大规模非线性特征值问题等。.模型降阶在集成电路仿真验证中的应用。对于带多端口甚至大量端口的RC（电阻电容）电路，之前的模型降阶方法或者填充过多，或者精度太低。我们提出了基于聚合的RC模型降阶算法AMOR，该算法1. 基于对电阻（R)网络图的谱聚类； 2. 不会引入多余的非零元增加矩阵稠密性； 3. 相应的电容进行合并； 4. 可以获得降阶模型对应的物理可实现的降阶。该方法已经集成到华大九天的ALPS中，比传统的求解器大约快10倍；还应用于电源地中。.稀疏表示的理论及算法。我们证明了求解一类稀疏优化问题的ADMM 法是全局线性收敛的。其意义在于 1. 该模型不仅包含二次规划的稀疏优化模型, 还可以包含LASSO 等著名统计模型; 2. 模型可以引进多面体约束. 因此约束比以前的结果更具有一般性; 3. 以前的结果只是证明了二次规划的ADMM 的局部线性收敛..稀疏表示在集成电路仿真验证中的应用。针对1. 功率门控电源网络的瞬态仿真，基于稀疏恢复的思想，利用解的稀疏性加快线性方程组的求解，提出了改进的共轭梯度法MCG。2. 将稀疏表示技术应用于集成电路工艺参数空间分布的建模；3.优化设计参数。稀疏表示在集成电路设计中的应用是本项目的特色，取得了非常好的效果。