How to define and measure the performance of MPI_Bcast exactly?

[razor1991]

MPI_Bcast shows different performance under different MPI_Barrier algorithm via osu_bcast.

Background information

What version of Open MPI are you using? (e.g., v3.0.5, v4.0.2, git branch name and hash, etc.)

OpenMPI v4.1.x with UCX v1.10.1

Describe how Open MPI was installed (e.g., from a source/distribution tarball, from a git clone, from an operating system distribution package, etc.)

git clone
./configure --prefix=/path/to/mpi --with-ucx=/path/to/ucx --enable-mpi1-compatibility --with-platform=contrib/platform/mellanox/optimized

Please describe the system on which you are running

• Operating system/version: CentOS 7.6
• Computer hardware: Kunpeng920*2 (128 cores per node)
• Network type: CX5

---

Details of the problem

I do the osu_bcast test on 8 nodes with 128 ppn, but the performance show much better than 4 nodes on small packages.
Intuitively, the performance of 8 nodes should be worse than that of 4 nodes.

8 nodes test result:

mpirun -np 1024 -N 128 --hostfile ./hf8 --mca btl ^openib -x UCX_NET_DEVICES=mlx5_0:1 -x UCX_TLS=sm,rc osu_bcast -f

# OSU MPI Broadcast Latency Test v5.9
# Size       Avg Latency(us)   Min Latency(us)   Max Latency(us)  Iterations
1                       1.70              0.93              2.55        1000
2                       1.60              0.88              2.51        1000
4                       1.60              0.86              2.53        1000
8                       1.63              0.90              2.49        1000
16                      1.63              0.86              2.52        1000
32                      2.23              1.40              3.04        1000
64                      2.57              1.47              3.86        1000
128                     2.74              1.41              3.86        1000
256                     4.14              2.04              5.93        1000
512                     4.75              2.47              6.73        1000
1024                    7.41              4.15             10.42        1000
2048                    9.06              5.12             12.36        1000
4096                   13.68              7.09             19.08        1000

4 nodes test result:

mpirun -np 512 -N 128 --hostfile ./hf4 --mca btl ^openib -x UCX_NET_DEVICES=mlx5_0:1 -x UCX_TLS=sm,rc osu_bcast -f

# OSU MPI Broadcast Latency Test v5.9
# Size       Avg Latency(us)   Min Latency(us)   Max Latency(us)  Iterations
1                       7.64              2.48             15.57        1000
2                       7.74              2.50             15.78        1000
4                       7.62              2.51             15.78        1000
8                       7.61              2.51             15.49        1000
16                      7.66              2.43             15.61        1000
32                      8.18              2.61             16.52        1000
64                      9.19              2.89             17.88        1000
128                     9.32              3.20             17.94        1000
256                    12.02              3.73             25.10        1000
512                    12.83              4.28             26.23        1000
1024                   14.80              4.92             29.42        1000
2048                   16.38              5.26             33.53        1000
4096                   19.58              7.11             38.04        1000

I read the source code of coll/tuned, and I found that MPI_barrier use algorithm 4 (bruck) under 512 procs and use algorithm 6 (tree) under 1024 procs. So I change the MPI_Barrier algorithm 6->4 under 1024 procs, the result is below.

8 nodes with MPI_Barrier using algorithm 4, test result:

mpirun -np 1024 -N 128 --hostfile ./hf8 --mca btl ^openib -x UCX_NET_DEVICES=mlx5_0:1 -x UCX_TLS=sm,rc -mca coll_tuned_use_dynamic_rules true -mca coll_tuned_barrier_algorithm 4 osu_bcast -f

# OSU MPI Broadcast Latency Test v5.9
# Size       Avg Latency(us)   Min Latency(us)   Max Latency(us)  Iterations
1                       8.41              2.53             16.74        1000
2                       8.53              2.66             16.99        1000
4                       8.48              2.63             16.96        1000
8                       8.39              2.55             16.75        1000
16                      8.47              2.53             16.65        1000
32                      9.11              3.01             17.86        1000
64                     10.18              3.25             20.58        1000
128                    10.42              3.35             20.40        1000
256                    13.03              3.66             27.95        1000
512                    13.87              4.20             29.90        1000
1024                   16.49              5.23             34.55        1000
2048                   25.56              7.90             50.83        1000
4096                   22.57              7.53             44.77        1000

So, I have some questions.

1. Why different MPI_Barrier will affect the performance display of osu_bcast?
2. How to define and measure the performance of MPI_Bcast exactly?

[devreal]

@razor1991 I ran into the same problem and found that the reason for this unexpected behavior is the barrier implementation used. For some reason, OMPI switches implementations in the range [512...1024). Can you rerun your experiments on both 4 and 8 and pass the following flags: --mca coll_tuned_barrier_algorithm 6 --mca coll_tuned_use_dynamic_rules 1? This forces the use of the tree-based barrier, which lead to significantly lower latencies reported by the OSU benchmarks for MPI_Reduce in my case.

[devreal]

This issue is related to #10947.

[gkatev]

Why different MPI_Barrier will affect the performance display of osu_bcast?

I have experimented with this in the context of single-node broadcast. The osu microbenchmark executes an MPI_Barrier before each Bcast iteration, so that all ranks will enter the measured collective at the same time. But... will they? If the barrier implementation is not good/fast, they will exit the barrier with large variation and thus enter Bcast with large variation, and this can skew the reported latency (either worsening or improving it!).

I suggest experimentally finding (e.g. osu_barrier) the best barrier implementation for each scenario, and forcing its use while benchmarking other collectives.

[devreal]

@gkatev The "fastest" (according to osu_barrier) is not necessarily the "best" barrier in this case. What's important is uniform synchronization to avoid stragglers entering the actual collective under test, not the average latency (which is a questionable metric, at best). OSU is notoriously bad at doing what it's supposed to do (provide a measure of latency) but it's one of those tragedies of life that everyone is using it. There are better alternatives (IMB, mpibench) and I wish users would stop using OSU for good.

[razor1991]

@devreal
Result of 4 nodes:

mpirun -np 512 -N 128 --hostfile ./hf4 --mca btl ^openib -x UCX_NET_DEVICES=mlx5_0:1 -x UCX_TLS=sm,rc -mca coll_tuned_use_dynamic_rules true -mca coll_tuned_barrier_algorithm 6 osu_bcast -f
# OSU MPI Broadcast Latency Test v5.9
# Size       Avg Latency(us)   Min Latency(us)   Max Latency(us)  Iterations
1                       1.59              0.85              2.39        1000
2                       1.54              0.78              2.33        1000
4                       1.54              0.78              2.35        1000
8                       1.56              0.83              2.33        1000
16                      1.57              0.81              2.30        1000
32                      2.14              1.22              2.87        1000
64                      2.39              1.25              3.60        1000
128                     2.54              1.31              3.53        1000
256                     3.77              1.73              5.46        1000
512                     4.28              2.06              6.33        1000
1024                    6.70              3.42              9.77        1000
2048                    8.21              4.46             11.68        1000
4096                   12.46              6.26             18.35        1000

Result of 8 nodes:

mpirun -np 1024 -N 128 --hostfile ./hf8 --mca btl ^openib -x UCX_NET_DEVICES=mlx5_0:1 -x UCX_TLS=sm,rc -mca coll_tuned_use_dynamic_rules true -mca coll_tuned_barrier_algorithm 6 osu_bcast -f
# OSU MPI Broadcast Latency Test v5.9
# Size       Avg Latency(us)   Min Latency(us)   Max Latency(us)  Iterations
1                       1.66              0.88              2.54        1000
2                       1.61              0.88              2.43        1000
4                       1.60              0.82              2.49        1000
8                       1.62              0.88              2.45        1000
16                      1.62              0.86              2.48        1000
32                      2.20              1.40              3.04        1000
64                      2.56              1.46              3.94        1000
128                     2.73              1.49              3.85        1000
256                     4.14              2.06              5.93        1000
512                     4.70              2.43              6.77        1000
1024                    7.42              4.07             10.13        1000
2048                    9.14              5.05             12.39        1000
4096                   13.71              6.94             18.89        1000

[razor1991]

I experimented to reduce the test scale to 4 procs and print the latency of each rank.

Tree Barrier:

mpirun -np 4 --mca btl ^openib -x UCX_NET_DEVICES=mlx5_0:1 -x UCX_TLS=sm,rc -mca coll_tuned_use_dynamic_rules true -mca coll_tuned_barrier_algorithm 6 osu_bcast -f
# OSU MPI Broadcast Latency Test v5.9
# Size       Avg Latency(us)   Min Latency(us)   Max Latency(us)  Iterations
rank: 0, latency: 0.355740
rank: 2, latency: 0.200430
rank: 1, latency: 0.785600
rank: 3, latency: 0.390490
1                       0.43              0.20              0.79        1000

Bruck Barrier:

mpirun -np 4 --mca btl ^openib -x UCX_NET_DEVICES=mlx5_0:1 -x UCX_TLS=sm,rc -mca coll_tuned_use_dynamic_rules true -mca coll_tuned_barrier_algorithm 4 osu_bcast -f
# OSU MPI Broadcast Latency Test v5.9
# Size       Avg Latency(us)   Min Latency(us)   Max Latency(us)  Iterations
rank: 0, latency: 0.779740
rank: 3, latency: 1.103850
rank: 1, latency: 1.028930
rank: 2, latency: 0.872790
1                       0.95              0.78              1.10        1000

As we can see, in "Tree Barrier" the min lantecy is rank 2 not rank 0!!
For bcast on 4 procs, the communication pattern is "rank 0"->"rank 2", "rank 0->rank 1" and "rank 2->rank 3".
The latency of rank 2 should not be smaller than rank 0, if the barrier is ideals.

I speculated that in MPI_Barrier stage, rank 2 have received the bcast data from rank 0. So when rank 2 enter MPI_Bcast, it don't need to spend time to wait receive data.

[razor1991]

@devreal I agree with you about "OSU is notoriously bad at doing what it's supposed to do" :)
The same result happened when I use IMB, but IMB has a parameter "-imb_barrier on" to use internal barrier instead of MPI_Barrier. The result shows similar to use "Bruck Barrier" when testing MPI_Bcast. Maybe It is much fair to test all MPI Interfaces using same barrier.

[razor1991]

I suggest experimentally finding (e.g. osu_barrier) the best barrier implementation for each scenario, and forcing its use while benchmarking other collectives.

@gkatev I think for MPI benchmark test, we should use a more balanced barrier implementation, even it is slower ("Tree Barrier" is not good for testing, especially for one-to-all MPI API, like MPI_Bcast, MPI_Reduce, etc.). Because the time of MPI_Barrier is not recorded in benchmark result. I've read the "imb_barrier" in IMB, it is a recursive doubling barrier implementation, which usually is slower than tree barrier.

[gkatev]

@razor1991 In the above scenario with 4 procs, are they all on the same node, or spread across 4 nodes? If on the same node, I suggest also a benchmark with coll/sm's barrier, which I've generally seen perform well on most systems (you would have to manually disable tuned's barrier, add sm to the coll list + adjust its priority).

I agree with the above sentiments, the best/ideal barrier in this scenario (microbenchmarking) is the one where all processes exit simultaneously (or, the closest that we have to that), whether it's fast or slow. The "choose the barrier performing the best in osu_barrier" advice is probably the quick approach, but indeed not necessarily the correct one. Ideally, one would have to measure exactly how "synchronized" the ranks exit the barrier and enter the collective -- possible easier said than done, especially with multiple nodes (due to clock synchronization issues, I imagine). Furthermore as also noted, one should optimally consider both the exit pattern from the barrier, as well as the communication pattern of the respective Bcast implementation, and how these will "mesh" together, and how that will skew the reported latency.

I also follow the idea of using the same barrier for all components' benchmarks, in an attempt to be fair. I only really do single-node benchmarks, for now -- I feel like it's easier to get uniform/synchronized exit from a barrier in a single vs multiple ones.

As for the OSU benchmarks, I'd say it's a tool with its shortcomings and its advantages. I use it for evaluating my implementations and for detecting performance phenomenons. But I'm aware of some issues (ideally, all of them...), like the barrier implementation, the fact that it always uses root=0, and that it never alters the data buffer it sends (I've modified it to write to the buffer before each iteration, to avoid phenomenons due to caching across iterations). I don't have much experience with IMB or other suites, though I should at some point... Indeed, for evaluating the general performance of MPI implementations (and without any due diligence) by users, it might not be the right tool!

Inspired by @razor1991's testing above, I tried some experiments (single node) with a tool I have for visualizing bcast executions in a fine scale. I'm attaching what an xpmem-shared-memory bcast looks like, preceded by different barriers. The message size is 16K instead of few bytes (less noisy, hopefully). There's probably too much info in the graphs, but the important part is the white space between t=0 and the grey area. The grey part denotes idle time, and where it begins is the point at which the rank enters the collective, so the white area is the time that other ranks have entered the collective, but the local one has not. Again this is only a single node, so probably not all that useful here, but I'm putting this up for however it might be useful.

Don't quote me too much on these graphs, the tool is experimental :-). I didn't take the time to verify that the communication pattern of the barriers matches the bcast-enter patterns that the graphs show...

Also, data dump of osu_barrier results for these barrier implementations (single node, 4 procs, 10 runs, recording the average of each one, and below is the average of the 10 averages, their deviation, etc):

Recursive doubling
Average 1.035 us, Stddev 0.146373 us, Min 0.86 us, Max 1.25 us

Bruck
Average 1.07 us, Stddev 0.15479 us, Min 0.87 us, Max 1.28 us

Tree
Average 1.382 us, Stddev 0.147296 us, Min 1.19 us, Max 1.57 us

coll/sm
Average 0.402 us, Stddev 0.0376298 us, Min 0.36 us, Max 0.49 us

[razor1991]

@gkatev The 4 procs test is on single node.

As we can see, in "Tree Barrier" the min lantecy is rank 2 not rank 0!!
For bcast on 4 procs, the communication pattern is "rank 0"->"rank 2", "rank 0->rank 1" and "rank 2->rank 3".
The latency of rank 2 should not be smaller than rank 0, if the barrier is ideals.

I did a further analysis for "min lantecy is rank 2 not rank 0". I use coll/tuned, so we can treat MPI_Barrier(tree) as MPI_Gather(tree) and MPI_Bcast(tree), so the MPI_Bcast(tree) in MPI_Barrier and MPI_Bcast(tree) be tested will overlap.

But for Recursive Doubling Barrier(algo id 3) or Bruck Barrier(algo id 4), a lot of rank pairs will send and receive to each other, which can less overlap with MPI_Bcast(tree).