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;

Further Questions?

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.