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

Tue Mar 24 10:37:00 CDT 2015

Dan,

Thanks for the explanation. I think this information needs to be captured in the "advice to users" to help understand the difference between "what it does" vs "why to use it" ... simplified a bit, of course.

To summarize this for my own understanding: These INFO keys do not necessarily allow implementations to improve message match performance beyond what is already possible given current MPI match semantics. However, these INFO keys do allow implementations to potentially optimize fabric performance by relaxing the ordering requirement on the network.

Is that mostly correct? If so, then is the message match optimization only addressed in ticket #461?

Regarding the INFO keys themselves, "no_ordering" and "any_order" seem to be the same so this is just a choice in the name and how it is described.  The "single_use_matching" INFO key is slightly different .. or, at least the description is much more complicated so it seems to me like it should be different. What kind of optimizations are possible with this "single_use_matching" INFO key that are not possible with the others?

Thanks,
Mike

From: Daniel Holmes [mailto:dholmes at epcc.ed.ac.uk]
Sent: Tuesday, March 24, 2015 5:17 AM
To: Blocksome, Michael; MPI WG Point To Point Communications working group
Subject: Re: ticket 463 "any order communicator info key"

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! :)
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<mailto: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/7857ad73/attachment-0001.html>