Classification d’accès mémoire pour la parallélisation verticale en tâches

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.Nous présentons un paradigme et une implémentation d’un modèle deflot de contrôle parallèle pour des motifs algorithmiques de deux nids de bouclesimbriqués; une boucle externe d’itération et une boucle interne de parcours dedonnées. Ce paradigme est basé sur les motifs d’accès mémoire. Contrairementà la programmation par flot de données, il assure l’ordre séquentiel des modificationsde chaque objet. Par conséquent, les effets de bords visibles sur tousles objets sont garantis identiques à une exécution séquentielle. Ainsi l’ensemble des optimisations effectuées sont compatibles avec la machine abstraite d’état de C, et les compilateurs peuvent les effectuer, en principe, de façon automatique et non-observée. Nous présentons deux implémentations distinctes de ce modèle. La premiere, effectuée en C++, utilise la surcharge de l’opérateur [] pour instrumenter les accès mémoire. La seconde, effectuée en Modular C, utilise des annotations et transformations de code pour les deux boucles imbriquées. Ainsi le code à l’intérieur des boucles peut rester aussi proche que possible de l’original pour ne pas impacter inutilement son optimisation. Ces implémentations montrent des résultats prometteurs pour des codes de référence tirés de polybench et rodinia