基于BIE-WOS方法的并行全芯片寄生电容参数提取算法研究

Parallel computation on extreme scale computing platform and local computation are the feasible approaches for large-scale realistic engineering problems, such as the full-chip parasitic capacitance extraction. However, it is definitely not easy to improve current algorithms to obtain the high scalability and parallel efficiency on such platform. Traditional Boundary Element Methods (BEM) methods are with the merits of high accuracy and versatility, but they belong to global methods, which are difficult to be parallelized with high scalability and to be locally computed. Nevertheless, random methods can be easily parallelized and locally computed, but many realistic engineering problems cannot be solved, for example, the intensity of electric field on interconnect..Based on the novel Boundary Integral Equation-Walk On Spheres (BIE-WOS) algorithm, which holds the merits of versatility from BEM and scalability and local computation from Random methods simultaneously, we will research the error analysis of the BIE-WOS algorithm, efficient method of computing the distance function in 3D space, and accelerating technologies by GPU, Intel Phi and so on. Then, we will implement a parallel BIE-WOS algorithm on “TianHe2” platform, and apply it for realistic engineering problems, for example, the full-chip parasitic capacitance extraction. Comparing the parallel BIE-WOS algorithm with parallel FEM/BEMs will reveal the different pros and cons of two different technical approaches for parallel computation on extreme scale computing platform. .This project will improve the BIE-WOS algorithm into a useful parallel method.

超大规模并行计算和无损局部计算是解决全芯片寄生电容参数提取等大规模工程问题的可行途径，但改造现有算法使之具有高并行规模和并行效率绝非易事。传统边界元法虽精度高、适应性广，但属全局性方法，实现大规模并行和无损局部计算困难；随机法虽易并行和局部求解，但无法计算导体表面电场强度，限制了其适用范围。.本项目基于自主提出的BIE-WOS算法，该算法兼具边界元法适用性广和随机法易并行、可局部求解的优势。本项目拟解决BIE-WOS算法误差分析、空间距离快速计算、GPU和众核加速等问题，并在“天河二号”等平台上实现并行BIE-WOS算法，应用于全芯片寄生电容参数提取等实际工程问题。与现有并行有限元/边界元法的比较，将深刻揭示在超大规模平台下两种不同并行线路的优点和局限性。本项目将为BIE-WOS方法从一个理论算法，成长为一个有用的并行算法奠定基础。

在14/7/5纳米以下技术节点，集成电路中寄生参数、光刻、工艺扰动等可制造新设计问题对电路性能和成品率产生极大影响，是制约集成电路设计的瓶颈问题。本项目从基于随机法的寄生参数提取问题出发，在BIE-WOS算法误差分析和异构并行、高维度集成电路成品率分析和优化、扰动时序和光刻版图分解技术等三个方面展开研究工作，取得了一系列具有国际前沿水平的创新性研究成果。.（1）针对BIE-WOS的误差分析和异构并行，分析了第一类积分方程误差大的根源，并提出采用第二类积分方程有效控制误差的方法，在约5120个CPU核上验证了算法的并行效率和精度；提出FPGA/CPU异构并行平台实现高能效比的随机并行算法；提出简单、高效的可控重复执行次数多线程事务存储编程模型。上述成果为BIE-WOS算法走向工程应用提供理论和技术基础。（2）针对高维集成电路成品率分析和优化，提出了非高斯采样、贝叶斯推断以及神经网络等方法，将与维度呈指数关系的成品率分析和优化问题，降为常数关系，并应用于上海高性能集成电路设计中心国产神威CPU处理器的存储电路良率分析和优化问题中。（3）针对扰动时序和光刻版图分解技术算法，提出基于改进图的高效时序分析方法、基于迭代划分的多重图案版图分解方法、基于2D装箱算法的光刻字符盘优化设计方法等，其中扰动时序分析和优化方法，已集成到Synopsys公司IC Compiler工具物理设计的post routing优化工具中。.本项目共发表论文9篇，其中SCI收录3篇、EI收录6篇。计算数学领域著名SCI期刊Communications In Computational Physics论文1篇；EDA领域著名SCI期刊Journal ACM Trans. on DAES (TODAES) 论文2篇。EDA 领域顶尖国际会议IEEE/ACM DAC论文2篇、IEEE/ACM DATE论文2篇、ASP-DAC 论文1篇、IEEE ISPA论文1篇。申请国家发明专利7项。