<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"Lucida Grande";
panose-1:2 11 6 0 4 5 2 2 2 4;}
@font-face
{font-family:"Times New Roman \(Body CS\)";
panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
{font-family:"Lucida Grande \,sans-serif";
panose-1:2 11 6 0 4 5 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
p.xmsonormal, li.xmsonormal, div.xmsonormal
{mso-style-name:x_msonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle23
{mso-style-type:personal-reply;
font-family:"Lucida Grande",sans-serif;
color:windowtext;}
.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;}
/* List Definitions */
@list l0
{mso-list-id:235826938;
mso-list-template-ids:1970325936;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></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]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-family:"Lucida Grande",sans-serif">The paragraph in Sec 3.5 (reproduced below) talks about the case when two sends match one receive and another case where two receives match one send. In the first case, the receive can
get data only from the first send. In the second case, only the first receive can get the data from the send. That is what is meant by non-overtaking.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Lucida Grande",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Lucida Grande",sans-serif">“Messages are non-overtaking: If a sender sends two messages in succession to the same destination, and both match the same receive, then this operation cannot receive the second message
if the first one is still pending. If a receiver posts two receives in succession, and both match the same message, then the second receive operation cannot be satisfied by this message, if the first one is still pending. This requirement facilitates matching
of sends to receives.”<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Lucida Grande",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Lucida Grande",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Lucida Grande",sans-serif"><o:p> </o:p></span></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:12.0pt;color:black">From: </span></b><span style="font-size:12.0pt;color:black">"Hudson, Stephen Tobias P" <shudson@anl.gov><br>
<b>Date: </b>Thursday, March 12, 2020 at 4:09 PM<br>
<b>To: </b>"Thakur, Rajeev" <thakur@anl.gov>, "Larson, Jeffrey M." <jmlarson@anl.gov>, "discuss@mpich.org" <discuss@mpich.org><br>
<b>Cc: </b>"Navarro, John-Luke Nicolas" <jnavarro@anl.gov><br>
<b>Subject: </b>Re: [mpich-discuss] In-order messages<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Paraphrasing the discussion so far, my understanding is:<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Note: I am only thinking of the case where both messages have the same tag and go to the same destination processor.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Section 3.5 of the MPI standard mentions: "Messages are non-overtaking: "<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">I think this must mean that once the messages are in the receive buffer one cannot overtake the one infront. It is trying to make the point that your MPI_Recv cannot reach over message 1 and say
I want message 2 (the buffer is FIFO). But this is only in the receive buffer.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">However, the order the messages are received into the buffer (from the network) cannot be guaranteed to be the same as the order they were sent.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Is this correct?<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Many Thanks,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Steve<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="98%" align="center">
</div>
<div id="divRplyFwdMsg">
<p class="MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> Thakur, Rajeev <thakur@anl.gov><br>
<b>Sent:</b> Thursday, March 12, 2020 1:18 PM<br>
<b>To:</b> Larson, Jeffrey M. <jmlarson@anl.gov>; discuss@mpich.org <discuss@mpich.org><br>
<b>Cc:</b> Navarro, John-Luke Nicolas <jnavarro@anl.gov>; Hudson, Stephen Tobias P <shudson@anl.gov><br>
<b>Subject:</b> Re: [mpich-discuss] In-order messages</span> <o:p></o:p></p>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="xmsonormal"><span style="font-family:"Lucida Grande",sans-serif">Matching specifies which buffer the incoming message goes into. Two sends issued in order with the same tag and destination will match two receives issued in order with the same tag
or MPI_ANY_TAG at the destination. The two sends could take different paths through the network, one more congested than the other, and hence reach the destination out of order. But they will get placed in the intended buffers.</span><o:p></o:p></p>
<p class="xmsonormal"><span style="font-family:"Lucida Grande",sans-serif"> </span><o:p></o:p></p>
<p class="xmsonormal"><span style="font-family:"Lucida Grande",sans-serif">Rajeev</span><o:p></o:p></p>
<p class="xmsonormal"><span style="font-family:"Lucida Grande",sans-serif"> </span><o:p></o:p></p>
<p class="xmsonormal"><span style="font-family:"Lucida Grande",sans-serif"> </span><o:p></o:p></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="xmsonormal"><b><span style="font-size:12.0pt;color:black">From: </span>
</b><span style="font-size:12.0pt;color:black">"Larson, Jeffrey M." <jmlarson@anl.gov><br>
<b>Date: </b>Thursday, March 12, 2020 at 1:12 PM<br>
<b>To: </b>"Thakur, Rajeev" <thakur@anl.gov>, "discuss@mpich.org" <discuss@mpich.org><br>
<b>Cc: </b>"Navarro, John-Luke Nicolas" <jnavarro@anl.gov>, "Hudson, Stephen Tobias P" <shudson@anl.gov><br>
<b>Subject: </b>Re: [mpich-discuss] In-order messages</span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal"> <o:p></o:p></p>
</div>
<div>
<p class="xmsonormal">On 3/12/20 1:04 PM, Thakur, Rajeev wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="xmsonormal"><span style="font-family:"Lucida Grande ,sans-serif",serif">The standard specifies the order in which messages match, not complete. They can complete in any order.</span><o:p></o:p></p>
<p class="xmsonormal"><span style="font-family:"Lucida Grande ,sans-serif",serif"> </span><o:p></o:p></p>
<p class="xmsonormal"><span style="font-family:"Lucida Grande ,sans-serif",serif">Rajeev</span><o:p></o:p></p>
<p class="xmsonormal"><span style="font-family:"Lucida Grande ,sans-serif",serif"> </span><o:p></o:p></p>
<p class="xmsonormal"><span style="font-family:"Lucida Grande ,sans-serif",serif"> </span><o:p></o:p></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="xmsonormal"><b><span style="font-size:12.0pt;color:black">From: </span>
</b><span style="font-size:12.0pt;color:black">"Larson, Jeffrey M. via discuss" <a href="mailto:discuss@mpich.org">
<discuss@mpich.org></a><br>
<b>Reply-To: </b><a href="mailto:discuss@mpich.org">"discuss@mpich.org"</a> <a href="mailto:discuss@mpich.org">
<discuss@mpich.org></a><br>
<b>Date: </b>Thursday, March 12, 2020 at 12:46 PM<br>
<b>To: </b><a href="mailto:discuss@mpich.org">"discuss@mpich.org"</a> <a href="mailto:discuss@mpich.org">
<discuss@mpich.org></a><br>
<b>Cc: </b>"Larson, Jeffrey M." <a href="mailto:jmlarson@anl.gov"><jmlarson@anl.gov></a>, "Navarro, John-Luke Nicolas"
<a href="mailto:jnavarro@anl.gov"><jnavarro@anl.gov></a>, "Hudson, Stephen Tobias P"
<a href="mailto:shudson@anl.gov"><shudson@anl.gov></a><br>
<b>Subject: </b>[mpich-discuss] In-order messages</span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal"> <o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">Hello MPICH friends,</span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black"> </span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">Consider the simple two-rank MPI scenario:</span><o:p></o:p></p>
</div>
<div>
<ul style="margin-top:0in" type="disc">
<li class="xmsonormal" style="color:black;mso-list:l0 level1 lfo1;background:white">
<span style="font-size:12.0pt">Rank 1 is doing calculations and giving chunks of data to rank 0 using nonblocking sends and tag=0.</span><o:p></o:p></li><li class="xmsonormal" style="color:black;mso-list:l0 level1 lfo1;background:white">
<span style="font-size:12.0pt">When rank 1 is finished, it will send it's last data (or no data) with tag=1. </span><o:p></o:p></li><li class="xmsonormal" style="color:black;mso-list:l0 level1 lfo1;background:white">
<span style="font-size:12.0pt">Rank 0 is using probes to see when data is ready to be received. It receives with any tag, knowing when to stop receiving, or give new data when a tag=0 is received. </span><o:p></o:p></li></ul>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">Is it possible that rank 0 receives a tag=1 message when there are outstanding tag=0 messages?</span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black"> </span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">Looking at section 3.5 of the MPI standard lets me know that</span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black"> </span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">"Messages are non-overtaking: If a sender sends two messages in succession to the same destination, and both match the same receive, then this operation cannot receive
the second message if the first one is still pending."</span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black"> </span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">But I'm not sure if this applies to the above case. Is anytag "the same receive"? </span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">If rank 1 puts data in its buffer, doesn't the network have to be used to communicate that to the buffer of rank 0?</span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">While rank 1 is putting data into its buffer in order, is it possible that a tiny tag=1 message is registered in the rank 0 buffer before a massive tag=0 message? </span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black"> </span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">Thank you for your help,</span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal" style="background:white"><span style="font-size:12.0pt;color:black">Jeff</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<p>Hi Rajeev,<o:p></o:p></p>
<p><br>
What is the difference between matching and completing?<o:p></o:p></p>
<p>Does this mean that the quote from the standard that I gave means the messages between two fixed ranks could overtake each other? That is, they "match" but don't "complete" in the same order?<o:p></o:p></p>
</div>
</div>
</div>
</body>
</html>