CAPLET: Field-solver Accurate Real-time Capacitance Extraction Toolkit using Instantiable Basis Functions
- Category: Circuits & Systems
- Tags: luca daniel, yu-chung hsiao
Print This Page
Download as PDFTraditional capacitance extraction for VLSI interconnects usually adopts 2D scanning and table look-up methods for fast extraction at acceptable accuracy. However, for certain full-3D structures, such as partially overlapping wires and comb capacitors, 2D scanning methods fail to generate accurate results (within 5% errors). Therefore, using 3D field solvers becomes necessary despite the much slower performance. Some accelerated capacitance extraction field solvers have been proposed in the past decades, e.g., FASTCAP[1] and pre-corrected FFT [2], whose accelerations are effective only for large, semi-global structures of hundreds of wires. More importantly,[3] and[4] have demonstrated that the two acceleration methods are not efficiently parallelizable, showing rapid degradation of parallel efficiency with the number of cores (40% to 60% at eight cores).
This work targets the sub-second extraction performance within 5% errors for small-to-medium-sized structures of tens of wires. We adopt our instantiable basis functions (Figure 1(a)) developed in [5] as compact representations of charge distribution in a boundary element method. Such compactness both provides acceleration in serial execution (6x faster than FASTCAP for the NAND gate in Figure 1(b)), and achieves linear scalability of parallel efficiency (Figure 2). The key idea is that using such compact representations reduces the parallelization bottleneck, system solving computation, for from the original 90% of total computation to less than 5%. Hence the embarrassingly parallelizable part, filling the system matrix, is now dominant (from 10% of total computation to more than 95%)[6]. In four-core parallel execution, we achieve a 38-ms extraction time for an inverter and 190-ms for a NAND gate. Our toolkit can directly handle GDS2 layouts to generate capacitance matrices and 3D visualization (Figure 1(b)). Our code is available in the public domain at http://www.rle.mit.edu/cpg/codes/caplet/index.html.
-
- Figure 1: (a) Charge distribution represented by 572 piecewise constant basis functions (left) and 17 instantiable basis functions (right). Capacitance errors for both cases are 2% w.r.t. a reference capacitance value extracted by standard BEM with fine discretization. (b) CAPLET GUI and NAND gate visualization.
-
- Figure 2: A 24×24 bus example (top) and its parallel efficiency comparison (bottom) with the algorithms in [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, 61(12): 1751–1774, 2001. [↩]
- N. R. Aluru, V. B. Nadkarni, and J. White, “A parallel precorrected fft based capacitance extraction program for signal integrity analysis,” Proceedings of the 33rd annual Design Automation Conference, DAC ’96, New York, NY, USA, 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, EPEPS ’09. pp. 179–182, Oct. 2009. [↩]
- Y.-C. Hsiao and L. Daniel, “A highly scalable parallel boundary element method for capacitance extraction,” in Proceedings of the 48th Annual Design Automation Conference, DAC 2011, San Diego, CA, USA, pp. 552-557. [↩]