Irregular data distribution

Figure: Use of lip in a simple parallel C program with irregularly distributed in-core data array and index array.

  MPI_Init( /* ... */ );
  LIP_Setup( /* ... */ );

  * Generate index array describing
  * relationships between user data */
 
 /*Creation of data distribution*/
  LIP_create_hilbert_distribution_in_core(
                              datamap,...)
    
 /*Creation of communication pattern used 
   to move data */
  LIP_remap(bufmap,remapping_schedule,...) 
    
 /*Actual movement of data*/
  LIP_Gather(remapping_schedule,...)             
  
 /* Inspector Phase (computes 
  * optimized communication pattern) */
  LIP_Localize(datamap,schedule,... );

       /* Executor Phase (performs 
        * communication and computation) */

       /* gather non-local irregular data */
       LIP_Gather(schedule,... );
 
      /* perform computation on data */
       for ( i = /* ... */ )
       {
        k = edge[i];
        y[k] = f( x[k] );
       }

      /* scatterer non-local
       * irregular data (results) */
       LIP_Scatter(schedule,... );
  

       LIP_Exit( /* ... */ );
       MPI_Finalize( /* ... */ );

In order to achieve better load balancing and to minimize the communication phase, various techniques for creating data distribution were introduced.

At present, lip supports a coordinate-based partitioner using Hilbert's curve to determine what part of data should reside on the same node. The library supports both in- and out-of-core versions of the partitioner. Fig. shows pseudocode that uses the partitioner.

The most significant difference between Fig. and Fig. is the use of the LIP_create_hilbert_distribution_in_core() routine. This function activates an in-core partitioner. The routine results in creation of a special object called Datamap that stores information about the new distribution. Additionally, a schedule object is created which is used by the communication function LIP_Gather to actually redistribute data.

Created by Katarzyna Zając