A divide-and-conquer algorithm for 3-D capacitance extraction

We present a divide-and-conquer algorithm to improve the three-dimensional (3-D) boundary element method (BEM) for capacitance extraction. We divide 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 application is critical nets, clock trees, or packages where 3-D 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 3-D BEM algorithms and their enhancements can.