$$Date$$

Abstract

This thorn implement processor-local reduction operations.

A reduction operation can be deﬁned as an operation on arrays (tuples) of variables resulting in a single number. Typical reduction operations are sum, minimum/maximum value, and boolean operations. A typical application is, for example, ﬁnding the minimum value in an $n$-dimensional array.

This thorn provides processor-local reduction operations only. Global reduction operations can make use of these local reduction operations by providing the necessary inter-processor communication.

The new local reduce thorn has several new features including index strides and oﬀsets for array indexing and full complex number support. Pending request, weight support can be enabled (there are some issues that a mask is essentially a weight with 1 or 0 value).

Modifying or extending this thorn is quite a simple matter. The heart of all the reduction operations is the large iterator macro in local_reductions.h. This iterator supports n-dimensional arrays with oﬀsets and strides. The iterator is used in all local reduction operators in this thorn. To add a reduction operator, or change an existing one, all that needs to be done is to change the actual reduction operation deﬁnition which is called from within the iterator to perform the reduction.

To use a custom local reduction operator from the new global reduction implementation, some values must be returned to the global reduction implementation, such as the type of MPI reduction operation that needs to be performed (MPI_SUM, MPI_MIN, MPI_MAX) and if the ﬁnal result should include a division by the total number of points used in the reduction. These are set in the parameter table with keys: mpi_operation and perform_division.

Please refer to the TestLocalReduce thorn in the CactusTest arrangement.

The following reduction operations are imlemented. ${a}_{i}$ are the values that are reduced, $i\in \left[1\dots n\right]$.

- count:
- The number of values
$$count:=n$$
- sum:
- The sum of the values
$$sum:=\sum _{i}{a}_{i}$$
- product:
- The product of the values
$$product:=\prod _{i}{a}_{i}$$
- sum2:
- The sum of the squares of the values
$$sum2:=\sum _{i}{a}_{i}^{2}$$
- sumabs:
- The sum of the absolute values
$$sum2:=\sum _{i}\left|{a}_{i}\right|$$
- sumabs2:
- The sum of the squares of the absolute values
$$sumabs2:=\sum _{i}|{a}_{i}{|}^{2}$$
- min:
- The minimum of the values
$$min:=\underset{i}{min}{a}_{i}$$
- max:
- The maximum of the values
$$max:=\underset{i}{max}{a}_{i}$$
- maxabs:
- The maximum of the absolute values $$maxabs:=\underset{i}{max}\left|{a}_{i}\right|$$

Note that the above deﬁnitions are for both real and complex values. For $n=0$, the result of the reduction operation is $0$, except for $product$, which is $1$, $min$, which is $+\infty $, and $max$, which is $-\infty $. We deﬁne the minimum of complex values by

$$min\left(a+ib,x+iy\right):=min\left(a,x\right)+imin\left(b,y\right)$$and deﬁne the maximum equivalently.

The following high-level reduction operations are also implemented. They can be deﬁned in terms of the basic reduction operations above.

- average:
- The algebraic mean of the values
$$average:=sum\u2215count$$
- norm1:
- The ${L}_{1}$
norm, i.e., the sum of the absolute values
$$norm1:=sumabs\u2215count$$
- norm2:
- The ${L}_{2}$
norm, i.e., the Pythagorean norm
$$norm2:=\sqrt{sumabs2\u2215count}$$
- norm_inf:
- The ${L}_{\infty}$ norm $$norm\text{\_}inf:=maxabs$$

It is often convenient to assign a weight ${w}_{i}$ to each value ${a}_{i}$. In this case, the basic reduction operations are redeﬁned as follows.

- count:
- The number of values
$$count:=\sum _{i}{w}_{i}$$
- sum:
- The sum of the values
$$sum:=\sum _{i}{w}_{i}{a}_{i}$$
- product:
- The product of the values
$$product:=exp\sum _{i}{w}_{i}log{a}_{i}$$
- sum2:
- The sum of the squares of the values
$$sum2:=\sum _{i}{w}_{i}{a}_{i}^{2}$$
- sumabs:
- The sum of the absolute values
$$sum2:=\sum _{i}{w}_{i}\left|{a}_{i}\right|$$
- sumabs2:
- The sum of the squares of the absolute values
$$sumabs2:=\sum _{i}{w}_{i}|{a}_{i}{|}^{2}$$
- min:
- The minimum of the values
$$min:=\underset{i}{min}{w}_{i}\ne 0:{a}_{i}$$
- max:
- The maximum of the values