Open MPI logo

Open MPI User's Mailing List Archives

  |   Home   |   Support   |   FAQ   |   all Open MPI User's mailing list

Subject: Re: [OMPI users] MPI_Allreduce()
From: Brock Palen (brockp_at_[hidden])
Date: 2008-03-13 17:18:51


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
brockp_at_[hidden]
(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
>> brockp_at_[hidden]
>> (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
>>>> brockp_at_[hidden]
>>>> (734)936-1985
>>>>
>>>>
>>>> _______________________________________________
>>>> users mailing list
>>>> users_at_[hidden]
>>>> http://www.open-mpi.org/mailman/listinfo.cgi/users
>>>
>>>
>>> _______________________________________________
>>> users mailing list
>>> users_at_[hidden]
>>> http://www.open-mpi.org/mailman/listinfo.cgi/users
>>>
>>>
>>
>>
>> _______________________________________________
>> users mailing list
>> users_at_[hidden]
>> http://www.open-mpi.org/mailman/listinfo.cgi/users
>
> _______________________________________________
> users mailing list
> users_at_[hidden]
> http://www.open-mpi.org/mailman/listinfo.cgi/users