Towards a Compiler Analysis for Parallel Algorithmic Skeletons

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

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

Abstract

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
PublisherACM
Pages174-184
Number of pages11
ISBN (Print)978-1-4503-5644-2
DOIs
Publication statusPublished - 24 Feb 2018
Event27th International Conference on Compiler Construction - Vienna, Austria
Duration: 24 Feb 201825 Feb 2018
https://cc-conference.github.io/18/

Conference

Conference27th International Conference on Compiler Construction
Abbreviated titleCC'18
CountryAustria
CityVienna
Period24/02/1825/02/18
Internet address

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

Cite this