Association for Computing Machinery
It is unknown how to include stochastic process variation into Fast-Multipole-Method (FMM) for a full chip capacitance extraction. This paper presents a parallel FMM extraction using stochastic polynomial expanded geometrical moments. It utilizes multiprocessors to evaluate in parallel for the stochastic potential interaction and it's Matrix-Vector Product (MVP) with charge. Moreover, a Generalized Minimal RESidual (GMRES) method with deflation is modified to incrementally consider the nominal value and the variance. The overall extraction flow is called piCAP. Experiments show that the parallel MVP in piCAP is up to 3X faster than the serial MVP and the incremental GMRES in pi-CAP is up to 15X faster than non-incremental GMRES methods.