A Combinatorial Multigrid Preconditioned Iterative Method for Large Scale Circuit Simulation on GPU s

Abstract

Efficient large scale circuit simulation is among the most challenging problems facing the EDA industry today, since it is the only feasible way to verify a circuit's behaviour prior to manufacturing. In recent years, the emphasis has been placed on preconditioning methods which reduce the number of iterations for solving large Symmetric Diagonally Dominant systems resulting after the Modified Nodal Analysis. This paper presents a GPU-accelerated Preconditioned Conjugate Gradient (PCG) iterative method preconditioned by the Combinatorial Multigrid (CMG) for fast DC and transient analysis of large-scale linear circuits. Experimental results on IBM industrial power grids demonstrate speedups up to 4.69x and 4.50x for the PCG method and the CMG preconditioning algorithm, respectively, over the optimized CPU implementations. © 2018 IEEE.