next up previous contents index
Next: Irregular collective communications Up: A Distributed Array Communication Previous: Regular collective communications   Contents   Index

Reductions

Reduction operations take one or more distributed arrays as input. They combine the elements to produce one or more scalar values, or arrays of lower rank. Adlib provides a fairly large set of reduction operations, mimicking the reductions available as ``intrinsic functions'' in Fortran.

As a first example, the maxval operation simply returns the maximum of all elements of an array. It has prototypes

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ $$t$\verb$ maxval($$t$\verb$  ...

where $t$ now runs over all Java numeric types--that is, all Java primitive types except boolean. The discovered result is broadcast to the active process group, and returned as the result of the maxval() method. Other reduction operations with similar interfaces are minval, sum and product. Of these minval is minimum value, sum adds the elements of a in an unspecified order, and product multiplies them together.

The boolean reductions:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
... \\
\verb$ int count(boolean  ...

behave in a similar way: any returns true iff any element of a is true, all returns true iff all elements of a are true, and count returns a count of the number of true elements in a.

The function dotProduct used in some earlier examples is also logically a reduction, but it takes two aligned arrays as arguments and returns their scalar product--the sum of pairwise products of elements. The situation with element types is complicated because the types of the two arguments needn't be identical. If they are different, standard Java binary numeric promotions are applied before multiplying elements. The prototype is

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...$t_1$\verb$  ...

If either of $t_1$ or $t_2$ is a floating point type (float or double) the result type, $t_3$, is double). Otherwise the result type $t_3$ is long. The argument multiarrays must have the same shape and must be aligned. The result is broadcast to all members of the active process group. There is also a boolean form of dotProduct():

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...tProduct(boolean  ...

This returns the logical ``or'' of all the pairwise logical ``ands'' of elements.

The methods maxloc and minloc return respectively the maximum and minimum values of all elements of an array--similar to maxval and minval--but also output the index tuple in the array at which the extreme value was found. The prototypical forms are:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...minval(int [] loc, $$t$\verb$  ...

where loc is an ordinary Java array of length $R$, the rank of a. On exit it contains the (broadcast) global subscripts of the extreme value.

For each of the simple reductions that combine all elements of an array into a single value, there is a corresponding ``dimensional reduction'', which just reduces along a selected dimension of the input array, and outputs an array of values of rank one less than the input. The method maxvalDim(), for example, has the form:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...es, $$t$\verb$  ...

The dimension argument takes a value, $d$, in the range $0, \ldots,
R - 1$ where $R$ is the rank of a. The result array, res, must have rank $R-1$. It must be aligned with the input array a, with replicated alignment in the $d$th dimension of a. In other words, the distribution groups of a and res must be the same, and

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...erb$).isAligned(a.rng($$i$\verb$))$
\end{tabbing}\end{minipage}\end{displaymath}

for $i < d$, and

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...).isAligned(a.rng($$i + 1$\verb$))$
\end{tabbing}\end{minipage}\end{displaymath}

for $d \le i < R - 1$. The reductions minvalDim, sumDim, productDim, anyDim, allDim, countDim are defined in a similar way. The maxloc and minloc reductions have ``dimensional'' forms:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...oc, $$t$\verb$  ...

where the array loc has the same rank and alignment as res (since the reduction is in a single dimension, only one index value--for the specified dimension--needs to be returned per extreme value). Currently there is no ``Dim'' form of dotProduct().

Finally all the numeric simple reductions and dimensional reductions all have ``masked'' variants. These take an extra boolean array aligned with the source array. For example

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...al($$t$\verb$  ...

ignores all elements of a for which the corresponding element of mask is false.

A notable omission in the current version of the library is any facility for user-defined reduction operations. It also omits various arithmetic reductions that might seem natural in Java, such as bitwise, and, or, and xor. There is no fundamental reason for these omissions, and this might change in future releases.


next up previous contents index
Next: Irregular collective communications Up: A Distributed Array Communication Previous: Regular collective communications   Contents   Index
Bryan Carpenter 2003-04-15