The Galois System: Optimistic Parallelization of Irregular Programs

The last several years have seen multicore architectures become ascendant in the computing world. As a result, it is no longer sufficient to rely on increasing single-threaded performance to improve application performance; instead, programmers must turn to parallelization to realize the performance gains of multicore architectures. While much research over the past three decades have focused on parallelizing regular programs which operate over arrays and matrices, much less effort has been focused on irregular programs which operate over pointer-based data structures such as trees and graphs. In fact, it is not even clear that a significant amount of parallelism even exists in these applications. We identify a common type of parallelism that arises in irregular programs that operate over worklists of various kinds, which we call amorphous data-parallelism. Due to the data-dependent nature of these applications, static compiler analysis does not suffice to uncover any parallelism. Instead, successful parallelization requires speculative, or optimistic, parallelization. However, existing speculation techniques, such as thread-level speculation, are too low-level to recognize and extract useful parallelism from these applications. We present the Galois system for optimistic parallelization which uses high-level abstractions to express amorphous data-parallelism in irregular programs, and uses semantic properties of data structures to automatically parallelize such programs. These abstractions allow programs with amorphous data-parallelism to be written in a sequential manner, relying on run-time support to extract parallelism. We then develop abstractions which allow programmers to succinctly capture locality properties of irregular data structures. We show how these abstractions can be used to improve locality, improve speculation performance and reduce speculation overhead. We also present a novel parallel scheduling framework which allows programmers to leverage algorithm semantics to intelligently schedule concurrent computation, improving performance. We demonstrate the utility of the Galois approach, as well as the extensions that we propose, across a wide range of irregular applications demonstrating amorphous data-parallelism. We find that the Galois approach can be used to extract significant parallelism with low programmer overhead.DOE HPCS Fellowshi