[Mpi3-rma] Use cases for RMA

[Torsten Hoefler]

Hello Bill,

one more example, which would not work too well in MPI-2.2 is the
implementation of parallel graph algorithms. With regards to the
efficient parallelization, there are some easy ones (PageRank, Connected
Components etc.), but there are also much more demanding algorithms such
as SSSP (e.g., \Delta stepping)or Betweenness Centrality. Those
algorithms commonly build upon level-wise graph traversals (BFS) which
needs remote queue updates.

A common strategy to parallelize BFS is to distribute the graph vertices
(this has its own load-balancing issues) and have a distributed queue
with local pop(), remote push(), and global ifempty() semantics. In this
model, computation (the little there is) is pushed towards the owner of
the vertex, i.e., into the queue of the owning process.

This is commonly implemented with a polling active-message-like layer on
top of MPI (see Parallel Boost Graph Library) and pseudo-code can be
found in http://www.unixer.de/publications/img/hoefler-dsde-protocols.pdf
(Algorithm 3, I have C++ source code if anybody is interested). However,
this obviously causes a lot of unnecessary overhead at the receive side
(polling and unnecessary queue matching, and we also don't need MPI's
ordering semantics). An active message (or remote procedure call, or an
MPI_Accumulate with an operation that conditionally pushes on a remote
queue) could eliminate those overheads and one could perform the DSDE
steps (conditional insert into queue) in Algorithm 5 much more
efficient.

It would be even better if MPI would offer us some termination-detection
mechanism in case we do not need level-wise traversals (some algorithms
allow that, e.g., label-correcting SSSPs).

One might think that remote locks and updates could be used to protect
and access the queue, however, those operations introduce a large amount
of lock traffic and effectively multiplies the latency. Many such
(sparse) graph algorithms are latency-bound and one would like to update
remote queues as rapidly as possible.

All the Best,
  Torsten

-- 
 bash$ :(){ :|:&};: --------------------- http://www.unixer.de/ -----
Torsten Hoefler         | Research Associate
Blue Waters Directorate | University of Illinois
1205 W Clark Street     | Urbana, IL, 61801
NCSA Building           | +01 (217) 244-7736