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

Jeff Hammond jhammond at alcf.anl.gov
Thu Aug 9 09:58:49 CDT 2012 

(I'm not sure if Rolf wants my opinion or Squyres' but I'm never shy
about sharing mine...)

I agree with Brian and JeffS (and Bronis now) that it is too late to
change it.  The cross-references make it easier for someone without
the entire text of the standard in cache to understand, but I do not
believe they change the actually meaning hence can be omitted.

JeffH

On Thu, Aug 9, 2012 at 9:51 AM, Jeff Squyres <jsquyres at cisco.com> 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



-- 
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

More information about the mpi-forum mailing list