Support for irregular problems

Runtime support for parallel execution of in-core irregular code is based on the Inspector/Executor technique introduced in CHAOS . A piece of pseudocode using this technique is shown in Fig.

Figure: The use of lip in a simple parallel C program with an in-core data array and an index array.

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

  /* Generate index array describing
   * relationships between user data */
    
  /* Inspector Phase (computes 
   * optimized communication pattern) */
   LIP_Localize(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( /* ... */ );

Figure: Irregular inspector in lip

In the Inspector Phase data references (from indirect arrays) are examined and translated either into references to the node's local data array (global to local index translation) or into references to the node's temporary buffer (referred to as ghost area). The latter case is tightly connected with schedule generation which is a data structure describing how communication is to be performed efficiently to bring desired data into ghost area. The Inspector is activated using LIP_localize() call and its idea is shown in Fig. .

The next step of parallelization is the Executor Phase. In this phase results of Inspector phase (including a schedule) are used to perform communication (that brings non-local data into ghost area and is done through a call to the LIP_Gather() routine) and then a computation is performed using translated indices and local data array with additional buffer space (ghost area). Following that, another communication has to be performed to scatter back results of the computation. The communication schedule is used again through a call to the LIP_Scatter() function.

Created by Katarzyna Zając