Coarse-grained parallelism

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).

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?
  2. Do you know any other existing tools or practices to identify parallelizable function calls?

Thanks in advance

Andreas

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.

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.

  1. 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 () may be useful, too. – John T.

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.

  1. 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 () may be useful, too.

Thank you, I will look through your recommendations.

Andreas

Sadly, no. I don’t know anything about that code. I searched through the old CVS repository for the commit logs of this file. It appears to have been removed long ago because it fell into disuse.

– John T.

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

Hello Tobi,

my task is the automatic exploration of coarse-grained parallel-potential. In a first attempt I will disregard loop level parallelism and concentrate on function calls. Therefore I will collect some analysis information (dynamic as well as static), build a program-dependence-graph and evaluate it. The results shouldn't lead to automatic parallelization but to a recommendation for the user (which functions and how profitable). The main target for the approach are irregular applications with no specific sort of parallel characteristics.

Do you have a clue how to find dependencies between different function calls smartly? DSA provides such functionality but I don't know how practicable it is.

Greetings (from Passau)
Andreas

Hello Tobi,

my task is the automatic exploration of coarse-grained parallel-potential. In a first attempt I will disregard loop level parallelism and concentrate on function calls. Therefore I will collect some analysis information (dynamic as well as static), build a program-dependence-graph and evaluate it. The results shouldn't lead to automatic parallelization but to a recommendation for the user (which functions and how profitable). The main target for the approach are irregular applications with no specific sort of parallel characteristics.

If 2 function calls are known to be independent statically you can just
execute them in parallel. No need to give a hint to the user(?).

Interesting would be the following scenario (static only):
If you find 2 function calls that may not be independent, but have a
small set of conflicting accesses, you can point the conflict out to the
user and give him a hint (and an estimation of the achievable
performance gain perhaps).

Do you have a clue how to find dependencies between different function calls smartly? DSA provides such functionality but I don't know how practicable it is.

I'm not an expert on alias analysis, but you should always keep in mind
that the achievable precision of all AliasAnalysis is limited at compile
time (A 100% precise AA could solve the halting problem, I think). As
you mentioned a dynamic part: You could enhance your
alias information at run time.

Cheers,
Andreas