Speaker: Dr. Björn Franke from the University of Edinburgh

Title: Commutativity Characterization of Algorithmic Skeletons and Their Automated Detection in Sequential Legacy Codes

Abstract: Automatically parallelizing compilers aim to detect data-parallel loops in sequential programs, which – after suitable transformation – can be safely and profitably executed in parallel. However, additional parallelism exists in a plethora of other shapes such as task farms, divide & conquer, map/reduce and many more. These algorithmic skeletons, i.e. abstractions for commonly used patterns of parallel computation, differ substantially from data-parallel loops, which is why auto-parallelizers cannot exploit them. Unfortunately, algorithmic skeletons are informal programming abstractions and lack a formal characterization in terms of established compiler concepts. In our work, we develop compiler-friendly characterizations of popular algorithmic skeletons using a novel notion of liveness-based commutativity. We introduce hybrid static/dynamic analyses, which enable us to identify potential candidates for skeletons including task farms, map/reduce and divide&conquer. This analysis is implemented in the LLVMframework and evaluated against the SPEC CPU2006 benchmarks, where it finds profitably exploitable parallelism – often exceeding 50% of the sequential execution time – inaccessible to any existing parallelizing compilers.