Memory access classification for vertical task parallelism

Jens Gustedt (1) , Maxime Mogé (1)

1 CAMUS - Compilation pour les Architectures MUlti-coeurS

We present a paradigm and implementation of a parallel control flow model for algorithmic patterns of two nested loops; an outer iteration loop and an inner data traversal loop. It is centered around memory access patterns. Other than dataflow programming it emphasizes on upholding the sequential modification order of each data object. As a consequence the visible side effects on any object can be guaranteed to be identical to a sequential execution. Thus the set of optimizations that are performed are compatible with C's abstract state machine and compilers could perform them, in principle, automatically and unobserved. We present two separate implementations of this model. The first in C++ uses overloading of the operator[] to instrument the memory accesses. The second in Modular C uses annotations and code transformations for the two nested loops. Thereby the code inside the loops may stay as close as possible to the original code such that optimization of that code is not impacted unnecessarily. These implementations show promising results for appropriate benchmarks from polybench and rodinia.

Mots clés: automatic parallelization; iterative algorithms; memory access classification; parallel control flow

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Jens Gustedt, Maxime Mogé. Memory access classification for vertical task parallelism. PDP 2019 - 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, Feb 2019, Pavia, Italy. ⟨hal-02046105⟩