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!
Center for Advanced Computing
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/
> 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/
> 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://
> 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].
> 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:
>> I guess I am confused how to get alltoall() down from n^2.
>> Brock Palen
>> Center for Advanced Computing
>> 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
>>> 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.
>>> Le 12 mars 08 à 17:01, Brock Palen a écrit :
>>>> I have always been told that calls like MPI_Barrior()
>>>> and MPI_Alltoall() should be avoided.
>>>> I understand MPI_Alltoall() as it goes n*(n-1) sends and thus
>>>> 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
>>>> users mailing list
>>> users mailing list
>> users mailing list
> users mailing list