Question: MPI_Dims_create - is 'as close to each other as possible' a requirement?

[jeffhammond]

Regarding MPI_Dims_create, is the following a required semantic or just a quality of implementation issue?

The dimensions are set to be as close to each other as possible, using an appropriate divisibility algorithm.

When I run the MPICH test of this function with Open-MPI, it fails because 6x12 is not the ideal factorization of 72. I can't tell if this is an incorrect implementation or not?

https://github.com/pmodels/mpich/blob/main/test/mpi/topo/dims5.c

~/mukautuva/mpich-testsuite-4.1/topo$ ./dims5
soname = /usr/lib/x86_64-linux-gnu/libmpi.so
Authorization required, but no authorization protocol specified
Authorization required, but no authorization protocol specified
Authorization required, but no authorization protocol specified
Open-MPI
72 in 2d: 12 x 6 != 9 x 8
180 in 2d: 18 x 10 != 15 x 12
240 in 2d: 20 x 12 != 16 x 15
288 in 2d: 24 x 12 != 18 x 16
336 in 2d: 24 x 14 != 21 x 16
420 in 2d: 28 x 15 != 21 x 20
450 in 2d: 30 x 15 != 25 x 18
504 in 2d: 28 x 18 != 24 x 21
540 in 2d: 30 x 18 != 27 x 20
 Found 74352 errors

[RolfRabenseifner]

This is definitely a bug of Open-MPI (or at least terrible quality far beyond Jespers paper from 2015!
The solution exists (see paper from Jesper) and I wanted to fix this all but the forum decided not to accept by having too many abstains.
See #120
and its pdf: https://github.com/mpi-forum/mpi-issues/files/5086553/mpi-report-issue120-topol-2020-08-17-annotated-pages334-335.pdf

Especially page 334, lines 28-38 answers your question.
72 = 12x6 is not optimal, because the suim 12+6 is 18,
whereas 72=9x8 is optimal, because 9+8=17
and there is no other factorization with smaller sum, see references [51] and from Jesper [65] on pages 944 and 945.

[RolfRabenseifner]

@jeffhammond If you want, I can bring this AtoI + the references back to MPI-4.1 although the timeframe is extremely small: one day - next Monday. The missing quality aspects allow that some implementors may still ignore this state of the art.

[jeffhammond]

It's easy enough to just fix Open-MPI. I don't think changing the standard is worth it in this case. It's clear enough what is supposed to happen.

[RolfRabenseifner]

One argument was that the MPI-4.0 sentence

"The dimensions are set to be as close to each other as possible, using an appropriate divisibility algorithm"

does not imply a mathematical measure that allows to decide whether 12x6 or 9x8 closer to each other.
For only two dimensions, one may think the difference should be minimal.
But already for three dimensions, the wording does not really help.

This is the reason, why we proposed the text on page 337, lines 28-38 in
https://github.com/mpi-forum/mpi-issues/files/5086553/mpi-report-issue120-topol-2020-08-17-annotated-pages334-335.pdf

The current definition (25 years old) does not give enough direction that implementations not just choose 72=12x6.

[jeffhammond]

does not imply a mathematical measure that allows to decide whether 12x6 or 9x8 closer to each other.

Given the context is a Cartesian communicator, the Euclidean distance seems appropriate although there is an argument for the L1 norm since it's easier to compute.

Does anyone in the forum argue that the measure is something other than the L1 or L2 norm? Is it a norm for which D(6,12) < D(8,9)?

[jprotze]

The optimal solution for $n$ ranks and $d$ dimensions would be $o = \sqrt[d]{n}$. So, the question is how close a solution approximates the optimal solution. Since the solution is a factorization of $n$, I think a proper metric for a solution vector S is:

$\prod_{i\in {1..d}}(\frac{min(o, s_i)}{max(o, s_i)})$

For d=2 this is equivalent to:
$\frac{min(s_1, s_2)}{max(s_1, s_2)}$
$D(6,12) = \frac{6}{12} = .5$
$D(8,9) = \frac{8}{9}$

[RolfRabenseifner]

This discussion is answered in the mentioned references [51] :

Christoph Niethammer and Rolf Rabenseifner. An MPI interface for application and
hardware aware Cartesian topology optimization. In Proceedings of the 26th European
MPI Users' Group Meeting (EuroMPI 2019), September 11-13, 2019, Z�urich, Switzerland.
ACM, New York, NY, USA, 9 pages.

Mimimizing the L1-Norm (i.e., the sum of all factors of the factorization) is equivalent to minimizing the sum of all neighborhood communication in the n-dimensional directions.
The second and third criterion (if the L1-norm of two factorizations is identical and minimal) are helpful for having the size of the communications in the different directions as equal as possible.
It is important that the criterion is related to communication time and its minimization.

Therefore the proposed AtoI, because existing implementors have obviously overseen these reasons.

I'll provide the text as PR latest tomorrow - just in time for the deadline.

[wgropp]

I should note that the underlying assumption behind the standards choice is faulty. What most users want is a set of dimensions that "works well" on their system. That depends on the network topology, among other things. So I am not sure how much value there is to users to specify the behavior of DIMS_CREATE to this level of detail. I'd rather see the standard go in the other direction - give an implementation freedom to suggest something relevant to the system on which it is running, with a fallback of some reasonably balanced factorization.