Search code examples
carraysmpisparse-matrix

MPI Gather Sparse Vector

Hi I have the result bool C array (size of sizeResults) and it is very sparse as most of the values are false. I am using MPI_GATHER to gather this array from all workers however it is very time consuming...

MPI_Gather(result, sizeResults, MPI_BYTE, result_final, sizeResults, MPI_BYTE, 0, MPI_COMM_WORLD);

is there a more efficient way to do this? Thanks!

Solution

  • I can think of several, depending on just how sparse your array is. One trivial method is to condense your array of bools into a bit array, reducing it to 1/8 of its original size.

    Other things you could do:

    1. Instead of Gathering the bool values themselves, Gatherv the indices of the true values. For instance, if a process has the array { T, F, F, F, F, F, T, F, F, T }, then it would send the array { 0, 6, 9 }.

    2. If you want to get creative, think of your array as consisting of segments, where a segment is defined as a true value followed by all the false values leading up to the next true value. Using the above example, your 3 segments would be { T, F, F, F, F, F }, { T, F, F }, and { T }. Now all you need to Gatherv from each process is the length of each segment. In fairness, this generally isn't any more efficient than method 1.