[LLVMdev] Coarse-grained parallelism

[Tobias Grosser]

On 04/20/2011 08:05 AM, Andreas Wilhelm wrote:
> Am 19.04.2011 um 16:44 schrieb John Criswell:
>
>> On 4/19/11 5:57 AM, Andreas Wilhelm wrote:
>>> Hello,
>>>
>>> I found some code within the pool allocation project to identify
>>> parallelizable function calls.
>>> Unfortunately the functionality isn't part of the current release of
>>> poolalloc (in release 14 it was).
>>
>> Can you tell me in what file(s) this is implemented? I wasn't aware
>> that the poolalloc project had such an analysis.
>
> The automatic parallelization was implemented in
> poolalloc/lib/DSA/Parallelize.cpp. The pass uses the PDG of class
> PgmDependenceGraph to identify parallelizable function calls. Do you
> know something about the idea behind those code?
>>
>>>
>>> My intention is to estimate the parallelization-potential of
>>> sequential applications concerning coarse-grained parallelism.
>>> Can you tell me...
>>>
>>> 1. Why are classes of pollalloc, like the one for creating a Program
>>> Dependence Graph (DPG), not supported anymore?
>>
>> It's probably not supported because no one is using it. We primarily
>> use Automatic Pool Allocation as part of the SAFECode memory safety
>> compiler, so we haven't needed this functionality.
>>
>> If you'd like to try to get it working again, we'd welcome patches for
>> mainline poolalloc.
>>
>>> 2. Do you know any other existing tools or practices to identify
>>> parallelizable function calls?
>>
>> I don't work on automatic parallelization, so I'd prefer input from
>> others. That said, I believe the Polly framework and LLVM's memory
>> dependence analysis pass may be useful. As parallelizing C programs
>> will need points-to analysis, the DSA project (found within the
>> poolalloc source code) or the work of Calvin Lin and Ben Hardekopf
>> (http://www.cs.ucsb.edu/~benh/downloads.html) may be useful, too.
Hi Andreas,

sorry for replying slowly.

In respect of parallelizing function calls Polly may or may not help 
you. In case you want some interprocedural analysis or you want to 
detect if functions are 'pure' or 'readonly' Polly is probably not the 
right thing. It may be possible to use Polly to analyze functions and to 
give detailed information what a function touches, but this would need 
some work.

In case you have a list of function calls that are called in a loop and 
which are known to be pure or read-only, Polly will in many cases be 
able able to detect the parallel loop and to generate calls to the 
OpenMP runtime. The focus in Polly's automatic parallelization is 
currently on loop level parallelism.

Maybe you can give a little more details about what kind of function 
calls you want to parallelize?

If you want to investigate loop level parallelism as it may appear in 
image processing tools, augmented reality, ... Polly may help you.
What kind of programs are your currently looking into? Do you have some 
examples?

Cheers

Tobi