Parallel performance of hierarchical multipole algorithms for inductance extraction Academic Article uri icon

abstract

  • Parasitic extraction techniques are used to estimate signal delay in VLSI chips. Inductance extraction is a critical component of the parasitic extraction process in which on-chip inductive effects are estimated with high accuracy. In earlier work [1], we described a parallel software package for inductance extraction called ParIS, which uses a novel preconditioned iterative method to solve the dense, complex linear system of equations arising in these problems. The most computationally challenging task in ParIS involves computing dense matrix-vector products efficiently via hierarchical multipole-based approximation techniques. This paper presents a comparative study of two such techniques: a hierarchical algorithm called Hierarchical Multipole Method (HMM) and the well-known Fast Multipole Method (FMM). We investigate the performance of parallel MPI-based implementations of these algorithms on a Linux cluster. We analyze the impact of various algorithmic parameters and identify regimes where HMM is expected to outperform FMM on uniprocessor as well as multiprocessor platforms. Springer-Verlag 2004.

published proceedings

  • HIGH PERFORMANCE COMPUTING - HIPC 2004

author list (cited authors)

  • Mahawar, H., Sarin, V., & Grama, A.

citation count

  • 1

complete list of authors

  • Mahawar, H||Sarin, V||Grama, A

publication date

  • December 2004