This is good information for me!
For my users though its over the top. I was looking for simple
reasons why, I think I have that now though. Thanks!
Brock Palen
Center for Advanced Computing
bro...@umich.edu
(734)936-1985
On Mar 13, 2008, at 11:16 AM, George Bosilca wrote:
Collective communication was a hot topic for the last [at least
one] decade, and it is still today. Just minimizing the number of
messages is not generally the best approach. The collectives are
sensitive to the network characteristics and to the amount of data
in a very complex way. The best approach is a well balanced
algorithms, where the number of messages and the amount of data on
each message is computed based on the network properties. This
paper can give you an idea about this (http://csdl2.computer.org/
persagen/DLAbsToc.jsp?resourcePath=/dl/proceedings/&toc=comp/
proceedings/ipdps/2005/2312/16/2312toc.xml&DOI=10.1109/IPDPS.
2005.335).
In terms of theoretical complexity, the best Allreduce algorithm
I'm aware about allow you to decrease the complexity to O(log
(size)) + O(count), where size is the size of the message and count
is the number of participants in the communicator. You can find a
reference to this algorithm here (http://www.hlrs.de/organization/
par/services/models/mpi/myreduce.html).
Even the Alltoall can be optimized, but unfortunately not as much
as the other collective. This collective is considered as the most
difficult to implement and to optimize, even on homogeneous
environments. Another interesting paper on alltoall is http://
ieeexplore.ieee.org/Xplore/login.jsp?url=/
iel4/71/13981/00642949.pdf?arnumber=642949.
Is there anything more complex than a alltoall ... Well you can
take a look in the same family of collectives communication
patterns to alltoall[vwx].
george.
On Mar 13, 2008, at 9:29 AM, Brock Palen wrote:
Yeah, I know what you mean about if you have to use a 'all to all'
use MPI_Alltoall() don't roll your own.
So on paper, alltoall at first glance appears to be: n*(n-1) -> n^2-
n -> n^2 (for large n).
Allreduce appears to be simplest, n point to points followed by a
bcast(). Which can be simplified to gather + bcast.
Last I knew MPI_Bcast() was log(n) and gather is (n). So for
allreduce I get:
n+log(n)
I guess I am confused how to get alltoall() down from n^2.
Thanks.
Brock Palen
Center for Advanced Computing
bro...@umich.edu
(734)936-1985
On Mar 12, 2008, at 6:05 PM, Aurélien Bouteiller wrote:
If you can avoid them it is better to avoid them. However it is
always
better to use a MPI_Alltoall than coding your own all to all with
point to point, and in some algorithms you *need* to make a all
to all
communication. What you should understand by "avoid all to all"
is not
avoid MPI_alltoall, but choose a mathematic algorithm that does not
need all to all.
The algorithmic complexity of AllReduce is the same as AlltoAll.
Aurelien
Le 12 mars 08 à 17:01, Brock Palen a écrit :
I have always been told that calls like MPI_Barrior()
MPI_Allreduce()
and MPI_Alltoall() should be avoided.
I understand MPI_Alltoall() as it goes n*(n-1) sends and thus
grows
very very quickly. MPI_Barrior() is very latency sensitive and
generally is not needed in most cases I have seen it used.
But why MPI_Allreduce()?
What other functions should generally be avoided?
Sorry this is kinda off topic for the list :-)
Brock Palen
Center for Advanced Computing
bro...@umich.edu
(734)936-1985
_______________________________________________
users mailing list
us...@open-mpi.org
http://www.open-mpi.org/mailman/listinfo.cgi/users
_______________________________________________
users mailing list
us...@open-mpi.org
http://www.open-mpi.org/mailman/listinfo.cgi/users
_______________________________________________
users mailing list
us...@open-mpi.org
http://www.open-mpi.org/mailman/listinfo.cgi/users
_______________________________________________
users mailing list
us...@open-mpi.org
http://www.open-mpi.org/mailman/listinfo.cgi/users
