[LLVMdev] Vectorization: Next Steps

[Preston Briggs]

On Mon, Feb 6, 2012 at 12:13 PM, Sebastian Pop <spop at codeaurora.org> wrote:
> [many things, but I'm only going to focus on one of them]
> Would you consider using Polly http://polly.grosser.es to avoid
> writing this code?

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.

If I look at all the ways I know how to sort in parallel, they all look
roughly like this simple counting sort:

 for (unsigned i = 0; i < buckets; i++)
   count[i] = 0;

 for (unsigned i = 0; i < n; i++)
   count[src[i]]++;

 start[0] = 0;
 for (unsigned i = 1; i < buckets; i++)
   start[i] = start[i - 1] + count[i - 1];

 #pragma assert parallel
 for (unsigned i = 0; i < n; i++) {
   unsigned loc = int_fetch_add(start + src[i], 1);
   dst[loc] = src[i];
 }


The 1st loop is trivially parallel.  I think Polly would recognize this and
do good things.

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.

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.

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.

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.

Preston
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120206/f35b79a7/attachment.html>