GPU-Accelerated Parallel Monte Carlo Analysis of Analog Circuits by Hierarchical Graph-based Solver

In this article, we propose a new parallel matrix solver, which is very amenable for Graphic Process Unit (GPU) based fine-grain massively-threaded parallel computing. The new method is based on the graph-based symbolic analysis technique to generate the computing sequence of determinants in terms of determinant decision diagrams (DDDs). DDD represents very simple data dependence and data parallelism, which can be explored much easier by GPU massively-threaded parallel computing than existing LU-based methods. The new method is based on the hierarchical determinant decision diagrams (HDDDs). Inspired by the inherent data parallelism and simple data dependence in the evaluation process of HDDD, we design GPU-amenable continuous data structures to enable fast memory access and evaluation of massive parallel threads. In addition to parallelism in DDD graph, the new algorithm can naturally explore data independence existing in Monte Carlo and frequency domain analysis. The resulting algorithm is a general-purpose matrix solver suitable for fine-grain massive GPU-based computing for any circuit matrices. Experimental results show that the new evaluation algorithm can achieve about two orders of magnitude speedup over the serial CPU based evaluation and more than 4x speedup over numerical SPICE-based simulation method on some large analog circuits.