GPU friendly fast Poisson solver for structured power grid network analysis

ABSTRACT

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.

REFERENCES

• 1: T. Chen and C. C. Chen, "Efficient large-scale power grid analysis based on preconditioned Krylov-subspace iterative methods", DAC2001 Proceedings, pp. 559--562
• 2: J. N. Kozhaya, S. R. Nassif and F. N. Najm, "A multigrid-like technique for power grid analysis", IEEE Trans. On Computer Aided Design, vol. 21, no. 10, Oct. 2002, pp. 1148--1160
• 3: H. Qian, S. R. Nassif, S. S. Sapatnekar, "Random walks in a supply network", DAC 2003 Proceedings, pp. 93--98
• 4: M. Zhao, R. V. Panda, S. S. Sapatnekar and D. Blaauw, "Hierarchical analysis of power distribution networks", IEEE Trans. On Computer Aided Design, vol. 21, no. 2, Feb. 2002, pp. 159--168
• 5: E. Chiprout, "Fast flip-chip power grid analysis via locality and grid shells", ICCAD 2004 Proceeding, pp. 485--488
• 6: J. Singh, S. S. Sapatnekar, "Topology optimization of structured power/ground networks", ISPD 2004 Proceedings, pp. 16--123.
• 7: J. Shi, Y. Cai, S. X.-D. Tan, J. Fan, X. Hong, "Pattern-Based Iterative Method for Extreme Large Power/Ground Analysis", IEEE Trans. on CAD of Integrated Circuits and Systems vol. 26, no. 4, April 2007, pp. 680--692
• 8: Galoppo N, Govindaraju N K, Henson M, et al. "LU-GPU: Efficient Algorithms for Solving Dense Linear System on Graphics Hardware", ACM/IEEE SC 2005 Proceedings, pp. 3--8.
• 9: Buatois L, Caumon2 G, Lévy B., "Concurrent Number Cruncher: An Efficient Sparse Linear Solver on the GPU", Proceedings of High Performance Computation Conference, 2007, pp. 358--371.
• 10: Kanupriya Gulati, John F. Croix, Sunil P. Khatr, Rahm Shastry, "Fast Circuit Simulation on Graphics Processing Units", ASP-DAC 2009 Proceedings, pp. 403--408
• 11: http://crd.lbl.gov/xiaoye/SuperLU
• 12: Saad. Yousef, "Iterative Methods for Sparse Linear Systems", PWS Publishing Company, 1996.
• 13: Strang G. "Introduction to Applied Mathematics", Wellesley-Cambridge Press, 1986.
• 14: http://en.wikipedia.org/wiki/Matrix_multiplication
• 15: Broyden, C. G., "The Convergence of a Class of Double-Rank Minimization Algorithms", Journal Inst. Math. Applic., Vol. 6, pp. 76--90, 1970.
• 16: http://www.netlib.org/blas/
• 17: http://www.nvidia.com/object/cuda_home.html
• 18: http://developer.nvidia.com/object/matlab_cuda.html
• 19: http://heim.ifi.uio.no/~tom/fastpoissonslides.pdf

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Graphics

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing; Verification; Layout; Simulation

General Terms:
Algorithms, Design, Performance, Verification

Keywords:
GPU, P/G network, fast Poisson solver