Dynamic and Speculative Polyhedral Parallelization Using Compiler-Generated Skeletons

Alexandra Jimborean 1 Philippe Clauss 2, 3, 4 Jean-François Dollinger 2, 5 Vincent Loechner 2, 3 Juan Manuel Martinez 2, 5
2 CAMUS - Compilation pour les Architectures MUlti-coeurS
LSIIT - Laboratoire des Sciences de l'Image, de l'Informatique et de la Télédétection, Inria Nancy - Grand Est
ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : We propose a framework based on an original generation and use of algorithmic skeletons, and dedicated to speculative parallelization of scientific nested loop kernels, able to apply at run-time polyhedral transformations to the target code in order to exhibit parallelism and data locality. Parallel code generation is achieved almost at no cost by using binary algorithmic skeletons that are generated at compile-time, and that embed the original code and operations devoted to instantiate a polyhedral parallelizing transformation and to verify the speculations on dependences. The skeletons are patched at run-time to generate the executable code. The run-time process includes a transformation selection guided by online profiling phases on short samples, using an instrumented version of the code. During this phase, the accessed memory addresses are used to compute on-the-fly dependence distance vectors, and are also interpolated to build a predictor of the forthcoming accesses. Interpolating functions and distance vectors are then employed for dependence analysis to select a parallelizing transformation that, if the prediction is correct, does not induce any rollback during execution. In order to ensure that the rollback time overhead stays low, the code is executed in successive slices of the outermost original loop of the nest. Each slice can be either a parallel version which instantiates a skeleton, a sequential original version, or an instrumented version. Moreover, such slicing of the execution provides the opportunity of transforming differently the code to adapt to the observed execution phases, by patching differently one of the pre-built skeletons. The framework has been implemented with extensions of the LLVM compiler and an x86-64 runtime system. Significant speed-ups are shown on a set of benchmarks that could not have been handled efficiently by a compiler.
Type de document :
Communication dans un congrès
International Symposium on High-level Parallel Programming and Applications‎, HLPP, Jul 2013, Paris, France. 2013
Liste complète des métadonnées

Contributeur : Philippe Clauss <>
Soumis le : lundi 21 octobre 2013 - 11:21:40
Dernière modification le : jeudi 11 janvier 2018 - 06:23:13


  • HAL Id : hal-00825738, version 1



Alexandra Jimborean, Philippe Clauss, Jean-François Dollinger, Vincent Loechner, Juan Manuel Martinez. Dynamic and Speculative Polyhedral Parallelization Using Compiler-Generated Skeletons. International Symposium on High-level Parallel Programming and Applications‎, HLPP, Jul 2013, Paris, France. 2013. 〈hal-00825738〉



Consultations de la notice