reduction discussion

[Razya Ladelsky]

Hi,

I'd like to start the discussion about how reductions are going to be
handled in PCP code.
There are two major parts that should be aware of reductions: data
dependence and code generation.
data dependence should basically ignore the dependences carried by this
reduction and code generation
is producing special code to handle reductions in the paralleized code.

I'll start the discussion with handling data dependency:
For simple reductions, containing only one stmt, producing a special
reduc_stmt in PCP could probably work,
for the data dependency part: data dep will ignore the def and use in that
stmt.
For more complex reduction patterns (although most are not supported by
GCC reductions detection yet),
I think the whole reduction cycle needs to be marked as part of a
reduction.
For example:

for(i)
{
a=b+C[i];
b=a+D[i];
}

both stmts are a part of the reduction cycle, hence should be considered
as such by data dependence analysis.
(and therefore allow parallelism for this loop)

Thanks,
Razya

[Albert Cohen]

Hi Razya,

Yes, this is very important now that Sebastian merged the
reductions-handling patch in the code generator.

Regarding the tags for reductions, in PCP and in GPOLY, I advocate for
tagging specific references (both LHS and RHS) and not statements. In
general, some GBBs may be involved into one or more reduction cycles
through some of their references only.

When a GBB is involved into more than one cycle, the tags should keep
track of some information regarding which cycle they belong to. Tagging
a specific LHS expression should be sufficient to keep track of those
precise cycles.

Finally, the API for dependence analysis should allow to make this
optimization (i.e., dropping reduction arcs) optional. For example, when
using all dependences including RAR input dependences for the sake of
locality analysis (an important information for heuristics), you do not
want to ignore reductions. There is probably a motivation for this in
the ability to select different safe/unsafe math modes depending on the
loop transformation involved (some transformations exercise only
commutation, which is safe on floats)...

Thanks,
Albert