<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 1 November 2013 13:40, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Done = false;<br>
FirstI = -1, LastI = -1;<br>
while (!Done) {<br>
  for (I = FirstI+1; I < N; ++I)<br>
    if (r[i] > 0) {<br>
      FirstI = I;<br>
      break;<br>
    }<br>
<br>
  for (; I < N && !page_bound(&m[i]) && ...; ++I) {<br>
    if (r[i] > 0)<br>
      LastI = I;<br>
  }<br>
<br>
  Done = I == N;<br>
<br>
  for (I = FirstI; I <= LastI; ...) {<br>
    // Run the scalar/vector loop sequence as before.<br>
  }<br>
}<br></blockquote><div><br></div><div>Hi Hal,</div><div><br></div><div>Even if you could do something like this, there is no guarantee that (Last - First) will be multiple of VF, or even bigger than VF, and you'll have to cope with boundary conditions on every external loop, which, depending on the distribution of r[] could be as many as half the size of r[] itself.</div>
<div><br></div><div>I can't see an algorithmically (compile-time or run-time) way to guarantee that the number of clusters will be small without scanning the whole array. So, even if you add such a check in run-time and only vectorize if the number of clusters is small, the worst case scenario will run twice as many times, (the initial check can be vectorized, as it's a read-only loop), but the later cannot. in the best case scenario, you'll have only a handful of loops, which will run in parallel.</div>
<div><br></div><div>Worst case: n/VF + n</div><div>Best case: n/VF + ammortized n/VF</div><div><br></div><div>For VF == 2,</div><div> * best case is as fast as scalar code, considering overheads.</div><div> * worst case is 50% slower</div>
<div><br></div><div>For VF == 4,</div><div> * best case is 50% faster than scalar code</div><div> * worst case is 25% slower</div><div><br></div><div>And all that, depends on each workload, so it'll change for every different set of arguments, which in an n-body simulation, changes dynamically.</div>
<div><br></div><div>cheers,</div><div>--renato</div></div></div></div>