Flattening a 3D array in c++ for use with MPI

Question

Can anyone help with the general format for flattening a 3D array using MPI? I think I can get the array 1 dimensional just by using (i+xlength*j+xlength*ylength*k), but then I have trouble using equations that reference particular cells of the array.

I tried chunking the code into chunks based on how many processors I had, but then when I needed a value that another processor had, I had a hard time. Is there a way to make this easier (and more efficient) using ghost cells or pointer juggling?

Answer 1

You have two options at least. The simpler one is to declare a preprocessor macro that hides the complexity of the index calculation, e.g.:

#define ARR(A,i,j,k) A[(i)*ylength*zlength+(j)*zlength+(k)]

ARR(myarray,i,j,k) = ARR(myarray,i+1,j,k) + ARR(myarray,i,j+1,k) + ...

This is clumsy since the macro will only work with arrays of fixed leading dimensions, e.g. whatever x ylength x zlength.

Much better way to do it is to use so-called dope vectors. Dope vectors are basically indices into the big array. You allocate one big flat chunk of size xlength * ylength * zlength to hold the actual data and then create an index vector (actually a tree in the 3D case). In your case the index has two levels:

• top level, consisting of xlength pointers to the
• second level, consisting of xlength arrays of pointers, each containing ylength pointers to the beginning of a block of zlength elements in memory.

Let's call the top level pointer array A. Then A[i] is a pointer to a pointer array that describes the i-th slab of data. A[i][j] is the j-th element of the i-th pointer array, which points to data[i][j][0] (if data was a 3D array). Construction of the dope vector works similar to this:

double *data = new double[xlength*ylength*zlength];
double ***A;

A = new double**[xlength];
for (int i = 0; i < xlength; i++)
{
   A[i] = new double*[ylength];
   for (int j = 0; j < ylength; j++)
      A[i][j] = data + i*ylength*zlength + j*zlength;
}

Dope vectors are as easy to use as normal arrays with some special considerations. For example, A[i][j][k] will give you access to the desired element of data. One caveat of dope vectors is that the top level consist of pointers to other pointer tables and not of pointers to the data itself, hence A cannot be used as shortcut for &A[0][0][0], nor A[i] used as shortcut for &A[i][0][0]. Still A[i][j] is equivalent to &A[i][j][0]. Another caveat is that this form of array indexing is slower than normal 3D array indexing since it involves pointer chasing.

Some people tend to allocate a single storage block for both data and dope vectors. They simply place the index at the beginning of the allocated block and the actual data goes after that. The advantage of this method is that disposing the array is as simple as deleting the whole memory block, while disposing dope vectors, created with the code from the previous section, requires multiple invocations of the free operator.