Generic Irregular Computation

#define N (2 * 3 * 2 * 5 * 7 * 2 * 9)                                                
#define L (2 * N)                                                                      
                                                                                      
int                                                                                    
main(void)                                                                             
{                                                                                      
  double *x, *y;                                                                       
  int *perm;                                                                           
  int n = N, l = L;                                                                    
  int i;                                                                         
  double sum_x, sum_y;                                                              

  x    = malloc( l * (sizeof *x) );                                                    
  y    = malloc( n * (sizeof *y) );                                                    
  perm = malloc( n * (sizeof *perm) );                                                 
  generate_data(x, perm, l, 0, l, 0, n);                                                                                    
  /* irregular loops */                                                                 
  for (i = 0 ; i < n ; i++)                                                            
    y[i] = -x[ perm[i] ];                                                              
  for (i = 0 ; i < n ; i++)                                                            
    x[ perm[i] ] += y[i];                                                              
  for (sum_y = 0.0, i = 0 ; i < n ; i++)                                               
  {                                                                                    
    sum_y += y[i];                                                                     
  }                                                                                    
  printf( "The sum of %d elements of `y' is %g\n", n, sum_y );                         
for (sum_x = 0.0, i = 0 ; i < l ; i++)                                               
  {                                                                                    
    sum_x += x[i];                                                                     
  }                                                                                    
  printf( "The sum of %d elements of `x' is %g\n", l, sum_x );                         
free( perm );                                                                        
  free( y );                                                                           
  free( x );                                                                           
  return 0;                                                                            
} /* main */

In this simple program we have two data arrays: x[] and y[]. The first one is accessed through the indirect array perm[], while the latter is referenced in a regular way. The irregular loops that use array x[] do it in two ways: one performs reading data and the second one modifies it. In the next Section we will see how to parallelize these two kinds of loops.

Created by Katarzyna Zając