Hi Sanjoy,<div><br></div><div>Thanks for the update.</div><div><br></div><div>I reworked the code for analyseWeakZeroSIV, fixing bugs and exploiting the two special cases mentioned in the paper.</div><div>It's here: <a href="https://sites.google.com/site/parallelizationforllvm/weak-zero-siv-test" target="_blank">https://sites.google.com/site/parallelizationforllvm/weak-zero-siv-test</a></div>
<div><br></div><div>I'll rework analyseWeakCrossingSIV soon. I'll send you a note when it's ready.</div><div><br></div><div>The current code for analyseZIV is wrong, in that it sets</div><div><br></div><div><div>
<font face="'courier new', monospace"><b>
level->direction = Level::ALL;</b></font></div><div><font face="'courier new', monospace"><b> level->distance = diffSCEV;</b></font></div><div><font face="'courier new', monospace"><b> level->scalar = true;</b></font></div>
</div><div><br></div><div>Doesn't make sense, since ZIV tests have no induction variable and therefore no associated loop level.</div>
<div>Suggests some work on analyseSubscript (where it's assumed that the ZIV test relates to a loop)</div><div>and analysePair, which makes the same assumption.</div><div><br></div><div>In analysePair, there's some code that finds the innermost loop containing the source value and the innermost loop containing the destination value. Then it decides that if neither contains the other, then no dependence exists. That's not correct. Consider this example:</div>
<div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="'courier new', monospace"><b>for (i = 0; i < n; i++) {</b></font></div><div><font face="'courier new', monospace"><b> for (j = 0; j < m; j++)</b></font></div>
<div><font face="'courier new', monospace"><b> A[j][i] = ...</b></font></div><div><font face="'courier new', monospace"><b> for (k = 0; k < m; k++)</b></font></div><div><font face="'courier new', monospace"><b> A[k][i] = ...</b></font></div>
<div><font face="'courier new', monospace"><b>}</b></font></div></blockquote><div><br></div><div>Wolfe writes:</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><i>Data dependence distances and directions between the two bodies are computed only for the common loops, those that surround both bodies.</i></div>
</blockquote><div><br></div><div>So, we'll expect to find a loop-independent output dependence from the 1st store to the 2nd store, with direction vector [= | <]. And, since the outer loop carries no dependence, we could safely run it in parallel. Even better, we could fuse the two inner loops, then collapse the resulting inner loop with the outer loop and run the whole thing in parallel :-)</div>
<div><br></div><div>Embellishing the example slightly</div>
<div><blockquote style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:40px;border-top-style:none;border-right-style:none;border-bottom-style:none;border-left-style:none;border-width:initial;border-color:initial;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px">
<div><font face="'courier new', monospace"><b><br>for (i = 0; i < n; i++) {</b></font></div><div><font face="'courier new', monospace"><b> for (j = 0; j < m; j++)</b></font></div>
<div><font face="'courier new', monospace"><b> A[j][i][0] = ...</b></font></div><div><font face="'courier new', monospace"><b> for (j = 0; j < m; j++)</b></font></div><div><font face="'courier new', monospace"><b> for (k = 0; k < n; k++)</b></font></div>
<div><font face="'courier new', monospace"><b> A[j][i][k] = ...</b></font></div><div><font face="'courier new', monospace"><b>}</b></font></div></blockquote><div><br></div></div><div>we again find a loop-independent output dependence from the 1st store to the 2nd store, with direction vector [= | <]. The extra loop nesting doesn't change anything.</div>
<div>
<br></div><div>Here's a final variation:</div><div><div><blockquote style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:40px;border-top-style:none;border-right-style:none;border-bottom-style:none;border-left-style:none;border-width:initial;border-color:initial;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px">
<div><font face="'courier new', monospace"><b><br>for (i = 0; i < n; i++) {</b></font></div><div><font face="'courier new', monospace"><b> for (j = 0; j < m; j++)</b></font></div><div><font face="'courier new', monospace"><b> A[j][i][0] = ...</b></font></div>
<div><font face="'courier new', monospace"><b> for (j = 0; j < m; j++)</b></font></div><div><font face="'courier new', monospace"><b> for (k = 0; k < n; k++)</b></font></div><div><font face="'courier new', monospace"><b> A[j][i + 1][k] = ...</b></font></div>
<div><font face="'courier new', monospace"><b>}</b></font></div></blockquote><div><br></div></div></div><div>This time there's a loop-carried output dependence from the 2nd store back to the 1st store, with distance vector [1 | 0]. We found this by running the Strong SIV test on the middle subscript and ignoring the other two, since they don't refer to a common loop.</div>
<div><br></div><div>Finally, there's still no mention of loop-independent dependences. They're important! <span style="background-color:rgb(255,255,255);color:rgb(68,68,68);font-family:Arial,Verdana,sans-serif;font-size:13px;line-height:21px;text-align:left">When the dependence test is invoked, we need to pass in a flag indicating if a loop-independent dependence is possible; that is, if control can flow from the source to the destination without traversing a back edge. At the end of the dependence test, if dependence has not been disproved and the flag is set, we need to examine the direction vector. If all levels include the = direction, then we mark the dependence as loop independent.</span></div>
<div><br></div><div>Preston</div><div><br></div><div><br></div><div><br></div><div><br><div class="gmail_quote">On Thu, Apr 12, 2012 at 5:14 AM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
Here is a preliminary (monolithic) version you can comment on. This<br>
is still buggy, however, and I'll be testing for and fixing bugs over<br>
the next few days. I've used your version of the strong siv test.<br>
<br>
Thanks!<br>
<div><div>--<br>
Sanjoy Das.<br>
<a href="http://playingwithpointers.com" target="_blank">http://playingwithpointers.com</a><br>
</div></div></blockquote></div><br></div>