Life would be so much easier if only we had the source code...
Home -> Research -> NB Collectives -> CG Solver
NB Collectives
      CG Solver
    MPI Topologies
    MPI Datatypes
    Network Topologies
    Ethernet BTL eth
    Older Projects
  Full CV [pdf]


  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)


[1] Torsten Hoefler, P. Gottschling, Andrew Lumsdaine and Wolfgang 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:© Torsten Hoefler