A divide-and-conquer algorithm for 3D capacitance extraction [IC modeling]

We present a new algorithm to improve the 3D boundary element method (BEM) for capacitance extraction. We partition large interconnect structures into small sections, set new boundary conditions using the border for each section, solve each section, and then combine the results to derive the capacitance. The target applications are critical nets, clock trees, or packages where 3D accuracy is required. Our algorithm is a significant improvement over the traditional BEMs and their enhancements, such as the "window" method where conductors far away are dropped, and the "shield" method where conductors hidden behind other conductors are dropped. Experimental results show that our algorithm is a magnitude faster than the traditional BEM and the window+shield method, for medium to large structures. The error of the capacitance computed by the new algorithm is within 2% for self capacitance and 7% for coupling capacitance, compared with the results obtained by solving the entire system using BEM. Furthermore, our algorithms gives accurate distributed RC, where none of the previous 3D BEM algorithms and their enhancements can.