Yaakoub Y El Khamra <yye00@cct.lsu.edu>

Date

Abstract

This thorn implement processor-local reduction operations.

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. ai are the values that are reduced, i [1n].

count:
The number of values count := n

sum:
The sum of the values sum := iai

product:
The product of the values product := iai

sum2:
The sum of the squares of the values sum2 := iai2

sumabs:
The sum of the absolute values sum2 := i|ai|

sumabs2:
The sum of the squares of the absolute values sumabs2 := i|ai|2

min:
The minimum of the values min := miniai

max:
The maximum of the values max := maxiai

maxabs:
The maximum of the absolute values maxabs := maxi|ai|

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 + , and max, which is . We define the minimum of complex values by

min a + ib,x + iy := min a,x + imin b,y

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 := sumcount

norm1:
The L1 norm, i.e., the sum of the absolute values norm1 := sumabscount

norm2:
The L2 norm, i.e., the Pythagorean norm norm2 := sumabs2 count

norm_inf:
The L norm norm_inf := maxabs

4.3 Weighted Reduction Operations

It is often convenient to assign a weight wi to each value ai. In this case, the basic reduction operations are redefined as follows.

count:
The number of values count := iwi

sum:
The sum of the values sum := iwiai

product:
The product of the values product := exp iwi logai

sum2:
The sum of the squares of the values sum2 := iwiai2

sumabs:
The sum of the absolute values sum2 := iwi|ai|

sumabs2:
The sum of the squares of the absolute values sumabs2 := iwi|ai|2

min:
The minimum of the values min := miniwi0 : ai

max:
The maximum of the values max := maxiwi0 : ai

maxabs:
The maximum of the absolute values maxabs := maxiwi0 : |ai|

The notation miniwi0 : ai means: “The minimum of ai where i runs over all values where wi0”. 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

 

 Language:c
 Type: function