This page provides a summary of user-defined reductions in ZPL. If you find inconsistencies between this document and your use of ZPL, or bugs in user-defined reductions, please let us know at zpl-bugs@cs.washington.edu.

User-defined reductions are to be used when an appropriate built-in reduction does not exist. A user-defined reduction must be commutative and associative; if it is not, a wavefront computation may be more appropriate using the '@ operator.

To illustrate user-defined reductions, we present three
examples here. In the first example, we recreate a built-in
reduction, namely `min`

. Recall that this reduction
reduces an array to its minimum value which is stored in a
scalar.

To build the `min`

reduction as a user-defined
reduction, we need to write two procedures: an initialization
procedure and a reduction procedure. We must use overloading since
these procedures need the same name. The initialization procedure
creates a base result that has no effect regardless of the values
in the array. Thus, for examples, for the `min`

reduction, the initialization procedure returns the maximum value;
for the `plus`

reduction, the initialization procedure
returns zero since this adds nothing to the resulting sum. The
following program shows an example of a user-defined
`mymin`

reduction:

program test_mymin; config var n : integer = 8; region R = [1..n, 1..n]; procedure mymin() : double; begin return MAXDOUBLE; end; procedure mymin(d1, d2 : double) : double; begin if (d1 < d2) then return d1; else return d2; end; end; procedure test_mymin(); var A : [R] double; begin [R] A := (Index1-1) + (Index2-1)*n; [2,4] A := -2.0; [R] writeln(min<< A); [R] writeln(mymin<< A); end;

In the above program, we use the user-defined reduction
`mymin`

to find the minimum value in the array
`A`

. Of course, in this case, the resulting value is
the same as if we had used the built-in `min`

reduction.

Alternatively, we can write the procedures defining this reduction as follows:

procedure mymin(var d : double); begin d := MAXDOUBLE; end; procedure mymin(d1 : double; var d2 : double); begin if (d1 < d2) then d2 := d1; end; end;

In many cases, this is the preferred method since there is less copying of the result. One must remember that the function is often called during the course of the reduction and care should be taken to make it efficient. Note also that the first argument of the reduction operation should not be passed by reference. Since a reduction could be called over an expression, this must be a value parameter.

In certain cases, three procedures are needed to create a user defined reduction. If the resulting type is different than the type of the array, then three procedures are needed. The initialization procedure is needed and creates the initial value of the resulting type. Two reduction procedures are needed: (1) A local reduction procedure that takes an element of the array type and an element of the resulting type and returns an element of the resulting type, and (2) A global reduction procedure that takes two elements of the resulting type and returns an element of the resulting type.

The global function is needed for parallelism. Locally, each processor uses only the local reduction procedure to create reduced elements of the resulting type. These elements then must be combined using the global reduction procedure.

As an example, consider the `mini`

user-defined
reduction which finds the minimum value and returns not only the
minimum value, but also its position in the array. Example code
for this reduction is below:

program test_mini_reduce; config var n : integer = 10; region R = [1..n, 1..n]; var A : [R] double; type minloc = record d : double; x, y : integer; end; procedure mini() : minloc; var max : minloc; begin max.d := MAXDOUBLE; max.x := n+1; max.y := n+1; return max; end; procedure mini(d : double; x, y : integer; mini_so_far : minloc) : minloc; var new_mini : minloc; begin if d < mini_so_far.d then new_mini.d := d; new_mini.x := x; new_mini.y := y; return new_mini; end; return mini_so_far; end; procedure mini(mini1, mini2 : minloc) : minloc; begin if mini1.d < mini2.d then return mini1; else return mini2; end; end; procedure test_mini_reduce(); var ml : minloc; [R] begin A := (n - Index1 + 1) * (n - Index2 + 1); [n/2-1,n/2+1] A := 0.5; ml := mini<<(A, Index1, Index2); writeln(ml.d, ml.x, ml.y); end;

Alternatively, we could write these procedures using reference
parameters rather than return statements. Rather than show this
example, we provide one more example written using reference
parameters. In this case, it is especially important since the
resulting type is an indexed array. In this last example, we find
the five minimum values in an array. The procedures necessary to
implement this example are below. The number `vl`

is a
constant in our case equal to five.

procedure minvl(var maxv : vector); var i : integer; begin for i := 1 to vl do maxv[i] := MAXDOUBLE; end; end; procedure minvl(newval : double; var bestv : vector); var i, j : integer; tmpval : double; begin i := 1; while i <= vl & newval < bestv[i] do i += 1; end; if i > 1 then for j := 1 to i-2 do bestv[j] := bestv[j+1]; end; bestv[i-1] := newval; end; end; procedure minvl(var bestval1 : vector; var bestval2 : vector); var i : integer; begin for i := 1 to vl do minvl(bestval1[i], bestval2); end; end;

Note in the above code that the first parameter to the global reduction procedure is passed by reference. This is done for efficiency and does not preclude expressions being passed to the reduction. The vector type is defined as:

type vector = array[1..vl] of double;

If you have further questions about ZPL's support for user-defined reductions, please don't hesitate to contact us at zpl-info@cs.washington.edu.