高级检索

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

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

  • 摘要: 为了解决包含大量非分层介质的随机行走电容提取算法预处理时间过长的问题,提出一种优化算法.本文算法一共有2步:首先基于八分块立方体即时采样技术,提出处理复杂非分层介质的等效介电常数计算方法;然后基于网格的空间管理技术,减少随机行走电容提取的预处理时间.针对不同的电容提取应用场景,还提供了选择不同非分层介质空间管理策略的建议.在多个来自集成电路设计版图的互连结构上的实验结果表明,所提算法在保证电容提取精度与随机行走运行效率的同时,显著地加快了非分层介质空间管理构造以及随机行走算法的预处理时间;在含有超过70万非分层介质的测例上,与现有算法相比,该算法使非分层介质的空间管理构造时间最多加速420倍,并使整个预处理时间从114s减少到30s.

     

    Abstract: 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 dielectrics is analyzed, and then based on the on-the-fly sampling on eight-octant transition cubes, how to calculate equivalent permittivity and how to process complex non-stratified dielectrics by grid-based space management are proposed, to reduce the preprocessing time in random walk algorithm. Several interconnect structures 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 construction time of space management for non-stratified dielectrics by up to 420 times and reduce the preprocessing runtime from 114s to 30s. Furthermore, for different capacitance extraction application scenarios, how to choose these space management strategies is also provided.

     

/

返回文章
返回