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

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 114 s to 30 s. Furthermore, for different capacitance extraction application scenarios, how to choose these space management strategies is also provided.