[mpiwg-p2p] ticket 463 "any order communicator info key"

Daniel Holmes dholmes at epcc.ed.ac.uk
Tue Mar 24 05:16:32 CDT 2015


Hi Mike,

My understanding is that "no ordering", "any order" and "unique 
matching" are all attempting to express the same potential optimisation. 
One strong driver for whatever this INFO key ends up being called is the 
trend towards dynamic routing fabrics.

Another possible driver is, as you say, the possibility of simplifying 
the point-to-point matching queue structure. The request queue, and the 
unmatched-send queue, are currently partially ordered priority queues 
rather than a strict FIFO queues. The hash/map data structure you 
mention can be seen as an index into the (one, big) matching queue, 
which reduces the search time from O(n) for linear search to O(log(n)) 
for tree search. This can be done with current MPI semantics. There are 
a couple of ways of arranging the index but it effectively allows the 
one, big matching queue to be partitioned into a collection of strict 
FIFO queues (one per communicator+target+source+tag combination), which 
reduces the search time to O(1) for remove head item for the correct 
queue. However, finding the correct queue (mapping {context id, target, 
source|any_source, tag|any_tag} to one of many FIFO queues) is, at best, 
an O(log(n)) operation. I am currently writing a paper on this subject 
targeted at EuroMPI 2015.

This new INFO key does not subvert proper matching using source and tag 
but, for messages with the same source and tag as each other, it removes 
the ordering requirement that forces them to be matched a particular 
sequence. This would result in an indexed collection of (unordered) bags 
instead of an indexed collection of (ordered) FIFO queues. Removal of an 
item from a bag is O(1), exactly the same as removal from a FIFO queue, 
so probably nothing is gained over the hash/map index approach to 
optimising current semantics.

I believe, therefore, that the *only* driver for this INFO key is a 
fabric optimisation: the ability to enable dynamic routing without 
adding sequence numbers to the message envelope and buffering 
out-of-sequence envelopes at the receiver to recover the required ordering.

Cheers,
Dan.

On 23/03/2015 17:04, Blocksome, Michael wrote:
>
> In ticket 463, what is the difference between “no_ordering” and 
> “any_order”?
>
> The text for any_order permits messages to overtake others from the 
> same sender – messages are unordered. Isn’t this also what the 
> no_ordering text says as it “does not require message ordering”? Is 
> the key word somehow “require” here?
>
> What is the expected benefit for the mpi implementation for 
> no_ordering/any_order (not considering fabric optimizations)?  Is the 
> idea that the request queue (fifo) can be replaced with a hash/map 
> data structure so it’s faster to match?
>
> That’s enough for now .. Thanks! J
>
> Mike
>
> *From:*mpiwg-p2p [mailto:mpiwg-p2p-bounces at lists.mpi-forum.org] *On 
> Behalf Of *Daniel Holmes
> *Sent:* Monday, March 23, 2015 9:57 AM
> *To:* MPI WG Point To Point Communications working group
> *Subject:* Re: [mpiwg-p2p] Next meeting: 16th March 2015 11am Central US
>
> Hi Mike,
>
> Let's have the initial discussion on the email list and then add 
> relevant content to the appropriate ticket(s).
>
> Cheers,
> Dan.
>
> On 23/03/2015 14:46, Blocksome, Michael wrote:
>
>     I’ve got some comments on the info keys tickets – do you prefer to
>     have the discussion in the tickets or on the mailing list (so that
>     the ticket is more readable as a proposal “draft”) ?
>
>     Thanks,
>
>     Mike
>
>     *From:*mpiwg-p2p [mailto:mpiwg-p2p-bounces at lists.mpi-forum.org]
>     *On Behalf Of *Daniel Holmes
>     *Sent:* Monday, March 23, 2015 7:01 AM
>     *To:* MPI WG Point To Point Communications working group
>     *Subject:* Re: [mpiwg-p2p] Next meeting: 16th March 2015 11am
>     Central US
>
>     Hi All,
>
>     At the last telco meeting, Jim asked for a to-do list of the tasks
>     needed to move communicator assertions forward. Please find below
>     a first draft of such a task list. Could we agree that this is a
>     good list? If you see something odd/missing, reply to this email
>     group.
>
>     _To-do list for communicator assertions
>     _
>     0) Gather evidence to support "no-one will be affected by
>     backwards incompatibility".
>        (e.g. chase Pavan, who volunteered to do this for major MPICH
>     users)
>     1) Change behaviour of MPI_COMM_DUP so that INFO keys are *not*
>     propagated to new comm.
>        (include AtoU: if you want to dup INFO use
>     MPI_COMM_DUP_WITH_INFO, with example)
>     2) Discuss whether attributes (plus, anything else?) should be
>     propagated by MPI_COMM_DUP.
>        (default presumption is yes, they should still be propagated).
>     3) Find all occurrence of language in the MPI Standard that
>     suggests INFO keys are hints.
>     a) Change or remove any generic statements like "INFO keys cannot
>     change semantics".
>        (e.g. change to "cannot change observable semantics" or remove)
>     b) For each occurrence, determine if it should continue to suggest
>     hint status
>        (e.g. a particular key, most likely for the I/O keys but maybe
>     also some RMA keys)
>
>     A) Convert ticket 381 into "make comm assertions doable" proposal
>     (by Jun 2015 - Chicago?)
>     B) Get "no wildcard" INFO keys proposal ready for formal reading
>     (by Jun 2015 - Chicago?)
>     C) Get "no ordering" INFO key proposal ready for formal reading
>     (by Jun 2015 - Chicago?)
>     D) Get "no cancel" INFO keys proposal ready for formal reading (by
>     Jun 2015 - Chicago?)
>     E) Discuss other INFO key proposals, e.g. "only wildcard", "no
>     non-blocking", "no underflow"
>
>     Cheers,
>     Dan.
>
>     On 13/03/2015 19:22, Daniel Holmes wrote:
>
>         Hi All,
>
>         The next point-to-point teleconference will be on Monday 16th
>         March 2015 at 11am Central US via webex.
>
>         Connection details are on the point-to-point wiki page:
>         https://svn.mpi-forum.org/trac/mpi-forum-web/wiki/PtpWikiPage
>
>         Agenda:
>         1) "Can INFO keys change the semantic behaviour of MPI?" issue
>         - following the discussion at the face-to-face meeting, we
>         seem to have a workable way forward on this issue!
>         2) New communicator INFO keys - it looks like these will be
>         allowed, so we should define a few and get a proposal ready
>         for the next face-to-face meeting
>         3) Progress on Arecv and Fsend or ReceiveReduce?
>         4) Other stuff?
>
>         Cheers,
>         Dan.
>
>
>
>
>
>     -- 
>
>     Dan Holmes
>
>     Applications Consultant in HPC Research
>
>     EPCC, The University of Edinburgh
>
>     James Clerk Maxwell Building
>
>     The Kings Buildings
>
>     Peter Guthrie Tait Road
>
>     Edinburgh
>
>     EH9 3FD
>
>     T: +44(0)131 651 3465
>
>     E:dholmes at epcc.ed.ac.uk  <mailto:dholmes at epcc.ed.ac.uk>
>
>       
>
>     *Please consider the environment before printing this email.*
>
>
>
>
>     _______________________________________________
>
>     mpiwg-p2p mailing list
>
>     mpiwg-p2p at lists.mpi-forum.org  <mailto:mpiwg-p2p at lists.mpi-forum.org>
>
>     http://lists.mpi-forum.org/mailman/listinfo.cgi/mpiwg-p2p
>
>
>
> -- 
> Dan Holmes
> Applications Consultant in HPC Research
> EPCC, The University of Edinburgh
> James Clerk Maxwell Building
> The Kings Buildings
> Peter Guthrie Tait Road
> Edinburgh
> EH9 3FD
> T: +44(0)131 651 3465
> E:dholmes at epcc.ed.ac.uk  <mailto:dholmes at epcc.ed.ac.uk>
>   
> *Please consider the environment before printing this email.*

-- 
Dan Holmes
Applications Consultant in HPC Research
EPCC, The University of Edinburgh
James Clerk Maxwell Building
The Kings Buildings
Peter Guthrie Tait Road
Edinburgh
EH9 3FD
T: +44(0)131 651 3465
E: dholmes at epcc.ed.ac.uk

*Please consider the environment before printing this email.*

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mpi-forum.org/pipermail/mpiwg-p2p/attachments/20150324/bbe9e6fa/attachment-0001.html>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: not available
URL: <http://lists.mpi-forum.org/pipermail/mpiwg-p2p/attachments/20150324/bbe9e6fa/attachment-0001.ksh>


More information about the mpiwg-p2p mailing list