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.