[Mpi-forum] [EXTERNAL] Re: Fairness of MPI_ANY_SOURCE - MPI-3.0 Draft2 comment by Sebastien Boisvert
Rolf Rabenseifner
rabenseifner at hlrs.de
Thu Aug 9 09:32:49 CDT 2012
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)
More information about the mpi-forum
mailing list