Towards a Compiler Analysis for Parallel Algorithmic Skeletons

Tobias Edler von Koch, Stanislav Manilov, Chris Vasiladiotis, Murray Cole, Björn Franke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Parallelizing compilers aim to detect data-parallel loops in sequential programs, which – after suitable transformation – can be safely and profitably executed in parallel. However, in the traditional model safe parallelization requires provable absence of dependences. At the same time, several well-known parallel algorithmic skeletons cannot be easily expressed in a data dependence framework due to spurious depedences, which prevent parallel execution. In this paper we argue that commutativity is a more suitable concept supporting formal characterization of parallel algorithmic skeletons. We show that existing commutativity definitions cannot be easily adapted for practical use, and develop a new concept of commutativity based on liveness, which readily integrates with existing compiler analyses. This enables us to develop formal definitions of parallel algorithmic skeletons such as task farms, MapReduce and Divide&Conquer. We show that existing informal characterizations of various parallel algorithmic skeletons are captured by our abstract formalizations. In this way we provide the urgently needed formal characterization of widely used parallel constructs allowing their immediate use in novel parallelizing compilers.
Original languageEnglish
Title of host publicationProceedings of the 27th International Conference on Compiler Construction (CC2018)
Place of PublicationVienna, Austria
Number of pages11
ISBN (Print)978-1-4503-5644-2
Publication statusPublished - 24 Feb 2018
Event27th International Conference on Compiler Construction - Vienna, Austria
Duration: 24 Feb 201825 Feb 2018


Conference27th International Conference on Compiler Construction
Abbreviated titleCC'18
Internet address


Dive into the research topics of 'Towards a Compiler Analysis for Parallel Algorithmic Skeletons'. Together they form a unique fingerprint.

Cite this