Efficient Techniques for Handling Large Nets in Capacitance Extraction Based on Floating Random Walk

An approach for fast generation of virtual Gaussian surface in floating random walk algorithm is proposed,which resolves the difficulty of performing capacitance extraction on large wire nets including over one hundred thousand conductor blocks.Firstly,computational complexity of the existing virtual Gaussian surface sampling technique is analyzed.Based on it,techniques are proposed to improve the distance calculation among conductor blocks and the intersection calculation of block Gaussian surfaces.The techniques are based on space management and reduce the computational time for generating the Gaussian surfaces,achieving better performance than the approach based on parallel computing.The efficiency and correctness of the proposed approach is verified with the experiments carried out on a server with 32 cores.The experimental results show that,for a large structure including about one million conductor blocks the proposed approach accelerates generating the Gaussian surface for 372 times,which is much better than the acceleration brought by paralleling computing.