Volume 7 Number 12 (Dec. 2012)
Home > Archive > 2012 > Volume 7 Number 12 (Dec. 2012) >
JSW 2012 Vol.7(12): 2695-2702 ISSN: 1796-217X
doi: 10.4304//jsw.7.12.2695-2702

An Improved Implementation of Preconditioned Conjugate Gradient Method on GPU

Yechen Gui and Guijuan Zhang
Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China

Abstract—An improved implementation of the Preconditioned Conjugate Gradient method on GPU using CUDA (Compute Unified Device Architecture) is proposed. It aims to solving the Poisson equation arising in liquid animation with high efficiency. We consider the features of the linear system obtained from the Poisson equation and propose an optimization method to solve it. First, a novel storage format called mDIA (modified diagonal storage format) is presented to improve the efficiency of the Sparse Matrix-Vector product (SpMV) operation. Second, a parallel Jacobi iterative method is proposed when using the Incomplete Cholesky preconditioner to explore inherent parallelism. Third, CUDA streams are also introduced to overlap computations among separate streams. The proposed optimization technique is embedded into our GPU based PCG algorithm. Results on Geforce G100 show that our SpMV kernel yields an improvement of nearly 100% for large sparse matrix with more than 30, 0000 rows. Also, a speedup of more than 7 is obtained for PCG method, making the real-time physics engine possible.

Index Terms—CUDA, PCG, Incomplete Cholesky preconditioner, SpMV, Poisson equation

[PDF]

Cite: Yechen Gui and Guijuan Zhang, "An Improved Implementation of Preconditioned Conjugate Gradient Method on GPU," Journal of Software vol. 7, no. 12, pp. 2695-2702, 2012.

General Information

ISSN: 1796-217X (Online)
Frequency: Monthly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Aug 21, 2019 News!

    Papers published in JSW Vol 14, No 1- Vol 14 No 8 have been indexed by DBLP     [Click]

  • Jun 25, 2019 News!

    Vol.13, No.9 has been indexed by EI (Inspec).   [Click]

  • Aug 01, 2018 News!

    [CFP] 2019 the annual meeting of JSW Editorial Board, ICCSM 2019, will be held in Barcelona, Spain, July 14-16, 2019.   [Click]

  • Jul 10, 2019 News!

    Vol 14, No.8 has been published with online version 4 original aritcles from 2 countries are published in this issue.    [Click]

  • Sep 12, 2019 News!

    Vol 14, No 10 has been published with online version 4 original aritcles from 2 countries are published in this issue      [Click]