On Mon, Feb 6, 2012 at 12:13 PM, Sebastian Pop <<a href="mailto:spop@codeaurora.org">spop@codeaurora.org</a>> wrote:<br>> [many things, but I'm only going to focus on one of them]<br>> Would you consider using Polly <a href="http://polly.grosser.es">http://polly.grosser.es</a> to avoid<br>
> writing this code? <br><br>My impression is that Polly (and polyhedral analysis generally) doesn't do want I want. But I'm happy to talk about it 'cause I might be wrong.<br><br>If I look at all the ways I know how to sort in parallel, they all look roughly like this simple counting sort:<br>
<br><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><font face="'courier new', monospace">  for (unsigned i = 0; i < buckets; i++)<br>    count[i] = 0;<br><br> for (unsigned i = 0; i < n; i++)<br>
    count[src[i]]++;<br>  <br> start[0] = 0;<br>  for (unsigned i = 1; i < buckets; i++)<br>    start[i] = start[i - 1] + count[i - 1];<br>  <br> #pragma assert parallel<br>  for (unsigned i = 0; i < n; i++) {<br>    unsigned loc = int_fetch_add(start + src[i], 1);<br>
    dst[loc] = src[i];<br>  }</font></blockquote><div><br></div><div>The 1st loop is trivially parallel.  I think Polly would recognize this and do good things.</div><div><br></div><div>The 2nd loop has a race condition that can be handled by using an atomic increment provided by the architecture, if the compiler knows about such things. I don't think Polly would help here.</div>
<div><br></div><div>The 3rd loop is a linear recurrence that can be rewritten and solved in parallel, if the compiler knows about such things. I don't think Polly would help here.</div><div><br></div><div>The 4th loop relies on the programmer to use both an explicit assertion and an explicit fetch-and-add intrinsic. I think both of these are outside of Polly's scope.</div>
<div><br></div><div>This is the sort of code I want to handle -- parallel code written by knowledgable programmers who're counting on the compiler to recognize parallel loops, recognize and rewrite recurrences and reductions, and insert synchronization where helpful, using a variety of directives to clarify their intent.</div>
<div><br></div><div>Preston</div><div><br></div>