Man page for reduction.1
Table of Contents

NAME

reduction - reduction recognition

SYNOPSIS

reduction [ options ] infile outfile

DESCRIPTION

The reduction program recognizes program reductions and puts annotations on the loops and SUIF instructions where the reductions occur. This pass expects two file specifications on the command line: first for the input file, then for the output file.

Basically a reduction is an associative computation accumulated to one location. The accumulated location is called the reduction variable in this documentation. The reduction program tries to recognize such reductions and annotates the corresponding reduction variables and enclosing FOR nodes. Later passes of the SUIF parallelizer decide whether to do parallel reduction and which loop to parallelize.

OPTIONS

-V n This sets the the verbosity level to the integer n. The default is verbosity level 0. At higher verbosity levels, more comments will be written to standard output about what reduction is doing. Currently verbosity levels above one have the same effect as level one.

-debug
This tells reduction to dump debugging information to the standard output.

SCOPE OF THE ANALYSIS

Currently four kinds of associative computations are supported, namely, summation, multiplication, minimum, and maximum. For each loop, reduction finds all read-modify-write operations to the same location and makes sure that the modify operation is one of the four associative computations mentioned above. It also guarantees that there are no other non-reduction accesses to that location in that loop or any inner loops. Other operands used in the reduction operations are examined by the usual dependence analysis.

A reduction variable can be a scalar variable or an array, which is read and written in the same loop body. For example, s, a[i], b[i,3], c[d[i]] can all be reduction variables. That is, the reduction program recognizes reductions in any direction.

The reduction pass puts reduction annotations on the enclosing FOR nodes as long as the associative and read-modify-write properties are preserved. It is up to the later passes of the SUIF parallelizer to choose which loop level to parallelize.

Multiple reductions are allowed. That is, the loop j in the following example can be parallelized:

for i
for j
A[j][3] = A[j][3] + ...
A[j][4] = A[j][4] + ...
B[j] = B[j] * ...
C[j] = max(C[j], ...)
D[j] = min(D[j], ...)
end j
end i

The reduction pass doesn't deal with read-modify-write operations spanning multiple instruction AST nodes. Therefore, a forward substitution pass must be run before this pass to handle reductions across multiple instruction AST nodes.

SEE ALSO

skweel(1), pgen(1), oynk(1), moo(1)

HISTORY

Reduction was written by Shih-Wei Liao.


Table of Contents