A Pattern Language for Parallelizing Irregular Algorithms

In irregular algorithms, data set's dependences and distributions cannot be statically predicted. This class of algorithms tends to organize computations in terms of data locality instead of parallelizing control in multiple threads. Thus, opportunities for exploiting parallelism vary dynamically, according to how the algorithm changes data dependences. This paper presents the first part of a pattern language for creating parallel implementations of irregular parallel algorithms and applications. Four patterns are proposed: Amorphous Data-Parallelism, Data-Parallel Graph,Optimistic Iteration and In-Order Iteration.