Bug in MPI_NEIGHBOR_ALLTOALL--1 or 2 processes in the cyclic Cartesian case

[tonyskjellum]

Problem

For MPI_NEIGHBOR_ALLTOALL|V|W, the behavior for 1 or 2 processes in the Cartesian case is well defined for users and implementors, but neither users nor implementors can easily read the standard. As a result, both mpich and OpenMPI return wrong results in the receive buffer, if a Cartesian dimension is cyclic and the number of processes in that dimension is 1 or 2. Some additional explanations or examples are missing in the MPI standard.

Here a set of 7 slides showing the problem:
153_neighbor_mpi-3_bug_2010-10-03.pdf

Proposal

The following slides show a draft how we may fix this problem:
153_neighbor_mpi-3_bug_2019-10-08.pdf

Changes to the Text

Here is the latest Latex pdf file: mpi-report-issue153-neighbor-errata-2020-01-30-annotated-corr-2020-02-03.pdf

Small update from the reading in Portland:
mpi-report-issue153-neighbor-errata-2020-02-20-annotated.pdf

The pull request is PR153: https://github.com/mpi-forum/mpi-standard/pull/153
The latex source is at https://github.com/RolfRabenseifner/mpi-standard

Impact on Implementations

Both, OpenMPI and mpich and all their derivatives must correct their outcome for 1 or 2 processes in a direction of a Cartesian topology. I tested it only for periodic, but I expect that they have the same bug also for non-perodic Cartesian virtula topologies.

TBD: To check other independent implementations.

Impact on Users

Users will better understand the definition in the MPI standard and therefore also which behavior of an MPI library is correct and which is not.
If a user has implemented a work-around for the wrong behavior of MPI_NEIGHBOR_ALLTOALL
then for the moment, she/he should substitute the MPI_NEIGHBOR_ALLTOALL by a correct usage of MPI_SENDRECV or nonblocking calls as shown in the slides, see above, at least for the case that 1 or more process dimensions are less or equal 2.

References

PR is PR153: https://github.com/mpi-forum/mpi-standard/pull/153
The problem was reported to me by a user: Simone Chiocchetti, University of Trento, ITALY

Continuation, see Issue #320 and PR304 https://github.com/mpi-forum/mpi-standard/pull/304 and PR312 https://github.com/mpi-forum/mpi-standard/pull/312

[omor1]

How is this not well-defined?

In the 1-dimensional cyclic cartesian topology with 2 processes, the negative neighbor of process 0 is 1; the positive neighbor of process 1 is 0. That is, MPI_Cart_shift(comm, 0, -1, &src, &dest) on 0 returns src = dest = 1 and on 1 returns src = dest = 0. With 1 process, it's a bit sillier, but my interpretation is that 0 is its own positive and negative neighbor; that is, rank = src = dest = 0. As far as I know, nothing prevents a process from being its own neighbor. In fact, this is explicitly allowed by the graph topologies.

Given the above topologies, the interaction with the neighborhood collectives seems clear. In the case with 2 processes, each process must send a buffer with 2 * sendcount elements of type sendtype and will receive 2 * recvcount elements of type recvtype. That these happen to be coming from the same process is irrelevant. The implementation must ensure that the send is matched with the correct receive, similarly to the case where there are multiple edges in a (distributed) graph topology.

In the case with 1 process, it must send a buffer with 2 * sendcount elements of type sendtype and will receive 2 * recvcount elements of type recvtype. The call will match with itself—that is, at the end of the call sendbuf[i] == recvbuf[i] for all i (assuming that the element types are the same).

I suppose a note could be added to clarify the interaction, but I don't see how the standard could be interpreted differently—though I suppose I could be assuming something that is not correct.

[RolfRabenseifner]

153_neighbor_mpi-3_bug_2019-10-01.pdf

In the case with 1 process, it must send a buffer with 2 * sendcount elements of type sendtype and will receive 2 * recvcount elements of type recvtype. The call will match with itself—that is, at the end of the call sendbuf[i] == recvbuf[i] for all i (assuming that the element types are the same).

I hope that my two slides clearly show that this is exactly the wrong interpretation of MPI-3.1.
And exactly such interpretations are a clear reason for the need of a clarifying text in MPI-4.0, which may be seen also as an errata, because with such a clarification already included in MPI-3.0, the wrong interpretations in form of wrong MPI libraries would have never existed.

[omor1]

Ah, I see the problem. Yeah, for the case with one process that's a bit confusing. I think my description for two processes was correct though (or at least my mental model—I suppose I didn't explicitly write the exact send/recv logic). Thanks for the visual @RolfRabenseifner!

Clarifying the interaction is important, as I've clearly demonstrated.

[RolfRabenseifner]

Dear Omri, thank you.

Clarifying the interaction is important, as I've clearly demonstrated.

And thank you, that you took it positive that I cited you in my slide.

[dholmes-epcc-ed-ac-uk]

Ah, I see Rolf has given the correction before I could comment.

An additional wrinkle: the topology may not be 1D. This occurs in any dimension with an extent in that dimension of 1 process, irrespective of how many processes there are in total. For example, a 1x10 cartesian topology each process will send 4sendcount elements and receive 4recvcount elements; for all processes, two of the send buffers will be received back by the same process in the buffers representing the opposite direction in the short dimension. In general for an nD cartesian topology, 2n buffers are sent. If m of those n dimensions are loop-back dimensions (with an extent of 1 process), then 2m of those send buffers will be copied locally into 2*m receive buffers each with an index one different to the matching send buffer.

A similar situation occurs for the graph topologies; a process can send and receive to/from itself. The ordering of the buffers is determined by the order in which the topology query function returns them. Thus, the buffer indexes may be different (by one or by more than one) or identical, depending on how the topology was created.

Hopefully I haven't just provided @RolfRabenseifner with another example for his slides :)

[RolfRabenseifner]

Yes, of course, my slide shows one direction. The problem is the same for all directions d=0..ndims-1.
As far as I was reported, the OpenMPI library is doing the wrong sequence of data in both cases, dims[d]==1 and dims[d]==2.

[dholmes-epcc-ed-ac-uk]

@RolfRabenseifner may I also suggest that the worked example, in particular the commented "instead of ..." code in Figure 7.3, be re-worked so that it is correct in the 1-process case?

Currently, that commented code would send 2 messages to itself using the same tag but it will deal with each direction in turn, so the matching rules (in particular the non-overtaking rule) will force the wrong (unintended) matching order. The result will be what Open MPI is apparently reported to be doing, not what is defined to be correct by the section 7.6 introduction text. The correction would be use a different tag for the send-back and send-forward messages to force the correct matching behaviour. It is not even that simple though - a multi-dimensional cartesian topology with only 1 process in total would require different tags for every message sent to guarantee the correct matching behaviour.

[RolfRabenseifner]

Bad news: OpenMPI and Cray-mpich have the same bug, i.e., Cartesian periodic MPI_NEIGHBOR_ALLTOALL does not work correctly according to the MPI-3.1 specification in the directions where the number of processes is only 1 or 2. Thanks to Christoph Niethammer who testet it now: openmpi/4.0.1-gnu-8.3.0 and cray-mpich/7.7.6

Here the test: It is EPCC's ring example:

• sending myrank around the ring in positiv direction
• it is 1-dimensional
• on n processes it executes the loop n times,
• i.e., each rank is going through all processes along the ring.
• It sums up all the ranks that are coming along the ring.
• The result is therefore on all processes identical:
  0 + 1 + 2 + ... + (n-1) = n * (n-1) / 2
  I used it with two modifications:
• sending 100+myrank around a ring
• therefore, the result is: n100 + n(n-1) / 2
• Instead of ISEND+RECV+WAIT, it calls MPI_NEIGHBOR_ALLTOALL
• It ignores the communication in negativ direction,
  but the send buffer for negative direction is initialized with -1000-my_rank

If MPI_NEGHBOR_ALLTOALL works correctly, then the results should be

• on 4 processes: 4 times sum=406
• on 3 processes: 3 times sum=303
• on 2 processes: 2 times sum=201
• on 1 processes: 1 times sum=100

On both, openmpi/4.0.1-gnu-8.3.0 and cray-mpich/7.7.6, the result for 3 and 4 processes is correct,
but

• with 2 processes:
  PE1: Sum = -2000
  PE0: Sum = -2002
• with 1 process:
  PE0: Sum = -1000

These results reflect, that the messages are received at the wrong index in the receive buffer.

ring_neighbor_alltoall_TEST.c.txt

[omor1]

I think that there's a related issue wherein MPI does not specify how incoming and outgoing edges are matched in (distributed) graph topologies. The behavior used by some (most?) MPI implementations (where the i-th outgoing edge matches with the i-th incoming edge) is due to the ordering requirements of sending and receiving with the same tag and is apparently an artifact of the implementation rather than a conscious decision on part of the implementors. In general, the behavior of both self-loops and edge multiplicity is underspecified in MPI.

This means that creating a topology that has the same behavior as a cartesian topology for the neighborhood collective functions using the (distributed) graph topology constructors is impossible. In this sense, it is related to #87 (the initial impetus for that was noticing that topologies with null process neighbors are not explicitly allowed).

[RolfRabenseifner]

In the following file, you can clearly see, that this problem with periodic virtual Cartesian process topologies is not related to any other problem with virtual graph topologies.
153_neighbor_mpi-3_bug_2019-10-03.pdf