Circuit simulation software based on SPICE
(such as ngspice
) uses Newton-Raphson method to solve non-linear system of equations which model circuits containing non-linear elements such as diodes or MOSFET transistors. In each iteration of Newton-method, most of the time is spent on the following two parts:
- device model evaluation: load the sparse matrix $A$ and rhs $b$ of $Ax=b$ with appropriate values according to the current operating point of the circuit.
- matrix solving: solve $Ax=b$
To speed up the simulation, efforts has been put in parallelizing both parts above, as the literature shows.
Some days a ago, an idea came across to me to speed up the simulation in a coarse-grained fashion, but I am not sure whether or not this is a viable idea or if there were studies/implementations of it already. Let me explain below what's in my mind, and please give advice or indications. Many thanks!
The idea is simple (based on the assumption that many computational resource are available): at each iteration, we try multiple ($N$) candidate solutions in parallel, i.e., $N$ version of $Ax=b$ is loaded/solved in parallel; if none converges, we choose the "best" one from $N$ solutions (somehow, e.g., simply using Euclidean distance betw. candidate and solution as criteria) for the next iteration. again, the next iteration generates $N$ candidate solutions based on the chosen one from the previous iteration (for example, simply choose different step sizes in the direction of $\delta x$), and carry on the process, until it converges or max iterations reached.
The hope is that:
- as we try $N$ candidates at each iteration, the number of iteration to reach convergence will most likely to decrease, thus speed up simulation.
- as we try more candidates, the solution may be a little bit more "global" then local solutions obtained from Newton method.
The following briefly depict the idea above: