Outside of the high-performance computing domain, many applications are irregular in the sense that opportunities to exploit parallelism change throughout the computation, due to the use of complex, pointer-based data structures such as lists and graphs. However, the parallel programming community has relatively little experience in parallelizing irregular applications, and we presently lack a deep understanding of the structure of parallelism and locality in the algorithms that underlie these applications. In this context, irregular algorithms pose a challenging problem to current parallelization methods and techniques.In recent years, the Galois project has proposed an approach for parallelizing irregular algorithms and applications that is based on a small set of simple abstractions. In this paper, we describe the Galois approach by means of a pattern language for parallel programming, thereby highlighting the key features of this approach, and elucidating more generally the concurrency patterns in irregular algorithms.
|Title of host publication||Conference on Pattern Languages of Programs|
|Publication status||Published - 1 Jan 2011|
|Event||Conference on Pattern Languages of Programs - |
Duration: 1 Jan 2011 → …
|Conference||Conference on Pattern Languages of Programs|
|Period||1/01/11 → …|