Common construct types

Table of Contents

• Indexed arrays
  • Similar popular data structures
  • Indexed Array Example
  • Recommended structure
• Parallel dispatch

In this section, commonly-used construct types whose use may require specific explainations or recommendations are described.

Indexed arrays

In many instance data such as mesh connectivity requires managing a variable number of entries per data element. This is for example the case of faces → vertices connectivity. The average number of vertices per face is usually quite low, but the maximum number may be significantly higher, so using an array with regular stride would be very inefficient for some data sets.

A common solution to this problem is to use indexed arrays, in which an array containing data is supplemented by a second array containing the start indexes of entries in the data array for each element.

In C and C++ code, the natural indexing is zero-based, but one-based indexing may also be used for some arrays as a vestige of prior Fortran code, or for arrays using global numbers.

The recommendations are the following:

• Local index arrays should be zero-based.
• Global index arrays should be one-based. This should only concern indexes read from or written to file.
• When containing cell, face, or vertex connectivity information, data arrays may be either zero or one-based: zero based arrays are less error-prone so they should be preferred, but where element ids may be signed (so as to convey orientation information), one-based arrays are necessary. In a given structure, consistency is recommended, so if cells → faces connectivity requires one-based face numbers, an associated faces → vertices connectivity may also use one-based vertex numbers, even though vertices have no orientation.

Let us consider an array array_data indexed by a zero-based array_index array. The values of array_data associated with element *i_e*, are the values ranging from indexes *i_start = i_e* included to *i_end = i_e+1* excluded (past-the-end index).

The number of values associated with *i_e* is determined by: array_index[i_e+1] - array_index[i_e], whether the index is zero-based or one-based.

For an indexed array of n elements, the size the index array should thus be equal to n+1 (and not n as would be the case for regular 1-d or strided arrays), and the total size of array_data is equal to array_index[n] for a zero-based index, or array_index[n] - array_index[0] in general.

Similar popular data structures

Readers familiar with Compressed Sparse Row or similar matrix or graph representations may already have noted the similarity with the indexed arrays described here. In the case of CSR matrix structures, 2 data arrays are often associated with 1 row index: one array definining the column indices, and a second one defining the associated values.

This is in reality no different than using an indexed array as described here to define a faces → vertices connectivity, and also associating data (for example coordinates) to vertices.

In code_saturne, matrix non-diagonal terms usually correspond to cell faces, and the CSR matrix representation is very similar to that of a cells → faces connectivity, except for the fact that a standard CSR representation uses only "unsigned" column ids, whereas face numbers may be signed in the matching mesh representation so as to convey orientation (an alternative solution would be to use a separate array for orientation, in which case the similarity to CSR would be complete).

Indexed Array Example

We illustrate the use of an indexed array to define a faces → vertices connectivity for a simple surface mesh:

In this example we use 0-based (0 to n-1) numbering, as in most uses of indexed arrays in code_saturne.

Recommended structure

For mesh connectivities (adjacencies) that may be used across several functions, the cs_adjacency_t structure allows storing an manipulation indexed arrays.

Parallel dispatch

In C++ code using the .cpp extension, the cs_dispatch_context class may be used to run code defined as C++ lambda functions in parallel. The corresponding code can be written in a portable manner, but executed using different runtimes, such as OpenMP or CUDA.

Examples are provided in the source tree, in

• tests/cs_dispatch_test.cpp
• src/alge/cs_benchmark.cpp

Note that this class should not be called from code with the .cxx extension, as when using CUDA, that code will ve compiled using a different compiler, and using the class in both cases may confuse those compiler's avoidance of duplicating C++ template code instanciation.