A pattern language for parallelizing irregular algorithms
Pedro Monteiro, Miguel P. Monteiro · 2010
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 algorithms and applications. Four patterns are proposed: Amorphous Data-Parallelism, Data-Parallel Graph, Optimistic Iteration and In-Order Iteration.