Large scale circuit simulation exploiting combinatorial multigrid on massively parallel architectures

Abstract

The complexity of modern very large scale integrated circuits renders circuit simulation very essential in the design process, as it is the only feasible way to verify circuit's behaviour prior to manufacturing. The heart of circuit simulation relies on the solution of huge systems resulting after the modelling using Modified Nodal Analysis. Matrices arising in those systems are sparse Symmetric Diagonally Dominant (SDD) matrices, and as a result, iterative methods for efficiently manipulating them are very crucial to the performance of the simulation. In recent years, the emphasis has been placed on preconditioning methods which reduce the number of iterations for solving such systems, while significant advancements have been accomplished in efficient implementations on massively parallel architectures like GPUs. This paper presents a GPU-accelerated simulator, based on the Preconditioned Conjugate Gradient method, which exploits the Combinatorial Multigrid, a reliably efficient SDD solver based on support theory principles, for fast DC and transient analysis of large-scale circuits. Experimental results on IBM power grids, demonstrate speedups up to 4.56x and 5.10x for the PCG method and the CMG preconditioning algorithm, respectively, compared to the optimized CPU implementations. © 2018 IEEE.