图的谱方法及其在纳米尺度集成电路分析优化中的应用

As the feature size continues to shrink, more than one billions of transistors are integrated in a single chip. The analysis and optimization tools for integrated circuits should have the capacity to deal with the problems in the scale of one hundred millions. A variety of analysis and optimization tools have employed the multi-level or hierarchical strategy to improve the capacity of the tools. On the other hand, since the wavelength of the lithography has not been significantly reduced, the integrated circuits also encounter the challenges of lower resolution of the lithography process. In this project, we propose to employ the idea of spectral analysis and spectral clustering methods from the spectral theory of graph to handle the problems of multi-level simulation/optimization, lithograph hotspot detection, layout decomposition of multiple patterning lithography. (1) We propose a fast and parallel spectral clustering to build the hierarchy of the large-scale circuits to improve the efficiency of circuit simulation/optimization. Compared with the traditional heuristic methods, the spectral clustering method can achieve more accurate and nature hierarchy with the support of mathematical theory. (2) We propose to employ the spectral clustering method to extract the "critical features" of the layout, and use the spectrum of the "critical feature" graph as the feature to build the SVM (Support Vector Machine), and thus realize the detection method for lithograph hotspots. (3) We propose to take the chromatic number bounds obtained from the spectral theory of the graphs as the criteria to judge whether the layout is suitable for the multiple patterning lithography. We also propose to use the spectral clustering method to solve the coloring problem of multiple patterning lithography. These new theory and methods not only significantly improve the efficiency of solving the aforementioned problems, but also contribute to the spectral theory for graphs.

随着集成电路特征尺寸的缩小和集成度的增加，集成电路设计优化处理问题规模不断膨胀，需要借助层次化方法来降低计算复杂度，提升处理问题规模。同时由于光刻所用光源的波长未显著减小，集成电路也面临光刻分辨率方面的挑战。本课题提出利用图的谱方法来解决集成电路层次化构建、光刻热点检测、多次曝光工艺版图分解问题。(1) 提出快速可并行的谱聚类方法，应用于层次化的集成电路分析优化。相比已有启发式算法，聚合结果更精确，具有数学理论支撑。(2) 提出利用谱聚类方法快速提取版图中"关键特征图"，并将图的谱作为支持向量机特征来检测"关键特征图"，实现光刻热点检测。 (3) 提出利用图的谱理论中的最小染色数的界，在设计早期衡量版图是否适合多次曝光工艺。并提出用谱聚类方法求解多次曝光版图分解的染色问题。这些新理论和新方法不仅将有效提升上述集成电路设计自动化问题的求解效率，同时对图的谱分析理论和方法的发展也具有重要意义。

本课题主要围绕图的谱方法及其在集成电路分析优化中的应用开展研究，研究了超大规模问题的谱聚类方法，图的谱方法在光刻热点检测问题及多次曝光版图图形分解问题中的应用以及基于谱聚类的层次化方法在集成电路分析优化问题中的应用等问题，完成了预期的研究目标。提出了基于预划分和并行的超大规模问题的谱聚类方法，可以提升聚类效率1个量级, 该方法被用于大规模电源地网络的降阶，可以降仿真速度提升18倍以上；提出将谱聚类方法用于提取版图中的关键子图，用于加速光刻热点检测；提出了基于正切空间测度和层次化的基于密度的聚类方法用于光刻热点分类,提高了分类精度；提出了针对先进光刻工艺的版图分解、切割点分配及布线算法；提出了系列贝叶斯方法利用不同层次电路的相关性来提高电路的分析效率；提出了系列利用贝叶斯优化策略来提升电路优化效率的方法，并应用于电路性能和成品率优化，可以提升优化效率2-5倍；发展了多目标贝叶斯优化和并行贝叶斯优化方法。至结题时，共发表论文26篇，其中SCI论文8篇，EI论文17篇。在IEEE Trans.上发表论文7篇，在集成电路设计自动化领域的最重要的国际会议IEEE/ACM DAC发表论文5篇，在机器学习领域顶级国际会议ICML发表论文1篇。此外，还在本领域的重要国际会议FPGA、ICCAD、DATE、ASPDAC、ISCAS上发表论文11篇。申请国家发明专利3项，获得软件著作权登记1项。基于层次化谱方法的电源地网络降阶方法2018年获得国际期刊Integration, the VLSI Journal最佳论文奖。此外，项目组还获得了DAC’2017、ASPDAC’2017最佳论文提名。项目负责人杨帆2018年获得国家自然科学基金委优秀青年基金资助。基于谱聚类的层次化互连线模型降阶方法已集成在北京华大九天软件有限公司的商用工具中，华大九天的相应工具已经在上百家单位应用。2018年，基于谱聚类的互连线模型降阶工具还集成到了中物院高性能数值模拟软件中心的电路仿真工具JEMS-CDS中。本项目共培养博士3名，硕士6名。