CAPLET: A Parallelized Boundary Element Method for VLSI Capacitance Extraction with Instantiable Basis Functions
- Category: Circuits & Systems
- Tags: luca daniel, yu-chung hsiao
Print This Page
Download as PDFTraditional interconnect capacitance extraction tools usually employ 2D scanning and table look-up methods for fast extraction. For some structures, e.g., partially overlapping wires and comb capacitors, 2D scanning methods fail to generate accurate results (i.e. within 5% error), therefore using 3D field solvers becomes necessary despite the much slower performance. Accelerated field solvers have been proposed, such as FastCap [1] and Precorrected FFT [2] whose accelerations are effective only for large, semi-global structures of hundreds of wires. More importantly, [3] and [4] demonstrated that such two acceleration methods are not efficiently parallelizable, showing rapid degradation of parallel efficiency with the number of parallel nodes (40% to 60% at eight nodes).
We propose an efficiently parallelizable acceleration method for local, small-to-medium structures of tens of wires, targeting errors within 5%. We adopt our instantiable basis functions [5] as a compact charge distribution representation in the boundary element method. Our instantiable basis functions are usually 30 times more compact than traditional piecewise constant (PWC) basis functions [1] [2] [3] [4] in terms of required basis functions for the same capacitance accuracy (Figure 1). Such compactness not only accelerates the single-node execution (six times in Figure 2.a) but also greatly improves the parallel efficiency (Figure 2.b) by redistributing the computation between the hard parallelizable system solving part (from 90% of total execution to less than 5%) and the embarrassingly parallelizable matrix filling part (from 10% to more than 95%) [6] . We will release the complete tool set, from input gds2 layout files to capacitance matrices, in the public domain.
-
- Figure 1: Charge distribution solutions represented by (a) 572 PWC basis functions and (b) 17 instantiable basis functions, respectively. Capacitance errors for both cases are 2% w.r.t. a reference value extracted by the standard BEM with fine PWC discretization.
-
- Figure 2: (a) Industrial example. The algorithm is 6x faster than FASTCAP [1] for single-threaded execution at same accuracy (2.8% error w.r.t. a reference value). (b) 24×24 bus example. (c) Parallel efficiency vs. algorithms [3] and [4] .
- K. Nabors and J. White, “Fast-Cap: A multipole-accelerated 3-D capacitance extraction program,” IEEE Transactions on Computer-Aided Design, vol. 10, no. 10, pp. 1447-1459, Nov. 1991. [↩] [↩] [↩]
- J. R. Phillips and J. K. White, “A precorrected-FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Transaction on Computer-Aided Design, vol. 16, no. 10, pp. 059-1072, Oct. 1997. [↩] [↩]
- Y. Yuan and P. Banerjee, “A parallel implementation of a fast multipole-based 3-d capacitance extraction program on distributed memory multicomputers,” Journal of Parallel and Distributed Computing, vol. 61, no. 12, pp. 1751–1774, 2001. [↩] [↩] [↩]
- N. R. Aluru, V. B. Nadkarni, and J. White, “A parallel precorrected FFT based capacitance extraction program for signal integrity analysis,” in Proceedings of the 33rd Annual Design Automation Conference, 1996, pp. 363-366. [↩] [↩] [↩]
- Y.-C. Hsiao, T. El-Moselhy, and L. Daniel, “Efficient capacitance solver for 3d interconnect based on template-instantiated basis functions,” IEEE 18th Conference on Electrical Performance of Electronic Packaging and Systems, 2009, pp. 179–182. [↩]
- Y.-C. Hsiao and L. Daniel, “A highly scalable parallel boundary element method for capacitance extraction,” Proceedings of the 48th Annual Design Automation Conference, DAC 2011. [↩]