[Mpi-forum] [EXTERNAL] Re: Fairness of MPI_ANY_SOURCE - MPI-3.0 Draft2 comment by Sebastien Boisvert

Richard Graham richardg at mellanox.com
Thu Aug 9 10:13:29 CDT 2012 

Agreed - the text is very clear, and any enumeration just sets us up to miss something in the future.

Rich

-----Original Message-----
From: mpi-forum-bounces at lists.mpi-forum.org [mailto:mpi-forum-bounces at lists.mpi-forum.org] On Behalf Of Bronis R. de Supinski
Sent: Thursday, August 09, 2012 5:58 PM
To: Main MPI Forum mailing list
Subject: Re: [Mpi-forum] [EXTERNAL] Re: Fairness of MPI_ANY_SOURCE - MPI-3.0 Draft2 comment by Sebastien Boisvert


I agree with Brian and Jeff. While the proposed additions are not a substantiative change, I think they add very little value and would require editing for wording that is likely to be incomplete. Bring it up for MPI Next.

On Thu, 9 Aug 2012, Jeff Squyres wrote:

> I agree that adding that text are enhancements and don't change the meaning of the spec (at least, at first glance they don't appear to change the meaning to me -- I am trusting Rolf on this point).
>
> I don't think adding these enhancements are a good idea at this late stage.  Possibly a good candidate for 3.1, though.
>
>
> On Aug 9, 2012, at 10:32 AM, Rolf Rabenseifner wrote:
>
>> Brian,
>>
>> I did not changed the standard with my proposal.
>> I added 4 cross-references to make clear and findable for each reader 
>> that MPI says "no garantee of fairness".
>>
>> Are you against these cross-references?
>> If yes, why?
>> Obviously users cannot find the behavior of MPI_ANY_SOURCE because 
>> exactly these references are missing.
>>
>> Jeff and Bill,
>>
>> are you pro or con the adding of my proposed cross-references?
>>
>> Rolf
>>
>> ----- Original Message -----
>>> From: "Brian W Barrett" <bwbarre at sandia.gov>
>>> To: "Main MPI Forum mailing list" <mpi-forum at lists.mpi-forum.org>
>>> Sent: Thursday, August 9, 2012 3:55:28 PM
>>> Subject: Re: [Mpi-forum] [EXTERNAL] Re: Fairness of MPI_ANY_SOURCE - 
>>> MPI-3.0 Draft2 comment by Sebastien Boisvert Since Rolf explicitly 
>>> asked for my opinion, I agree with Bill. No text change is required.
>>>
>>> Brian
>>>
>>> On 8/9/12 7:11 AM, "William Gropp" <wgropp at illinois.edu> wrote:
>>>
>>>> Agreed. This has always been a "quality of implementation" issue, 
>>>> since, as Jeff notes, providing fairness, particularly a 
>>>> specifically defined fairness, can have significant performance 
>>>> implications.
>>>>
>>>> Bill
>>>>
>>>> William Gropp
>>>> Director, Parallel Computing Institute Deputy Director for Research 
>>>> Institute for Advanced Computing Applications and Technologies Paul 
>>>> and Cynthia Saylor Professor of Computer Science University of 
>>>> Illinois Urbana-Champaign
>>>>
>>>>
>>>>
>>>> On Aug 9, 2012, at 6:01 AM, Jeff Hammond wrote:
>>>>
>>>>> I think this is very thorough and useful. I also agree that 
>>>>> fairness should absolutely not be added to the standard. It's a 
>>>>> nightmare for performance in some cases.
>>>>>
>>>>> Jeff
>>>>>
>>>>> On Thu, Aug 9, 2012 at 4:55 AM, Rolf Rabenseifner 
>>>>> <rabenseifner at hlrs.de> wrote:
>>>>>> Rich,
>>>>>>
>>>>>> yes and no:
>>>>>> - Yes, any real change about fairness is going beyond MPI-3.0.
>>>>>>
>>>>>> - No, the current text is not clear enough because there is no 
>>>>>> reference between MPI_ANY_SOURCE and the "lack of fairness"
>>>>>> statement.
>>>>>> For this, I proposed the clarifications below.
>>>>>>
>>>>>> What does the Pt-to-Pt chapter team, i.e., Richard Graham(c), 
>>>>>> Anthony Skjellum, Fab Tillier, Brian Smith, Devendar Bureddy, 
>>>>>> Bill Gropp, Torsten Hoefler, Adam Moody, Martin Schulz, Brian 
>>>>>> Barrett, think about my proposal?
>>>>>>
>>>>>> - And all discussion on any changes of the current text should go 
>>>>>> through "Main MPI Forum mailing list"
>>>>>> <mpi-forum at lists.mpi-forum.org>
>>>>>> otherwise the risk of problems popping up between Sep 12 and Sep
>>>>>> 20
>>>>>> is to big.
>>>>>>
>>>>>> Best regards
>>>>>> Rolf
>>>>>>
>>>>>> ----- Original Message -----
>>>>>>> From: "Richard Graham" <richardg at mellanox.com>
>>>>>>> To: "Main MPI Forum mailing list" 
>>>>>>> <mpi-forum at lists.mpi-forum.org>
>>>>>>> Sent: Thursday, August 9, 2012 11:23:57 AM
>>>>>>> Subject: Re: [Mpi-forum] Fairness of MPI_ANY_SOURCE - MPI-3.0
>>>>>>> Draft2
>>>>>>> comment by Sebastien Boisvert
>>>>>>> Rolf,
>>>>>>> Thanks a lot for the help here, but this is really not needed at 
>>>>>>> this stage. I have started to farm off requests to the 
>>>>>>> appropriate working groups. In this case, the response will be 
>>>>>>> that we will need a specific proposal for something to happen 
>>>>>>> beyond MPI 3.0, as this can be either an implementation issue, 
>>>>>>> or a change in long-standing semantics, which are beyond the 
>>>>>>> scope of the current work.
>>>>>>>
>>>>>>> Thanks,
>>>>>>> Rich
>>>>>>>
>>>>>>> -----Original Message-----
>>>>>>> From: mpi-forum-bounces at lists.mpi-forum.org
>>>>>>> [mailto:mpi-forum-bounces at lists.mpi-forum.org] On Behalf Of Rolf 
>>>>>>> Rabenseifner
>>>>>>> Sent: Thursday, August 09, 2012 12:20 PM
>>>>>>> To: Main MPI Forum mailing list
>>>>>>> Subject: [Mpi-forum] Fairness of MPI_ANY_SOURCE - MPI-3.0 Draft2 
>>>>>>> comment by Sebastien Boisvert
>>>>>>>
>>>>>>> I try to test the proposed process for comments.
>>>>>>>
>>>>>>> This comment is about the Point-to-Point chapter.
>>>>>>> Rich is the chapter author.
>>>>>>>
>>>>>>> Here is the comment (see bottom of this email) together with my 
>>>>>>> reply to the comment's author and a first proposal for solving 
>>>>>>> it:
>>>>>>>
>>>>>>> All references are related to
>>>>>>> http://meetings.mpi-forum.org/draft_standard/mpi3.0_draft_2.pdf
>>>>>>>
>>>>>>> Summary about the comment:
>>>>>>> ==========================
>>>>>>>
>>>>>>> The text in new MPI_IMPROBE about MPI_ANY_SOURCE does not say 
>>>>>>> anything about fairness.
>>>>>>> The commentator asks for a round-robin fairness behavior.
>>>>>>>
>>>>>>> Summary of my proposal to answer this comment:
>>>>>>> ==============================================
>>>>>>>
>>>>>>> - Keep the unfair behavior as defined on p42:10-17
>>>>>>> - Clarify this faiirness-paragraph to make clear that it also 
>>>>>>> applies to MPI_ANY_SOURCE.
>>>>>>> - Add cross-references between p42:10-17, MPI_RECV and all 
>>>>>>> MPI_PROBE routines to make clear that there is no fairness with 
>>>>>>> MPI_ANY_SOURCE.
>>>>>>>
>>>>>>> Proposed solution:
>>>>>>> ==================
>>>>>>>
>>>>>>> All references are related to
>>>>>>> http://meetings.mpi-forum.org/draft_standard/mpi3.0_draft_2.pdf
>>>>>>>
>>>>>>> mpi3.0_draft_2.pdf p29:25-31 read
>>>>>>>
>>>>>>> The receiver may specify a wildcard MPI_ANY_SOURCE value for 
>>>>>>> source, and/or a wildcard MPI_ANY_TAG value for tag, indicating 
>>>>>>> that any source and/or tag are acceptable.
>>>>>>> It cannot specify a wildcard value for comm. Thus, a message can 
>>>>>>> be received by a receive operation only if it is addressed to 
>>>>>>> the receiving process, has a matching communicator, has matching 
>>>>>>> source unless source=MPI_ANY_SOURCE in the pattern, and has a 
>>>>>>> matching tag unless tag=MPI_ANY_TAG in the pattern.
>>>>>>>
>>>>>>> and the following text should be added:
>>>>>>>
>>>>>>> Note that MPI makes no guarantee of fairness in the handling of 
>>>>>>> communication, especially when using MPI_ANY_SOURCE; for details 
>>>>>>> see the section on {\em Fairness} on page 42.
>>>>>>>
>>>>>>>
>>>>>>> mpi3.0_draft_2.pdf p42:10 read
>>>>>>>
>>>>>>> Fairness[ ] MPI makes no guarantee of fairness in the handling 
>>>>>>> of communication.
>>>>>>>
>>>>>>> but should read
>>>>>>>
>>>>>>> Fairness[ ] MPI makes no guarantee of fairness in the handling 
>>>>>>> of communication, e.g., when using MPI_ANY_SOURCE, MPI_WAITANY 
>>>>>>> or MPI_WAITSOME in a singlethreaded process, or using MPI_RECV 
>>>>>>> or MPI_MPROBE by several threads in a multithreaded process.
>>>>>>>
>>>>>>>
>>>>>>> mpi3.0_draft_2.pdf p65:16-18 (in the definition of MPI_IPROBE) 
>>>>>>> read
>>>>>>>
>>>>>>> The call matches the same message that would have been received 
>>>>>>> by a call to MPI_RECV(..., source, tag, comm, status) executed 
>>>>>>> at the same point in the program, and returns in status the same 
>>>>>>> value that would have been returned by MPI_RECV().
>>>>>>>
>>>>>>> but should read (only the reference on the last line is added):
>>>>>>>
>>>>>>> The call matches the same message that would have been received 
>>>>>>> by a call to MPI_RECV(..., source, tag, comm, status) executed 
>>>>>>> at the same point in the program, and returns in status the same 
>>>>>>> value that would have been returned by MPI_RECV(), see Section 
>>>>>>> 3.2.4 on page 28.
>>>>>>>
>>>>>>>
>>>>>>> mpi3.0_draft_2.pdf p68:33-35 (in the definition of MPI_IMPROBE) 
>>>>>>> read
>>>>>>>
>>>>>>> The call matches the same message that would have been received 
>>>>>>> by a call to MPI_RECV(..., source, tag, comm, status) executed 
>>>>>>> at the same point in the program and returns in status the same 
>>>>>>> value that would have been returned by MPI_RECV.
>>>>>>>
>>>>>>> but should read (only the reference on the last line is added):
>>>>>>>
>>>>>>> The call matches the same message that would have been received 
>>>>>>> by a call to MPI_RECV(..., source, tag, comm, status) executed 
>>>>>>> at the same point in the program and returns in status the same 
>>>>>>> value that would have been returned by MPI_RECV, see Section 
>>>>>>> 3.2.4 on page 28.
>>>>>>>
>>>>>>>
>>>>>>> Proposed answer to the commentator (together with the proposed 
>>>>>>> solution):
>>>>>>> ======================================
>>>>>>>
>>>>>>> MPI defines to be unfair, see page 42, lines 10-17.
>>>>>>> Cross-references were missing in the MPI standard, i.e., it was 
>>>>>>> not easy to detect that this paragraph on fairness also applies 
>>>>>>> to MPI_ANY_SOURCE in any call (MPI_RECV, MPI_IRECV, and all 
>>>>>>> versions of
>>>>>>> MPI_PROBE) The proposed solution adds the missing 
>>>>>>> cross-references.
>>>>>>>
>>>>>>> For performance reasons, the MPI Forum decided not to change 
>>>>>>> this "unfair" behavior.
>>>>>>>
>>>>>>> You may use other mechanisms to implement some sort of fairness.
>>>>>>> Especially the tag can be used in a cyclic way (i.e. with values 
>>>>>>> between 0 and 32767) to implement some sort of fairness, but 
>>>>>>> this is outside of the scope of the MPI standard.
>>>>>>>
>>>>>>> We did not add an advice to users about mechanisms to implement 
>>>>>>> some sort of fairness within the application.
>>>>>>> Such an advice would go beyond the task of the MPI standard.
>>>>>>>
>>>>>>>
>>>>>>> Background (not to be part of the answer to the commentator) 
>>>>>>> ============================================================
>>>>>>>
>>>>>>> The following part of the comment
>>>>>>>> Presently, the MPI standard contains nothing about which source 
>>>>>>>> should be probed when MPI_ANY_SOURCE is provided.
>>>>>>> is not fully true.
>>>>>>> The MPI standard clearly states in mpi3.0_draft_2.pdf in Section 
>>>>>>> 3.5 Semantics of Point-to-Point Communication on page 42 lines 
>>>>>>> 10-17
>>>>>>>
>>>>>>> Fairness. MPI makes no guarantee of fairness in the handling of 
>>>>>>> communication. Suppose that a send is posted. Then it is 
>>>>>>> possible that the destination process repeatedly posts a receive 
>>>>>>> that matches this send, yet the message is never received, 
>>>>>>> because it is each time overtaken by another message, sent from 
>>>>>>> another source.
>>>>>>> Similarly, suppose that a receive was posted by a multithreaded 
>>>>>>> process. Then it is possible that messages that match this 
>>>>>>> receive are repeatedly received, yet the receive is never 
>>>>>>> satisfied, because it is overtaken by other receives posted at 
>>>>>>> this node (by other executing threads). It is the programmer's 
>>>>>>> responsibility to prevent starvation in such situations.
>>>>>>>
>>>>>>> that there is no fairness.
>>>>>>> And I expect that the MPI Forum does not want to change this 
>>>>>>> statement.
>>>>>>> This section does not mention MPI_ANY_SOURCE.
>>>>>>> My proposal adds here a note on MPI_ANY_SOURCE that readers can 
>>>>>>> find the Fairness paragraph when the look at all locations of 
>>>>>>> MPI_ANY_SOURCE.
>>>>>>>
>>>>>>> MPI_ANY_SOURCE is defined in the text about the source rank of 
>>>>>>> MPI_RECV without any reference to the Fairness paragraph, see 
>>>>>>> page 29 lines 23-31.
>>>>>>> I added a reference to the Fairness paragraph to solve this lack 
>>>>>>> of reference.
>>>>>>>
>>>>>>> And MPI_IPROBE and MPI_IMPROBE have own text on MPI_ANY_SOURCE.
>>>>>>> Here I would propose to add only a reference to Section 3.2.4, 
>>>>>>> which defines MPI_RECV and which should contain the reference to 
>>>>>>> the fairness paragraph.
>>>>>>>
>>>>>>> ----------------------
>>>>>>> My goal was not to change anything, i.e., only to add clarifying 
>>>>>>> references.
>>>>>>> Any comments about this proposal?
>>>>>>> Corrections about my wording?
>>>>>>> Agreed?
>>>>>>>
>>>>>>> Best regards
>>>>>>> Rolf
>>>>>>>
>>>>>>>
>>>>>>> ----- Forwarded Message -----
>>>>>>> From: "Rolf Rabenseifner" <rabenseifner at hlrs.de>
>>>>>>> To: "Sébastien Boisvert" <sebastien.boisvert.3 at ulaval.ca>
>>>>>>> Sent: Thursday, August 9, 2012 8:09:49 AM
>>>>>>> Subject: Re: [Mpi-comments] One comment on MPI-3.0 Draft 2, 
>>>>>>> August
>>>>>>> 2012
>>>>>>>
>>>>>>> Dear Mr. Boisvert,
>>>>>>>
>>>>>>> the MPI Forum will discuss your comment and will return an 
>>>>>>> answer before our meeting Sep. 20-21 in Vienna.
>>>>>>>
>>>>>>> Best regards
>>>>>>> Rolf Rabenseifner
>>>>>>>
>>>>>>> ----- Original Message -----
>>>>>>>> From: "Sébastien Boisvert" <sebastien.boisvert.3 at ulaval.ca>
>>>>>>>> To: mpi-comments at mpi-forum.org
>>>>>>>> Sent: Sunday, August 5, 2012 6:50:29 AM
>>>>>>>> Subject: [Mpi-comments] One comment on MPI-3.0 Draft 2, August
>>>>>>>> 2012
>>>>>>>> Dear MPI Forum committee members,
>>>>>>>>
>>>>>>>> I would like to submit a comment on the MPI-3.0 Draft 2, August
>>>>>>>> 2012
>>>>>>>> for your consideration.
>>>>>>>>
>>>>>>>> Version: MPI-3.0 Draft 2, August 2012.
>>>>>>>>
>>>>>>>> The URL of the version of the MPI standard:
>>>>>>>> http://meetings.mpi-forum.org/draft_standard/mpi3.0_draft_2.pdf
>>>>>>>>
>>>>>>>> Page: 65
>>>>>>>>
>>>>>>>> Line number: 28
>>>>>>>>
>>>>>>>> Section: 3.8.1
>>>>>>>>
>>>>>>>> In:
>>>>>>>>
>>>>>>>> 3. Point-to-Point Communication
>>>>>>>> 3.8 Probe and Cancel
>>>>>>>> 3.8.1 Probe
>>>>>>>>
>>>>>>>> Comment:
>>>>>>>>
>>>>>>>> It says that the source argument of MPI_Iprobe can be 
>>>>>>>> MPI_ANY_SOURCE, but it does say anything about fairness. 
>>>>>>>> Therefore MPI_ANY_SOURCE can lead to resource starvation.
>>>>>>>>
>>>>>>>> I think it would be better if probing would be done in a 
>>>>>>>> round-robin fashion when the source is MPI_ANY_SOURCE so that 
>>>>>>>> any MPI rank has an equal chance of having its message probed 
>>>>>>>> and received.
>>>>>>>>
>>>>>>>> Presently, the MPI standard contains nothing about which source 
>>>>>>>> should be probed when MPI_ANY_SOURCE is provided.
>>>>>>>>
>>>>>>>> I hope you will consider my comment.
>>>>>>>>
>>>>>>>>
>>>>>>>> Sincerely,
>>>>>>>>
>>>>>>>>
>>>>>>>> Sébastien Boisvert
>>>>>>>> PhD student
>>>>>>>> Université Laval
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> mpi-comments mailing list
>>>>>>>> mpi-comments at lists.mpi-forum.org 
>>>>>>>> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-comments
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Dr. Rolf Rabenseifner . . . . . . . . . .. email 
>>>>>> rabenseifner at hlrs.de High Performance Computing Center (HLRS) . 
>>>>>> phone
>>>>>> ++49(0)711/685-65530
>>>>>> University of Stuttgart . . . . . . . . .. fax ++49(0)711 /
>>>>>> 685-65832
>>>>>> Head of Dpmt Parallel Computing . . .
>>>>>> www.hlrs.de/people/rabenseifner
>>>>>> Nobelstr. 19, D-70550 Stuttgart, Germany . (Office: Allmandring
>>>>>> 30)
>>>>>>
>>>>>> _______________________________________________
>>>>>> mpi-forum mailing list
>>>>>> mpi-forum at lists.mpi-forum.org
>>>>>> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-forum
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Jeff Hammond
>>>>> Argonne Leadership Computing Facility University of Chicago 
>>>>> Computation Institute jhammond at alcf.anl.gov / (630) 252-5381 
>>>>> http://www.linkedin.com/in/jeffhammond
>>>>> https://wiki.alcf.anl.gov/parts/index.php/User:Jhammond
>>>>>
>>>>> _______________________________________________
>>>>> mpi-forum mailing list
>>>>> mpi-forum at lists.mpi-forum.org
>>>>> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-forum
>>>>
>>>>
>>>> _______________________________________________
>>>> mpi-forum mailing list
>>>> mpi-forum at lists.mpi-forum.org
>>>> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-forum
>>>>
>>>>
>>>
>>>
>>> --
>>> Brian W. Barrett
>>> Dept. 1423: Scalable System Software Sandia National Laboratories
>>>
>>>
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> mpi-forum mailing list
>>> mpi-forum at lists.mpi-forum.org
>>> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-forum
>>
>> --
>> Dr. Rolf Rabenseifner . . . . . . . . . .. email rabenseifner at hlrs.de
>> High Performance Computing Center (HLRS) . phone ++49(0)711/685-65530
>> University of Stuttgart . . . . . . . . .. fax ++49(0)711 / 685-65832
>> Head of Dpmt Parallel Computing . . . www.hlrs.de/people/rabenseifner
>> Nobelstr. 19, D-70550 Stuttgart, Germany . (Office: Allmandring 30)
>>
>> _______________________________________________
>> mpi-forum mailing list
>> mpi-forum at lists.mpi-forum.org
>> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-forum
>
>
> --
> Jeff Squyres
> jsquyres at cisco.com
> For corporate legal information go to: http://www.cisco.com/web/about/doing_business/legal/cri/
>
>
> _______________________________________________
> mpi-forum mailing list
> mpi-forum at lists.mpi-forum.org
> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-forum
>

More information about the mpi-forum mailing list