Interfaces for generalized vector

Collaboration diagram for Interfaces for generalized vector:

Modules
	Public declarations, typedefs and misc functions.
	Reduction/Transformation Operator Interface Functions (virtual).
	Implementation of Reduction/Transformation Operators.
	RTOp_Server.

Detailed Description

reduction/transformation operators in C.

The purpose of these C classes (structs) and functions is to allow users to specify arbitrary reduction/transformation operations on vectors without requiring the vectors to reveal their implementation details. The design is motivated partly by the "Visitor" patter (Gamma, 1995). Since this set of components is implemented in C it is very type unsafe and the declarations are somewhat verbose to avoid name clashes. Implementing this in C however makes this set of components accessible to a wider range of users and vector implementations. However, implementations of the operators in other languages (i.e. C++) is possible. All public declarations associated with this set of components starts with the prefix RTOp_ which is short for "Reduction/Transformation Operators".

This set of interfaces was designed to allow implementation of a distributed parallel application without the explicit knowledge by the application.

In the following discussion, v[k], x, y and z are abstract vector objects of dimension n. Users can define operators to perform reduction and/or transformation operations. Reduction operations must be applied over all of the elements of a vector and therefore requires communication between nodes in a parallel environment but do not change any of the vectors involved. Transformation operations don't require an operation to see an entire vector and therefore usually don't require any communication between nodes in a parallel environment. The targets of a transformation operation is a set of one or more vectors which are mutated in some way.

The idea is that the user may want to perform reduction operations of the form:

op(v[0]...v[*],z[0]...z[*]) -> reduct_obj

where reduct_obj is a single object based on a reduction over all the elements of the vector arguments, or transformation operations of the form:

op(v[0](i)...v[*](i),z[0](i)...z[*](i)) -> z[0](i)...z[*](i), for i = 1...n

The tricky part though, is that the reduct_obj object of the reduction operation may be more complex than a single scalar value. For instance, it could be a double and an int pair such as in the reduction operation:

min{ |x(i)|, i = 1...n } -> [ x(j_min), j_min ]

or it could perform several reductions at once and store several scalar values such as in:

min_max_sum{ x(i), i = 1...n } -> [ x(j_min), j_min, x(j_max), j_max, x_sum ]

Transformation operations are much simpler to think about and to deal with. Some off-the-wall examples of transformation operations that this design will support are:

max{ |x(i)|, |y(i)| } + |z(i)| -> z(i), for i = 1...n

alpha * |z(i)| / x(i) -> z(i), for i = 1...n

alpha * x(i) * y(i) + beta * z(i) -> z(i), for i = 1...n

Reduction operations present the more difficult technical challenge since they require information gathered from all of the elements to arrive at the final result. This design allows operator classes to be defined that can simultaneously perform reduction and transformation operations:

 op(v[0](i)...v[*](i),z[0](i)...z[*](i)) -> z[0](i)...z[*](i),reduct_obj
    , for i = 1...n

This design is based on a few assumptions about the reduction and transformation operations and vector implementations themselves. First, we will assume that vectors are stored and manipulated as chunks of sub-vectors (of dimension sub_dim) where each sub-vector is sufficiently large. This design supports dense strided sub-vectors (see RTOp_SubVector and RTOp_MutableSubVector) and is relatively flexible.

It is strictly the responsibilities of the vector implementations to determine how these operators are applied. For instance, if we are performing a transformation operation of the form:

op( x(i), y(i), z(i) ) -> z(i), for i = 1...n

where x, y, and z are distributed parallel vectors, then we would assume that the elements would be partitioned onto the various processors with the same local elements stored on each processor so as not to require any communication between processors.

In order to maintain the simplicity of the design and interfaces, only one real floating-point element type and one index type are supported. The type for the floating-point numbers and the type for the indices should be compatible with Fortran DOUBLE PRECISION and INTEGER so that these operations can be implemented (the guts anyway) in Fortran or applied to data created in Fortran. In essence, we want to allow mixed language programming from the start. To allow for more data types (such as single precision REAL or COMPLEX ) would make these interfaces much more complicated and would be too much of a burden for users and vector implementors to deal with. This set of datatypes will benefit the largest number of users.