GPU friendly fast Poisson solver for structured power grid network analysis
EDA Lab, Computer Science Department, Tsinghua University, PRC
46th ACM/IEEE Design Automation Conference, 2009. DAC ’09. p.178-183
@conference{shi2009gpu,
title={GPU friendly fast Poisson solver for structured power grid network analysis},
author={Shi, J. and Cai, Y. and Hou, W. and Ma, L. and Tan, S.X.D. and Ho, P.H. and Wang, X.},
booktitle={Design Automation Conference, 2009. DAC’09. 46th ACM/IEEE},
pages={178–183},
issn={0738-100X},
year={2009},
organization={IEEE}
}
In this paper, we propose a novel simulation algorithm for large scale structured power grid networks. The new method formulates the traditional linear system as a special two-dimension Poisson equation and solves it using an analytical expressions based on FFT technique. The computation complexity of the new algorithm is O(NlgN), which is much smaller than the traditional solver’s complexity O(N^1.5) for sparse matrices, such as the SuperLU solver and the PCG solver. Also, due to the special formulation, graphic process unit (GPU) can be explored to further speed up the algorithm. Experimental results show that the new algorithm is stable and can achieve 100X speed up on GPU over the widely used SuperLU solver with very little memory footprint.
December 29, 2010 by hgpu
