1 Introduction

A reduction operation can be defined 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, finding 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.

2 Numerical Implementation

The new local reduce thorn has several new features including index strides and offsets 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 offsets 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 definition 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 final 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.

3 Using This Thorn

Please refer to the TestLocalReduce thorn in the CactusTest arrangement.

4 Reduction Operations

4.1 Basic Reduction Operations

The following reduction operations are imlemented. $a_i$ are the values that are reduced, $i\in [1\dots <!--FUNCTION\; APPLICATION-->n]$.

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 <!--FUNCTION\; APPLICATION-->}{a}_i$$

max:

The maximum of the values

$$max:=\underset{i}{\max <!--FUNCTION\; APPLICATION-->}{a}_i$$

maxabs:

The maximum of the absolute values

$$maxabs:=\underset{i}{\max <!--FUNCTION\; APPLICATION-->}\left|a_i\right|$$

Note that the above definitions 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 define the minimum of complex values by

and define the maximum equivalently.

4.2 High-level Reduction Operations

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

average:

The algebraic mean of the values

$$average:=sum∕count$$

norm1:

The $L_1$ norm, i.e., the sum of the absolute values

$$norm1:=sumabs∕count$$

norm2:

The $L_2$ norm, i.e., the Pythagorean norm

$$norm2:=\sqrt{sumabs2∕count}$$

norm_inf:

The $L_{\infty }$ norm

$$norm\text{\_}inf:=maxabs$$

4.3 Weighted Reduction Operations

It is often convenient to assign a weight $w_i$ to each value $a_i$. In this case, the basic reduction operations are redefined 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 <!--FUNCTION\; APPLICATION-->\sum _i{w}_i\log <!--FUNCTION\; APPLICATION-->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 <!--FUNCTION\; APPLICATION-->}{w}_i\ne 0:a_i$$

max:

The maximum of the values

$$max:=\underset{i}{\max <!--FUNCTION\; APPLICATION-->}{w}_i\ne 0:a_i$$

maxabs:

The maximum of the absolute values

$$maxabs:=\underset{i}{\max <!--FUNCTION\; APPLICATION-->}{w}_i\ne 0:\left|a_i\right|$$

The notation $\underset{i}{\min <!--FUNCTION\; APPLICATION-->}{w}_i\ne 0:a_i$ means: “The minimum of $a_i$ where $i$ runs over all values where $w_i\ne 0$”. The definition of the high-level reduction operations does not change when weights are present.

5 Parameters

6 Interfaces

General

Implements:

localreduce

7 Schedule

This section lists all the variables which are assigned storage by thorn CactusNumerical/LocalReduce. Storage can either last for the duration of the run (Always means that if this thorn is activated storage will be assigned, Conditional means that if this thorn is activated storage will be assigned for the duration of the run if some condition is met), or can be turned on for the duration of a schedule function.

Storage

NONE

Scheduled Functions

CCTK_STARTUP

  localreduce_startup

  startup routine