next up previous
Next: Optimization Methods Up: Issues in Irregular Computations Previous: Issues in Irregular Computations

Outline of Irregular Problems

The common feature of irregular codes is that they access data arrays through one or more levels of indirect indices that are not known until runtime so no optimization can be done by the compiler. Parallelizing such code for distributed-memory systems is a challenging problem of great importance. Application areas in which irregular code is found include unstructured multigrid fluid dynamic solvers , molecular dynamics simulations, Monte Carlo Simulations, N-body Simulations and many others. An example of an irregular problem is shown below:

int i;
int edge[N];
double x[M], y[M];

create_graph(edge1,edge2, N );

for (i = 0 ; i < N ; i++)
     y[edge2[i]] += x[ edge1[i] ];

The index arrays edge1 and edge2 are created during program execution (with a call to create_graph()) and thus their contents are not known until runtime. They are used to access data stored in data arrays x and y. When data arrays are distributed among processors, some of the indices point to the remote memory of other nodes. This results in additional communication during the calculation loop. In order to minimize communication latency, some kind of optimization needs to be performed. This cannot be done during the compilation phase as the index arrays are not defined at this stage.

next up previous
Next: Optimization Methods Up: Issues in Irregular Computations Previous: Issues in Irregular Computations
Created by Katarzyna Zając