Skip to main content


eCommons@Cornell >
Cornell University Graduate School >
Cornell Theses and Dissertations >

Please use this identifier to cite or link to this item:
Title: The Galois System: Optimistic Parallelization of Irregular Programs
Authors: Kulkarni, Milind Vidyadhar
Keywords: parallelism
irregular programs
automatic parallelization
Issue Date: 23-Jul-2008
Abstract: 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.
Appears in Collections:Cornell Theses and Dissertations

Files in This Item:

File Description SizeFormat
thesis.pdf1.71 MBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us