## User-Defined Reductions

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;
```