{"id":5515,"date":"2012-07-18T22:28:21","date_gmt":"2012-07-18T22:28:21","guid":{"rendered":"https:\/\/mtlsites.mit.edu\/annual_reports\/2012\/?p=5515"},"modified":"2012-08-14T14:54:09","modified_gmt":"2012-08-14T14:54:09","slug":"caplet-a-parallelized-boundary-element-method-for-vlsi-capacitance-extraction-with-instantiable-basis-functions","status":"publish","type":"post","link":"https:\/\/mtlsites.mit.edu\/annual_reports\/2012\/caplet-a-parallelized-boundary-element-method-for-vlsi-capacitance-extraction-with-instantiable-basis-functions\/","title":{"rendered":"CAPLET: A Parallelized Boundary Element Method for VLSI Capacitance Extraction with Instantiable Basis Functions"},"content":{"rendered":"

Traditional interconnect capacitance extraction tools usually employ 2D scanning and table look-up methods for fast extraction.\u00a0 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<\/a>] <\/sup> and Precorrected FFT [2<\/a>] <\/sup> whose accelerations are effective only for large, semi-global structures of hundreds of wires. More importantly, [3<\/a>] <\/sup> and [4<\/a>] <\/sup> 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).<\/p>\n

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<\/a>] <\/sup> 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<\/a>] <\/sup> [2<\/a>] <\/sup> [3<\/a>] <\/sup> [4<\/a>] <\/sup> 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<\/a>] <\/sup>. We will release the complete tool set, from input gds2 layout files to capacitance matrices, in the public domain.<\/p>\n\n\t\t