A Parallel Algorithm for Chip-Level 3D Parasitic Capacitance Extraction

With prevalence of multi-core CPU and distributed clusters,parallel computation is widely applied to scientific research as well as engineering practices,for solving complex numerical simulation problem.A parallel computational approach to the capacitance extraction is proposed, which is based on 3D hierarchical block boundary element method (HBBEM).It applies the two-way overlap and combination idea by dividing the chip into four kinds of the"windows"with different sizes, and then uses the variable-length mixed dynamic queue to schedule the windows to different processes via a combination of static and dynamic task-scheduling methods.It also adopts techniques to increase the efficiency of parallel computation in summation of sparse matrices and reduce communication cost between processes,and to gain efficient workload balance and high speedup.Experimental results on distributed clusters implemented by message passing interface (MPI) have validated the proposed method.