Generalized Task Parallelism
by
Kevin Streit, Johannes Doerfert, Clemens Hammacher, Andreas Zeller, Sebastian Hack
ACM Transactions on Architecture and Code Optimization, Pages 8:1-8:25, Volume 12, Number 1, January 2015.
Digital Library via DOI: 10.1145/2723164 - Local copy: Download as PDF file.
Abstract
Existing approaches to automatic parallelization produce good results in specific domains. Yet, it is unclear how to integrate their individual strengths to match the demands and opportunities of complex software. This lack of integration has both practical reasons, as integrating those largely differing approaches into one compiler would impose an engineering hell, as well as theoretical reasons, as no joint cost model exists that would drive the choice between parallelization methods. By reducing the problem of generating parallel code from a program dependence graph to integer linear programming, generalized task parallelization integrates central aspects of existing parallelization approaches into a single unified framework. Implemented on top of LLVM, the framework seamlessly integrates enabling technologies such as speculation, privatization, and the realization of reductions. Evaluating our implementation on various C programs from different domains, we demonstrate the effectiveness and generality of generalized task parallelization. On a quad-core machine with hyper-threading we achieve speed-ups of up to 4.6x.
BibTeX Entry
@article{streit-taco-2015,
title = "Generalized Task Parallelism",
author = "Kevin Streit and Johannes Doerfert and Clemens Hammacher and Andreas Zeller and Sebastian Hack",
year = "2015",
month = jan,
journal = "ACM Transactions on Architecture and Code Optimization",
number = "1",
pages = "8:1--8:25",
volume = "12",
doi = "10.1145/2723164",
}