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@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@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@epcc.ed.ac.uk
�
*Please consider the environment before printing this email.*




_______________________________________________
mpiwg-p2p mailing list
mpiwg-p2p@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@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@epcc.ed.ac.uk

*Please consider the environment before printing this email.*