What is reduction variable? Could anyone give me some examples?

Question

What is reduction variable? Could anyone give me some examples?

Answer 1

Here's a simple example in a C-like language of computing the sum of an array:

int x = 0;
for (int i = 0; i < n; i++) {
    x += a[i];
}

In this example,

• i is an induction variable - in each iteration it changes by some constant. It can be +1 (as in the above example) or *2 or /3 etc., but the key is that in all the iterations the number is the same.

  In other words, in each iteration i_new = i_old op constant, where op is +, *, etc., and neither op nor constant change between iterations.

• x is a reduction variable - it accumulates data from one iteration to the next. It always has some initialization (x = 0 in this case), and while the data accumulated can be different in each iteration, the operator remains the same.

  In other words, in each iteration x_new = x_old op data, and op remains the same in all iterations (though data may change).

In many languages there's a special syntax for performing something like this - often called a "fold" or "reduce" or "accumulate" (and it has other names) - but in the context of LLVM IR, an induction variable will be represented by a phi node in a loop between a binary operation inside the loop and the initialization value before it.

Commutative* operations in reduction variables (such as addition) are particularly interesting for an optimizing compiler because they appear to show a stronger dependency between iterations than there really is; for instance the above example could be rewritten into a vectorized form - adding, say, 4 numbers at a time, and followed by a small loop to sum the final vector into a single value.

_{* there are actually more conditions that the reduction variable has to fulfill before a vectorization like this can be applied, but that's really outside the scope here}