<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hi Mike,<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
Cheers,<br>
Dan.<br>
<br>
<div class="moz-cite-prefix">On 23/03/2015 17:04, Blocksome, Michael
wrote:<br>
</div>
<blockquote
cite="mid:CAA5EEA59BEBE04481F65B185DC47FAC962AC3@CRSMSX101.amr.corp.intel.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
span.EmailStyle19
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">In
ticket 463, what is the difference between “no_ordering” and
“any_order”?<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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?<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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?<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">That’s
enough for now .. Thanks!
</span><span
style="font-size:11.0pt;font-family:Wingdings;color:#1F497D">J</span><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Mike<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><a moz-do-not-send="true"
name="_MailEndCompose"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></a></p>
<div>
<div style="border:none;border-top:solid #E1E1E1
1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">From:</span></b><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">
mpiwg-p2p [<a class="moz-txt-link-freetext" href="mailto:mpiwg-p2p-bounces@lists.mpi-forum.org">mailto:mpiwg-p2p-bounces@lists.mpi-forum.org</a>]
<b>On Behalf Of </b>Daniel Holmes<br>
<b>Sent:</b> Monday, March 23, 2015 9:57 AM<br>
<b>To:</b> MPI WG Point To Point Communications working
group<br>
<b>Subject:</b> Re: [mpiwg-p2p] Next meeting: 16th March
2015 11am Central US<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-bottom:12.0pt">Hi Mike,<br>
<br>
Let's have the initial discussion on the email list and then
add relevant content to the appropriate ticket(s).<br>
<br>
Cheers,<br>
Dan.<o:p></o:p></p>
<div>
<p class="MsoNormal">On 23/03/2015 14:46, Blocksome, Michael
wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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”) ?</span><o:p></o:p></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Thanks,</span><o:p></o:p></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Mike</span><o:p></o:p></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1
1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">From:</span></b><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">
mpiwg-p2p [<a moz-do-not-send="true"
href="mailto:mpiwg-p2p-bounces@lists.mpi-forum.org">mailto:mpiwg-p2p-bounces@lists.mpi-forum.org</a>]
<b>On Behalf Of </b>Daniel Holmes<br>
<b>Sent:</b> Monday, March 23, 2015 7:01 AM<br>
<b>To:</b> MPI WG Point To Point Communications
working group<br>
<b>Subject:</b> Re: [mpiwg-p2p] Next meeting: 16th
March 2015 11am Central US</span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:12.0pt">Hi All,<br>
<br>
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.<br>
<br>
<u>To-do list for communicator assertions<br>
</u><br>
0) Gather evidence to support "no-one will be affected by
backwards incompatibility".<br>
(e.g. chase Pavan, who volunteered to do this for major
MPICH users)<br>
1) Change behaviour of MPI_COMM_DUP so that INFO keys are
*not* propagated to new comm.<br>
(include AtoU: if you want to dup INFO use
MPI_COMM_DUP_WITH_INFO, with example)<br>
2) Discuss whether attributes (plus, anything else?) should
be propagated by MPI_COMM_DUP.<br>
(default presumption is yes, they should still be
propagated).<br>
3) Find all occurrence of language in the MPI Standard that
suggests INFO keys are hints.<br>
a) Change or remove any generic statements like "INFO keys
cannot change semantics".<br>
(e.g. change to "cannot change observable semantics" or
remove)<br>
b) For each occurrence, determine if it should continue to
suggest hint status<br>
(e.g. a particular key, most likely for the I/O keys but
maybe also some RMA keys)<br>
<br>
A) Convert ticket 381 into "make comm assertions doable"
proposal (by Jun 2015 - Chicago?)<br>
B) Get "no wildcard" INFO keys proposal ready for formal
reading (by Jun 2015 - Chicago?)<br>
C) Get "no ordering" INFO key proposal ready for formal
reading (by Jun 2015 - Chicago?)<br>
D) Get "no cancel" INFO keys proposal ready for formal
reading (by Jun 2015 - Chicago?)<br>
E) Discuss other INFO key proposals, e.g. "only wildcard",
"no non-blocking", "no underflow"<br>
<br>
Cheers,<br>
Dan.<o:p></o:p></p>
<div>
<p class="MsoNormal">On 13/03/2015 19:22, Daniel Holmes
wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="margin-bottom:12.0pt">Hi All, <br>
<br>
The next point-to-point teleconference will be on Monday
16th March 2015 at 11am Central US via webex.
<br>
<br>
Connection details are on the point-to-point wiki page: <br>
<a moz-do-not-send="true"
href="https://svn.mpi-forum.org/trac/mpi-forum-web/wiki/PtpWikiPage">https://svn.mpi-forum.org/trac/mpi-forum-web/wiki/PtpWikiPage</a>
<br>
<br>
Agenda: <br>
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!
<br>
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
<br>
3) Progress on Arecv and Fsend or ReceiveReduce? <br>
4) Other stuff? <br>
<br>
Cheers, <br>
Dan. <o:p></o:p></p>
</blockquote>
<p class="MsoNormal"><br>
<br>
<br>
<br>
<o:p></o:p></p>
<pre>-- <o:p></o:p></pre>
<pre>Dan Holmes<o:p></o:p></pre>
<pre>Applications Consultant in HPC Research<o:p></o:p></pre>
<pre>EPCC, The University of Edinburgh<o:p></o:p></pre>
<pre>James Clerk Maxwell Building<o:p></o:p></pre>
<pre>The Kings Buildings<o:p></o:p></pre>
<pre>Peter Guthrie Tait Road <o:p></o:p></pre>
<pre>Edinburgh<o:p></o:p></pre>
<pre>EH9 3FD<o:p></o:p></pre>
<pre>T: +44(0)131 651 3465<o:p></o:p></pre>
<pre>E: <a moz-do-not-send="true" href="mailto:dholmes@epcc.ed.ac.uk">dholmes@epcc.ed.ac.uk</a><o:p></o:p></pre>
<pre> <o:p></o:p></pre>
<pre>*Please consider the environment before printing this email.*<o:p></o:p></pre>
<p class="MsoNormal"><br>
<br>
<br>
<o:p></o:p></p>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>mpiwg-p2p mailing list<o:p></o:p></pre>
<pre><a moz-do-not-send="true" href="mailto:mpiwg-p2p@lists.mpi-forum.org">mpiwg-p2p@lists.mpi-forum.org</a><o:p></o:p></pre>
<pre><a moz-do-not-send="true" href="http://lists.mpi-forum.org/mailman/listinfo.cgi/mpiwg-p2p">http://lists.mpi-forum.org/mailman/listinfo.cgi/mpiwg-p2p</a><o:p></o:p></pre>
</blockquote>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<pre>-- <o:p></o:p></pre>
<pre>Dan Holmes<o:p></o:p></pre>
<pre>Applications Consultant in HPC Research<o:p></o:p></pre>
<pre>EPCC, The University of Edinburgh<o:p></o:p></pre>
<pre>James Clerk Maxwell Building<o:p></o:p></pre>
<pre>The Kings Buildings<o:p></o:p></pre>
<pre>Peter Guthrie Tait Road <o:p></o:p></pre>
<pre>Edinburgh<o:p></o:p></pre>
<pre>EH9 3FD<o:p></o:p></pre>
<pre>T: +44(0)131 651 3465<o:p></o:p></pre>
<pre>E: <a moz-do-not-send="true" href="mailto:dholmes@epcc.ed.ac.uk">dholmes@epcc.ed.ac.uk</a><o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>*Please consider the environment before printing this email.*<o:p></o:p></pre>
</div>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
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: <a class="moz-txt-link-abbreviated" href="mailto:dholmes@epcc.ed.ac.uk">dholmes@epcc.ed.ac.uk</a>
*Please consider the environment before printing this email.*</pre>
</body>
</html>