<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">---------- Forwarded message ----------<br>From: Tobias Grosser <<a href="mailto:tobias@grosser.es">tobias@grosser.es</a>><br>
To: Dmitry Mikushin <<a href="mailto:dmitry@kernelgen.org">dmitry@kernelgen.org</a>><br>Cc: polly-dev <<a href="mailto:polly-dev@googlegroups.com">polly-dev@googlegroups.com</a>>, LLVM Developers Mailing List <<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>><br>
Date: Mon, 04 Feb 2013 17:53:11 +0100<br>Subject: Re: [LLVMdev] [Polly] Parallelizing outer loop containing inner reduction loop<br>On 02/04/2013 04:55 PM, Dmitry Mikushin wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Tobi,<br>
<br>
Thanks for looking into this!<br>
<br>
2013/2/4 Tobias Grosser <<a href="mailto:tobias@grosser.es" target="_blank">tobias@grosser.es</a> <mailto:<a href="mailto:tobias@grosser.es" target="_blank">tobias@grosser.es</a>>><br>
<br>
In any case, you seemed to have in some way convinced Polly to<br>
accept this code. Would you mind to share what you did?<br>
<br>
<br>
Sure. Aliasing is simply ignored. Instead we have substituted pointers<br>
and sizes for arrays and a special pass that converts memory accesses<br>
from every scop statement into ISL general form.<br>
</blockquote>
<br>
Interesting, why did you do this?<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Sorry, we are quite far<br>
from standard polly invocation process, maybe I should prepare some<br>
simplified plugin for testing purposes...<br>
</blockquote>
<br>
Or at least state that this is not standard polly. ;-) Then I would not keep trying to reproduce the problem.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Regarding your problem. As far as I understand, the problem is that<br>
the following code:<br>
<br>
for (i<br>
A[i] = 0<br>
for (j<br>
A[i] +=<br>
... = A[i]<br>
<br>
is changed by gcc (and other optimizations) to:<br>
<br>
for (i<br>
A[i] = 0<br>
tmp = A[i]<br>
<br>
for (j<br>
tmp +=<br>
<br>
A[i] = tmp<br>
... = A[i]<br>
<br>
<br>
Yes, exactly!<br>
<br>
<br>
This is a common optimization that unfortunately introduces a lot of<br>
dependences on tmp that block any direct parallelization. To<br>
parallelize the loop anyway we would need to expand the memory of<br>
tmp, such that each parallel thread has a private copy of 'tmp'.<br>
Deciding where and how to expand memory to enable further<br>
transformations is in general difficult such that I would normally<br>
run Polly before such optimizations are performed. Tough, in your<br>
case it may still be possible to parallelize the loop. To do this,<br>
you would need to ignore all dependences that can be removed by<br>
creating thread private copies of 'tmp'. If you are interested in<br>
having this implemented either open a bug report or give it a try<br>
yourself. I am happy to assist.<br>
<br>
<br>
Hm, how to create thread-private copies of tmp at that point and how<br>
useful could it be?</blockquote></blockquote><div><br></div><div style>Many auto-vectorizing compilers do such a thing (sometimes called "scalar expansion") as a way to attack otherwise parallel loops.</div><div>
</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
There are different approaches how to create thread private copies. You could aim to get back to the code in '1.ll' by creating an array with as<br>
many elements as there are iterations in the loop. That should be very general and independent of the platform specific parallel implementation. However, such a general implementation may introduce a lot of additional memory, which requires us to be careful with such transformations.<br>
</blockquote><div><br></div><div style>A better solution is to create an array with as many elements as there are threads, or, in the case of vectorization, as many elements as the length of the vector. Much less expensive!</div>
<div style><br></div><div style><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
> The problem is that platform-dependent view of<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
threads only steps into the process, once the loop is proved to be<br>
parallel. Before that, as far as I know, Polly/CLooG/ISL can't be aware<br>
of such things.<br>
</blockquote>
<br>
True. In general Polly does not know how parallelism is implemented exactly. Though we can perform some preparing transformations.<br>
<br>
> I thought more about pushing AllocaInst-s down closer to<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
the nested array header - would that work?<br>
</blockquote>
<br>
I don't think pushing AllocaInst-s into the loop is a better solution.<br>
In terms of memory behavior<br>
<br>
int A[i]; // stack allocated<br>
for i<br>
A[i] =<br>
<br>
and<br>
<br>
for i<br>
int *A = alloca(sizeof(int))<br>
*A =<br>
<br>
are the same. We really do not want to allocate a full temporary array on the stack.<br>
<br>
I see three options:<br>
<br>
0) We avoid optimizations that yield '2.ll'<br>
<br>
If we can (in some way) retain the version '1.ll', this is the<br>
best case and we should try hard to stay here.<br>
<br>
1) We malloc a temporary array<br>
<br>
In some cases it may be OK to do full memory expansion, e.g. <br>
by allocating the temporary array on the heap.<br>
<br>
2) Mark loops conditionally parallel<br>
<br>
We could mark loops parallel under the condition that certain<br>
memory references are privatized. For your use case, you could <br>
use the new loop.parallel meta-data and mark loops partial<br>
parallel. Meaning, you only mark the accesses parallel that<br>
are not involved in loop carried dependences. The remaining<br>
accesses then either need to be privatized or they need to<br>
be removed by mem2reg. For your example, mem2reg should remove<br>
the arrays, and the loop is then detected as parallel.<br>
<br>
Cheers<br>
Tobi<br></blockquote><div> </div></div></div></div>