Parallelizing Techniques for Irregular Problems

During execution of irregular loops there is a need to bring remote data into the local memory buffer. The techniques for solving the problem can be categorized as follows:

Fetch on demand

- the irregularly referenced data are brought to a processor's local memory when needed. This technique is very easy to implement, but it can only be used on machines with low communication latency as it results in highly inefficient communication. Optimization of this method can be achieved by data buffering.

Inspector/Executor

- this strategy involves generating two code phases for each loop specifying irregular computations. During the inspector phase indirect arrays are examined and optimized communication pattern is defined. Afterwards, the executor performs communication according to predetermined schemes and executes the actual computation.

The former method is rather easy and straightforward and it usually performs quite poorly due to the message startup cost. The latter requires a more complicated parallelizing scheme. However, in comparison to ''fetch on demand'' technique it produces much better results.

Created by Katarzyna Zając