Parallelizing Irregular Algorithms: a Pattern Language

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.
Original languageUnknown
Title of host publicationConference on Pattern Languages of Programs
Publication statusPublished - 1 Jan 2011
EventConference on Pattern Languages of Programs -
Duration: 1 Jan 2011 → …


ConferenceConference on Pattern Languages of Programs
Period1/01/11 → …

Cite this