CODEWITHSUNDEEP
parallel-processingmpi
Michal Charemza
Michal Charemza

Reputation: 27062

How many hops do the default implementations of MPI_Reduce and MPI_Allreduce take?

I'm trying to work out how many separate parallel "hop" phases would typically be involved in MPI_Reduce and MPI_Allreduce, to get a ball-park figure of a minimum latency that would be involved in these operations. Essentially under the assumption that the messages are very small, so latency would dominate(?)

Say, a reduce between between 100 MPI processes. An implementation could take 99 "latencies": each process sending a message to one other. Another implementation could make each process send a message to all other nodes, and would only take 1 amount of "latency" (although yes, can't really imagine it would be so simple: there would be contention that increased this)

Upvotes: 0

Views: 200

Answers (1)

Jérôme Richard
Jérôme Richard

Reputation: 50956

To complete the good comment of @GillesGouaillardet, several MPI implementations use a dynamic/autotuned-based approach. This is the case of the widely-used OpenMPI and MPICH implementations (assuming they are configured correctly). The chosen algorithm can be dependent on several factors (as you can see in the research papers). Even in your specific case: the buffer size matters for example. Latency is not always the limiting factor, especially with few nodes. Furthermore, the network topology (eg. fat trees, hypercubes, torus, etc.) and the interconnect technology of the nodes have a significant impact on the latency and throughput. An efficient implementation must take that into account to be efficient, mainly to avoid the contention of the network. That being said, they are algorithms that can do this in log(n) hops (with n the number of nodes) on fat-trees/hypercube/butterfly networks (for both collective operations). For torus-based networks, the number of hops is bounded by the topology itself and more specifically by the diameter of the torus which is generally something like O(n^(1/d)) (with d the number of dimensions of the torus).

Upvotes: 1

Related Questions