一种基于浮动随机游走的寄生电容提取方法及计算机可读存储介质与流程

本发明涉及集成电路电子设计自动化，尤其是指一种基于浮动随机游走的寄生电容提取方法及计算机可读存储介质。

背景技术：

1、在超大规模集成电路芯片互连寄生参数提取中，浮动随机游走（floating randomwalk, frw）算法因其对复杂三维几何结构的适应性和统计无偏性而被广泛应用。该算法通过模拟粒子在介质区域中的随机运动来求解拉普拉斯方程，进而计算导体间的耦合电容值。

2、现有frw方法通常全程采用单一类型的转移几何体（如立方体或球体）进行跳跃采样。然而，单一转移几何体难以同时满足远场区域快速空间扩散与近场区域高效边界终止的需求：若采用各向同性的大尺度几何体（如球体），虽有利于远场快速覆盖空间，但在接近导体表面时因缺乏面约束而导致终止效率低下；若采用具有面约束的多面体几何体（如立方体），虽能在近场利用自适应边界条件实现高效终止，但在远场受限于几何形状的方向性，空间扩散速率较慢。

3、这种单一几何体在空间覆盖能力与边界终止效率上的固有矛盾，导致现有frw算法在保证提取精度的前提下，难以进一步减少游走步数和总计算时间。

技术实现思路

1、为此，本发明针对现有技术存在的单一转移几何体在空间覆盖能力与边界终止效率上无法兼顾的问题，本发明通过一种基于浮动随机游走的寄生电容提取方法，根据游走粒子到最近导体的距离动态选择最大跳跃距离相匹配的不同转移几何体，实现在保证统计无偏性的前提下显著减少游走步数并提升提取效率。

2、为解决上述技术问题，本发明提供了一种基于浮动随机游走的寄生电容提取方法，包括：获取目标芯片的导体分布信息；在浮动随机游走的当前游走步骤中，获取当前游走粒子到最近导体的目标距离；响应于所述目标距离大于预设阈值，选择第一转移几何体对所述当前游走粒子执行跳跃采样；响应于所述目标距离小于或等于所述预设阈值，选择第二转移几何体对所述当前游走粒子执行跳跃采样；其中，所述第一转移几何体的最大跳跃距离与所述第二转移几何体的最大跳跃距离相匹配；基于游走路径的终止状态和对应的路径权重，确定所述目标芯片的寄生电容值。

3、上述方案通过在单次游走过程中根据粒子所处空间位置动态切换转移几何体，使远离导体的远场区域采用侧重各向同性大尺度扩散的第一转移几何体，靠近导体的近场区域切换为侧重边界约束与面采样终止的第二转移几何体，并通过匹配两者的最大跳跃距离消除切换边界处的效率劣化，从而在不牺牲精度的前提下最大化每步的均方位移，显著减少游走步数和总计算时间。

4、在本发明的一个实施例中，所述第一转移几何体为各向同性几何体，所述第二转移几何体为具有面约束的多面体几何体；所述预设阈值基于所述第一转移几何体的基础尺寸参数确定。

5、此实施方式明确了两种转移几何体在物理特性上的互补性：各向同性几何体在任意方向上具有相同的跳跃能力，适合在无导体约束的远场区域快速探索空间；具有面约束的多面体几何体则能利用其平面边界与导体表面的几何对齐特性，在近场区域通过调和测度采样实现高效吸收。预设阈值与第一转移几何体基础尺寸参数的关联，确保了切换时机与几何体自身空间覆盖能力的内在一致性。

6、在本发明的一个实施例中，所述第一转移几何体为球体，所述第二转移几何体为立方体；所述第一转移几何体的最大跳跃距离为所述球体的半径，所述第二转移几何体的最大跳跃距离为所述立方体的中心至顶点的距离；所述球体的半径与所述立方体的中心至顶点的距离相等或处于同一数量级。

7、此实施方式将球体与立方体作为优选的几何体组合，并通过限定球体半径与立方体中心至顶点距离（即半对角线长度）的匹配关系，解决了因几何体尺度失衡导致的切换边界效率劣化问题。当两者最大跳跃距离相等或处于同一量级时，粒子在切换边界处无论使用哪种几何体都具有可比的空间覆盖能力，避免了因某一侧几何体覆盖能力显著弱于另一侧而导致的混合模式整体性能退化。

8、在本发明的一个实施例中，所述第一转移几何体为球体，选择第一转移几何体对所述当前游走粒子执行跳跃采样，包括：在所述当前游走步骤中，从预计算的方向向量查找表中通过随机索引获取三维方向向量，所述方向向量查找表包含多个均匀分布在单位球面上的方向向量；基于所述当前游走粒子的当前位置、所述球体的半径以及所述三维方向向量，更新所述当前游走粒子的位置。

9、此实施方式通过预计算方向向量查找表消除了球面均匀采样中三角函数的实时计算开销。在执行阶段仅需一次随机整数生成和数组索引操作即可获取跳跃方向，将方向采样的时间复杂度降至o(1)，使得球体跳跃的单步耗时与立方体跳跃持平，确保混合模式的性能收益完全来自于步数减少而非单步速度差异。

10、在本发明的一个实施例中，选择第二转移几何体对所述当前游走粒子执行跳跃采样，包括：获取所述当前游走粒子在所述多面体几何体的各个轴向上受导体约束的约束状态；通过位掩码检测受约束的轴向数量，并根据所述轴向数量从多个格林函数子表中选择目标格林函数子表；基于所述目标格林函数子表对所述多面体几何体的表面进行采样，以确定所述当前游走粒子的下一跳位置。

11、此实施方式通过位掩码机制自动检测多面体各轴向的导体约束状态，并据此选择对应的格林函数子表（如全立方体、半立方体、四分之一立方体等）进行面采样概率修正。该机制确保在近场区域，转移几何体的采样分布始终符合吸收边界条件下的调和测度，使粒子能够以最高概率命中导体表面，最大化近场终止效率。

12、在本发明的一个实施例中，响应于所述目标距离大于预设阈值，选择第一转移几何体对所述当前游走粒子执行跳跃采样，包括：响应于所述目标距离大于所述预设阈值，将所述目标距离作为预计算半径参数传入所述第一转移几何体的转移函数；通过所述转移函数基于所述预计算半径参数执行跳跃，以跳过所述第一转移几何体内部的重复距离查询。

13、此实施方式利用距离预判结果消除混合模式中远场步的冗余计算。由于判定使用第一转移几何体时已计算出目标距离，将其直接作为预计算半径参数传入转移函数，可使第一转移几何体跳过内部再次遍历导体以计算最近距离的步骤，将每步的导体遍历次数从两次降至一次，进一步降低单步时间开销。

14、在本发明的一个实施例中，在所述浮动随机游走的所述当前游走步骤之前，所述方法还包括：在源导体表面按面积加权随机采样游走起点；采用泊松核半球边界估计器对所述游走起点执行第一跳，将所述当前游走粒子从所述源导体表面投射至介质区域，并计算对应的泊松权重系数。

15、此实施方式通过面积加权采样和泊松核半球边界估计器处理游走起点的第一跳，确保了从导体表面到介质区域的初始投射符合静电场边值问题的数学要求，为后续随机游走的统计无偏性奠定基础。

16、在本发明的一个实施例中，基于游走路径的终止状态和对应的路径权重，确定所述目标芯片的寄生电容值，包括：响应于所述当前游走粒子被目标导体吸收、超出仿真域边界或达到最大步数，终止当前游走路径；基于浮动随机游走电容公式计算源导体到所述目标导体的耦合电容值，所述浮动随机游走电容公式为：

17、；

18、其中，为源导体到目标导体的耦合电容值，为第次游走的路径权重，为有效介电常数，为源导体的表面积，为总游走次数，为第一跳半径，为介质权重，为指示当前游走路径是否命中目标导体的指示函数。

19、此实施方式明确了游走终止条件和电容计算的数学表达，其中路径权重综合了第一跳半径、介质权重和命中指示，确保了最终电容值的统计期望收敛于真实解。

20、在本发明的一个实施例中，选择第一转移几何体或第二转移几何体对所述当前游走粒子执行跳跃采样，包括：在每一步游走中，基于所述当前游走粒子到周围导体的实时距离，动态构建所述第一转移几何体或所述第二转移几何体的尺寸；在动态构建尺寸时，强制令所述第一转移几何体的设定尺寸等于当前受约束的所述第二转移几何体的最大空间覆盖尺度，以实时保持两者的最大跳跃距离相匹配。

21、此实施方式针对实际frw算法中转移几何体尺寸随粒子位置动态变化的场景，提出了实时尺寸对齐策略。在每一步动态构建几何体时，强制令第一转移几何体的设定尺寸（如球体半径）等于当前受约束的第二转移几何体的最大空间覆盖尺度（如立方体在当前约束下的中心至顶点距离），从而在动态尺寸模式下依然保持两者最大跳跃距离的实时匹配，确保混合模式在整个游走过程中始终维持最优的空间覆盖效率。

22、此外，本技术还提供了一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现如上述方案所述的方法。

23、本发明的上述基于浮动随机游走的寄生电容提取方法，通过根据游走粒子到最近导体的目标距离动态选择第一转移几何体或第二转移几何体，并使两者的最大跳跃距离相匹配，实现了远场快速空间扩散与近场高效边界终止的平滑衔接。其原理在于：在远场区域，各向同性的第一转移几何体能够以大尺度步长快速覆盖无导体约束的空间，减少无效的小步探索；在近场区域，具有面约束的第二转移几何体能够利用其几何边界与导体表面的对齐特性，通过调和测度采样引导粒子高效命中导体；而两者最大跳跃距离的匹配则消除了切换边界处因空间覆盖能力不对等导致的效率劣化，确保动态切换的实际收益得以充分发挥。由此，在保证电容提取统计无偏性的前提下，显著减少了平均游走步数和总计算时间，提升了芯片寄生电容提取的整体效率。