处理含大量非分层介质结构的悬浮随机行走电容提取算法  

Efficient Floating Random Walk Based Techniques for Capacitance Extraction of Structures with a Large Number of Non-Stratified Dielectrics

作　　者：宋明烨 杨明[1,2] 喻文健 Song Mingye;Yang Ming;Yu Wenjian(Department of Computer Science and Technology,Tsinghua University,Beijing 100084;Beijing National Research Center for Information Science and Technology,Tsinghua University,Beijing 100084)

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]北京信息科学与技术国家研究中心,北京100084

出　　处：《计算机辅助设计与图形学学报》2024年第3期435-442,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：北京市自然科学基金(Z220003);清华大学自主科研计划(2021Z11GHX006).

摘　　要：为了解决包含大量非分层介质的随机行走电容提取算法预处理时间过长的问题,提出一种优化算法.本文算法一共有2步:首先基于八分块立方体即时采样技术,提出处理复杂非分层介质的等效介电常数计算方法;然后基于网格的空间管理技术,减少随机行走电容提取的预处理时间.针对不同的电容提取应用场景,还提供了选择不同非分层介质空间管理策略的建议.在多个来自集成电路设计版图的互连结构上的实验结果表明,所提算法在保证电容提取精度与随机行走运行效率的同时,显著地加快了非分层介质空间管理构造以及随机行走算法的预处理时间;在含有超过70万非分层介质的测例上,与现有算法相比,该算法使非分层介质的空间管理构造时间最多加速420倍,并使整个预处理时间从114s减少到30s.In order to solve the problem that the preprocessing time of the random walk algorithm is too long for capacitance extraction when dealing with a structure containing a large number of non-stratified dielectrics,a grid-based space management is proposed.Firstly,the deficiencies of the existing method for non-stratified di-electrics is analyzed,and then based on the on-the-fly sampling on eight-octant transition cubes,how to calcu-late equivalent permittivity and how to process complex non-stratified dielectrics by grid-based space man-agement are proposed,to reduce the preprocessing time in random walk algorithm.Several interconnect struc-tures from integrated circuit designs are tested,and the results show that the proposed method can significantly reduce the time of constructing the non-stratified dielectric space management and the preprocessing time while ensuring the accuracy and efficiency.On a test case containing more than seven hundred thousand non-stratified dielectrics,compared with the existing method,the proposed method can accelerate the con-struction time of space management for non-stratified dielectrics by up to 420 times and reduce the preproc-essing runtime from 114s to 30s.Furthermore,for different capacitance extraction application scenarios,how to choose these space management strategies is also provided.

关 键 词：电容提取 随机行走 非分层介质 空间管理 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]