Non quia difficilia sunt non audemus, sed quia non audemus difficilia sunt
Home -> Research -> NB Collectives -> CG Solver
Home
  Publications
  Awards
  Research
    
NB Collectives
      
LibNBC
      NBCBench
      Performance
      CG Solver
      Kernels
      HPL
    MPI Topologies
    MPI Datatypes
    Netgauge
    Network Topologies
    Ethernet BTL eth
    ORCS
    DFSSSP
    Older Projects
    cDAG
    LogGOPSim
    CoMPIler
  Teaching
  BLOG
  Miscellaneous
  Full CV [pdf]






  Events








  Past Events





An Example: 3D Poisson CG Solver

This code uses a conjugate gradient based method to solve a poisson equation in 3-dimensional space. A first version using blocking collective communication was written in collaboration with Peter Gottschling. We added support for non-blocking collective operations with the NBC library by changing only two lines in the source code.

The parallel code uses a standard domain decomposition technique to distribute a discretized 3D space among the processes. The corresponding three-dimensional process grid is built with MPI_Cart_create. Within each iteration, a matrix vector product takes a significant fraction of the execution time which can be accelerated by non-blocking communication. Each process performs three main steps in the calculation:

  1. Multiply the local part of the matrix with available vector elements (which do not require communication).
  2. Communicate border elements with neighbors (using MPI_Alltoallv).
  3. Calculate border part of multiplication (depends on step 2)

Step 1 is independent of all others, which allows to perform this task between step 2 and 3. The non-blocking implementation issues the non-blocking Alltoallv as first operation, calculates the inner part, waits for the Alltoallv to complete and calculates the outer part.

A detailed description and benchmark results are available in "Optimizing a Conjugate Gradient Solver with Non-Blocking Collective Operations" [1].

The timed source code is available: CG Solver Source Code (pre-release) - (23.89 kb)

References

PARCO
[1] T. Hoefler, P. Gottschling, A. Lumsdaine and W. Rehm:
 Optimizing a Conjugate Gradient Solver with Non-Blocking Collective Operations Elsevier Journal of Parallel Computing (PARCO). Vol 33, Nr. 9, pages 624-633, Elsevier, ISSN: 0167-8191, Sep. 2007,

serving: 54.158.86.243:50187© Torsten Hoefler