# Contraintes d'OpenMP pour la parallélisation automatique à base de tâches

Julien Gaupp, Bérenger Bramas

► To cite this version:

Julien Gaupp, Bérenger Bramas. Contraintes d'OpenMP pour la parallélisation automatique à base de tâches. Conférence francophone d'informatique en Parallélisme, Architecture et Système (COMPAS 2025), Jun 2025, Bordeaux, France. hal-05293644

HAL Id: hal-05293644

https://inria.hal.science/hal-05293644v1

Submitted on 2 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Contraintes d'OpenMP pour la parallélisation automatique à base de tâches

Julien Gaupp et Bérenger Bramas

Université de Strasbourg,
Laboratoire ICube, équipe ICPS
Inria Nancy, équipe CAMUS
julien.gaupp@inria.fr

## Résumé

Les architectures modernes sont équipées de processeurs multi-cœurs qui nécessitent l'exécution d'applications parallèles pour être exploitées à pleine puissance. La parallélisation d'un programme peut être réalisée par des experts en utilisant, par exemple, la programmation basée sur les tâches. Cela peut aussi être réalisé de façon automatique. Dans cet article, nous abordons la parallélisation automatique basée sur les tâches et son implémentation avec OpenMP. Notre travail se focalise sur la gestion des dépendances des tableaux et l'évaluation de la profondeur lors de la création de tâches. Nous analysons différentes méthodes de gestion de ces aspects et évaluons leur impact en termes de coût supplémentaire. Nos résultats expérimentaux montrent que l'utilisation des itérateurs et de la clause if d'OpenMP entraîne un coût significatif. Nous identifions des alternatives plus efficaces qui permettent d'optimiser la performance des exécutions parallèles.

**Mots-clés** : compilation, openmp, CLang, tâches.

## 1. Introduction

Les processeurs modernes reposent sur des architectures multicoeurs, ce qui impose le développement d'applications parallèles pour exploiter pleinement leur potentiel. Cependant, concevoir des implémentations parallèles efficaces nécessite une expertise avancée et peut engendrer des défis en termes de maintenabilité.

Pour répondre à ces problématiques, la communauté scientifique en compilation a développé plusieurs approches visant à automatiser la parallélisation. Les méthodes classiques s'appuient principalement sur l'analyse des nids de boucles affines à l'aide du modèle polyédrique [3, 2]. Néanmoins, de nombreuses applications échappent à ce cadre, car elles ne peuvent pas être décrites de manière appropriée pour ce modèle.

Afin de surmonter cette limitation, nous avons proposé une méthode de parallélisation automatique basée sur les tâches [5]. Notre approche repose sur des transformations source à source, qui insèrent du code spécifique comme le ferait un développeur expert. Ces transformations exploitent des directives standardisées, facilitant ainsi l'utilisation de moteurs d'exécution tels qu'OpenMP [1].

OpenMP est aujourd'hui le standard de facto pour la parallélisation multicoeurs sur CPU [4, 6]. Cependant, OpenMP est une spécification qui ne décrit pas en détails tous les aspects liés à
son implémentation. De ce fait, les différentes bibliothèques d'OpenMP peuvent diverger dans leurs comportements et leur efficacité [8].

Dans cette publication, nous analysons deux fonctionnalités d'OpenMP qui peuvent compro-
mettre les performances attendues dans notre outil de parallélisation automatique : la clause
if du pragma *task* et l'utilisation des itérateurs dans la description des dépendances.<fnref n="1" />

## 2. Contexte

### 2.1. Parallélisation à base de tâches

La programmation à base de tâches consiste à décomposer un programme en unités de travail indépendantes, appelées tâches, et à décrire explicitement les dépendances entre elles [7]. Dans OpenMP, cette description des tâches est réalisée à la fois statiquement dans le code source à l'aide de pragmas, en ce qui concerne les parties du code qui composent des tâches et les types d'accès aux données, mais aussi dynamiquement en ce qui concerne les adresses des dépendances et le nombre de tâches. Dit autrement, l'intérieur des tâches est créé à la compilation, mais le graphe n'est construit qu'à l'exécution.

Cette description dynamique est réalisée en fournissant les dépendances entre tâches lors de leur soumission au moteur d'exécution. À ce moment, les adresses des variables impliquées, ainsi que leurs types d'accès (lecture, lecture-écriture, écriture), sont fournies. Ces informations permettent à OpenMP de construire un graphe de tâches représentant les relations de dépendance.

Une fois le graphe établi, les tâches sont exécutées en parallèle. Lorsqu'une tâche est prête (c'est-à-dire que toutes ses dépendances ont été résolues), elle est placée dans un conteneur. Les threads disponibles piochent alors des tâches dans ce conteneur pour les exécuter, assurant une exécution efficace et concurrente.

Les principaux compilateurs utilisés en HPC, tels que Clang, GCC et ICPC, intègrent des implémentations d'OpenMP. Toutefois, ces implémentations présentent parfois des variations qui peuvent influer sur leur comportement et leurs performances.

### 2.2. APAC

Apac est un compilateur source-à-source conçu pour la parallélisation automatique basée sur les tâches. Initialement, nous avons développé une première version reposant sur Clang Re-writer. Bien que cette version ait permis de valider le concept, elle mélangeait toutes les transformations dans une seule étape, ce qui rendait le code difficile à maintenir et à étendre.

Pour surmonter ces limitations, nous avons entièrement réimplémenté Apac en adoptant une approche modulaire basée sur un découpage en passes. Chaque passe effectue un ensemble limité de transformations spécifiques, telles que le désempilement des appels, le déplacement des variables de la pile vers le tas, la permutation des instructions, et d'autres optimisations (séparation des définitions des déclarations, substitution des *return* par des *goto*). Cette approche modulaire améliore la lisibilité et la maintenabilité du code tout en facilitant l'intégration de nouvelles fonctionnalités.

Après avoir appliqué ces transformations, Apac insère automatiquement des pragmas OpenMP pour activer la parallélisation. De plus, Apac intègre un système de profilage et de construction de modèles de performance. Ces outils permettent de déterminer, en fonction du contexte d'exécution, quand il est opportun d'activer les tâches afin d'optimiser les performances.

<footnote n="1">1. https://www.openmp.org/spec-html/5.0/openmpsu46.html</footnote>
## 3. Transformations étudiées

Apac réalise différentes transformations liées au langage source (C/C++), mais indépendantes du moteur d'exécution qui sera utilisé. Toutefois, d'autres transformations sont directement liées à ce dernier : l'activation des tâches conditionnelles et la déclaration de l'ensemble des dépendances. Ces deux aspects sont détaillés dans cette section.

### 3.1. Condition de taskification

Une tâche OpenMP est déclarée à l'aide de la directive suivante :

```
#pragma omp task [clause[ [, ]clause] ...]
```

Parmi les clauses disponibles, la clause `if(scalar-expression)` joue un rôle particulier. Si l'expression scalaire spécifiée est évaluée comme vraie, une tâche est créée et soumise au moteur d'exécution. En revanche, si l'expression est fausse, la tâche est tout de même créée, mais le thread qui l'a soumise ne poursuit son exécution qu'après avoir terminé celle de la tâche. Ce comportement s'apparente à une synchronisation implicite sur les dépendances, suivie de l'exécution immédiate de la tâche.

On pourrait logiquement s'attendre à ce que le surcoût induit par cette clause soit négligeable lorsque l'expression est évaluée à `false`. En d'autres termes, le code généré pour gérer cette situation pourrait simplement inclure un test conditionnel qui éliminerait tout traitement superflu lorsque l'expression `if` est évaluée comme fausse, minimisant ainsi les coûts de performance, comme illustré par le code suivant :

<figure><img src="image_2.png" /><figcaption>Code 1 – Exemple d'implémentation de la clause `if`.</figcaption></figure>

Si le surcoût associé à l'utilisation de `if(false)` est effectivement négligeable, il devient possible de désactiver la création de tâches sans avoir à dupliquer le code. Par exemple, si un grand nombre de tâches ont déjà été créées et qu'un thread entre dans une nouvelle section de création de tâches, il pourrait simplement passer la valeur `false` à la clause `if` de toutes les tâches de cette section. Cela empêcherait la création de nouvelles tâches tout en évitant toute synchronisation inutile, puisqu'aucune tâche n'aurait de prédécesseur.

Cependant, si le surcoût s'avère significatif, Apac devra adopter une stratégie différente. Dans ce cas, le compilateur devra générer deux versions distinctes du code source : une version séquentielle sans les pragmas, et une autre contenant les pragmas pour une exécution parallèle.
Cette approche garantirait des performances optimales en adaptant le code au contexte d'exécution, mais doublerait la taille du code source.

## 3.2. Déclaration des dépendances avec un itérateur

La déclaration des dépendances dans OpenMP peut être effectuée soit sur chaque élément individuellement, soit sur un ensemble d'éléments à l'aide d'un itérateur. Dans ce dernier cas, l'expression peut, par exemple, avoir la forme suivante :

```
depend(iterator(j=0:n), in : list[j])
```

Cette notation est équivalente à :

```
depend(in: list[0], list[1], ..., list[n-1])
```

Elle permet d'exprimer efficacement un grand nombre de dépendances et, surtout, d'exprimer un nombre de dépendances dynamiquement.

Cependant, la norme ne donne pas de détails sur la façon dont ce mécanisme doit être implémenté. Or faire une version optimisée peut s'avérer extrêmement difficile car cela nécessite de travailler à la fois au niveau du compilateur et au niveau de l'implémentation d'OpenMP. Il serait par exemple possible d'exprimer des dépendances sur des intervalles. A l'inverse, si les dépendances exprimées le sont sur chaque élément individuellement, cela peut induire un coût dramatique. Cette granularité excessive peut entraîner des surcoûts importants en termes de gestion des dépendances. Par exemple, lorsque cette approche est utilisée sur des tableaux de grande taille, on s'attend à ce qu'elle soit inefficace, car une dépendance est créée pour chaque élément de l'ensemble.

Dans Apac, nous ne faisons pas d'analyse de dépendances des boucles, et donc si une fonction *f* passe un tableau à une fonction *g*, elle va considérer que tous les éléments du tableau sont susceptibles d'être accédés.

Pour cette raison, nous proposons d'étudier des mécanismes alternatifs afin d'en évaluer les avantages et inconvénients.

### Macro-Dépendances

Dans cette approche, on déclare une dépendance sur un représentant et non sur les éléments de l'ensemble. Par exemple, en considérant que *tab* est un tableau et que l'on a les appels suivants *f*(tab), *g*(tab[4]) et *l*(tab[i]), on déclara la même dépendance pour les trois cas (par exemple sur *tab* ou *tab*[0]). Cette méthode est censée être très légère mais va enlever du parallélisme.

### Dépendances réelles

Dans cette approche on va déclarer les dépendances fines. Par exemple, en considérant que *tab* est un tableau et que l'on a les appels suivants *f*(tab), *g*(tab[4]) et *l*(tab[i]), on déclarera les dépendances sur *tab*[0:N], *tab*[4] et *tab*[i]), respectivement. Ainsi, il y aura une dépendance entre *f* et *g* (qui accèdent tous les deux l'élément 4) et une dépendance soit entre *g* et *l* ou *f* et *l* en fonction de la valeur de *i*. Cette approche va permettre un fort degré de parallélisme, mais elle va aussi déclarer des dépendances sur des ensembles entiers.

### Dépendances avec ensemble de représentants

Dans cette stratégie, on va statiquement construire les accès individuels, et considérer que les accès à tous les éléments ne doivent être protégés que pour ces éléments. Par exemple, en
considérant que `tab` est un tableau et que l'on a les appels suivants `f tab)`, `g (tab [4])` et `l (tab[i])`, on déclarera les dépendances sur `tab [4]`, `tab[i]`, `tab [4]` et `tab[i])`, respectivement. Ainsi, quand la fonction `f` est appelée, on ne déclare pas de dépendances inutiles. En revanche cette méthode ne fonctionnera pas s'il y a un changement de valeur des indices, par exemple si la variable `i` est modifiée entre `f` et `l`, dans ce cas, Apac doit utiliser une des autres méthodes.

## Dépendances Multi-modes

Dans cette stratégie, nous découpons les accès aux tableaux en zones, afin de scinder les sections dont les appels sont réalisés sur l'ensemble des éléments ou des éléments précis. Lorsque l'on passe d'une zone à une autre, qu'on passe d'un mode d'accès à tous les éléments à un mode d'accès à des éléments précis, on utilise un système de synchronisation. Afin de réaliser la synchronisation, on utilise un représentant qui peut être le pointeur du tableau.

## Dépendances sur des intervalles

Pouvoir gérer les intervalles de façon intelligente serait certainement une solution possible. Toutefois, nous ne l'étudions pas dans cette étude et laissons cela comme la prochaine tâche à réaliser.

Un exemple des différentes approches est décrit dans le Code 4 en annexe.

# 4. Étude des performances

## 4.1. Configurations

Nous avons réalisé des tests sur la machine suivante :

- **Dell** équipée du CPU Intel Core i5-13600H, de 16 GO de RAM et du compilateur GCC 12.2. Toutefois, nous utilisons `libomp` 15 de LLVM et non `libgomp` fourni avec GCC.

## 4.2. Cas tests

### Evaluation du if

Afin d'évaluer l'utilisation de la clause `if`, nous utilisons la fonction de Fibonacci. Cette fonction est simple et connue, si bien que son comportement est facile à interpréter. Nous fournissons en annexe, voir Code 2, le code de Fibonacci parallélisé avec OpenMP et dans lequel le parallélisme est limité par la clause `if`.

### Evaluation des dépendances sur les tableaux

Afin d'évaluer les différentes façons de déclarer des dépendances sur des sous-partie ou l'entièreté d'un tableau, nous avons créé un exemple très simple (voir Code 3 en annexe). Dans ce code, des boucles appellent des fonctions qui travaillent soit sur des éléments, soit sur le tableau. Dans ces boucles, nous avons simplement fait une attente active de 1 microseconde.

## 4.3. Résultats

### Évaluation du surcoût de l'utilisation du If

Dans la Figure 1, nous comparons le temps d'exécution de fibonacci sous plusieurs versions : séquentielle, parallèle générée par APAC et deux versions parallèles écrites à la main. Toutes les versions parallèles font un appel à la version séquentielle au-delà d'une certaine profondeur, à l'exception de la version *ParallelIf* qui utilise les clauses `If`. On peut observer que la version utilisant les clauses `If` est drastiquement plus lente que les autres versions, preuve du
surcoût de cette clause. Là où les deux autres versions parallèles présentent une accélération proche de x4.3. La seconde Figure 2 compare le temps d'exécution entre la clause If et notre version théorique pour 10⁸ tâches vides avec une condition fausse.

<figure><img src="image_3.png" /><figcaption>FIGURE 1 – Mesure du surcoût du If pour le calcul de Fibonacci (N=49). Le nombre au-dessus de chaque barre indique l'accélération par rapport à la version séquentielle.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>FIGURE 2 – Mesure du surcoût du If pour 10⁸ tâches vides.</figcaption></figure>

## Évaluation de la déclaration des dépendances

Nous présentons dans la Figure 3 les résultats de la comparaison des différentes méthodes pour déclarer des dépendances sur un tableau. Nous ne mesurons que le surcoût associé à la création des tâches et la gestion des dépendances (chaque tâche étant vide) sur un tableau de taille variable. Toutes les méthodes de définition des dépendances, à l'exception de celle utilisant l'itérateur, présentent une efficacité indépendante de la taille du tableau concerné. En revanche, l'utilisation de l'itérateur pour créer une dépendance sur chaque élément du tableau entraîne un surcoût important, et ce, même pour des tableaux de petite taille (1024 éléments). Cette méthode peut rester pertinente, car elle permet tout de même une gestion de dépendance précise et correcte, cependant d'autres méthodes, plus efficaces, le permettent aussi.

## 5. Conclusion

Dans cet article, nous avons étudié deux aspects importants d'OpenMP pour l'implémentation d'applications parallèles. Nous avons montré que désactiver le parallélisme en utilisant la condition if implique un surcoût important et rend cette approche inefficace. De la même manière, déclarer des dépendances sur tous les éléments d'un tableau, pour assurer la cohérence entre différentes tâches, engendre un surcoût considérable et ne peut pas être utilisé en pratique.

Ces démonstrations rappellent qu'il est essentiel de bien comprendre les impacts des différentes clauses et leurs implications. Ces connaissances nous permettront de générer du code parallèle automatiquement tout en maîtrisant les surcoûts.

Ainsi, dans un travail à venir, nous allons implémenter un mécanisme de double mode pour la déclaration des dépendances sur un tableau dans Apac.
<figure><img src="image_5.png" /><figcaption>FIGURE 3 – Temps d’exécution moyen pour différentes stratégies de déclaration des dépendances.</figcaption></figure>

Bibliographie

1. Ayguadé (E.), Copty (N.), Duran (A.), Hoeflinger (J.), Lin (Y.), Massaioli (F.), Teruel (X.), Unnikrishnan (P.) et Zhang (G.). – The design of openmp tasks. *IEEE Transactions on Parallel and Distributed systems*, vol. 20, n3, 2008, pp. 404–418.

2. Bastoul (C.). – Code generation in the polyhedral model is easier than you think. – In *Proceedings. 13th International Conference on Parallel Architecture and Compilation Techniques, 2004. PACT 2004.*, pp. 7–16. IEEE, 2004.

3. Jimborean (A.), Clauss (P.), Dollinger (J.-F.), Loechner (V.) et Martinez Caamaño (J. M.). – Dynamic and speculative polyhedral parallelization using compiler-generated skeletons. *International Journal of Parallel Programming*, vol. 42, 2014, pp. 529–545.

4. Kadosh (T.), Hasabnis (N.), Mattson (T.), Pinter (Y.) et Oren (G.). – Quantifying openmp : Statistical insights into usage and adoption. – In *2023 IEEE High Performance Extreme Computing Conference (HPEC)*, pp. 1–7. IEEE, 2023.

5. Kusoglu (G.), Bramas (B.) et Genaud (S.). – Automatic task-based parallelization of c++ applications by source-to-source transformations. *arXiv preprint arXiv:2105.10726*, 2021.

6. Pennycook (S. J.), Sewall (J. D.) et Hammond (J. R.). – Evaluating the impact of proposed openmp 5.0 features on performance, portability and productivity. – In *2018 IEEE/ACM International Workshop on Performance, Portability and Productivity in HPC (P3HPC)*, pp. 37–46. IEEE, 2018.

7. Thoman (P.), Dichev (K.), Heller (T.), Iakymchuk (R.), Aguilar (X.), Hasanov (K.), Gschwandtner (P.), Lemarinier (P.), Markidis (S.), Jordan (H.) et al. – A taxonomy of task-based parallel programming technologies for high-performance computing. *The Journal of Supercomputing*, vol. 74, n4, 2018, pp. 1422–1434.

8. Yu (C.), Royuela (S.) et Quinones (E.). – Taskgraph : A low contention openmp tasking framework. *IEEE Transactions on Parallel and Distributed Systems*, vol. 34, n8, 2023, pp. 2325–2336.
Annexe

<figure><img src="image_6.png" /><figcaption>Code 2 – Fibonacci avec la clause if.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Code 3 – Code d'étude pour l'évaluation des dépendances sur un tableau.</figcaption></figure>
1 // Fonctions qui utilisent tout le tableau ou un acces a un seul element
2 f tab;
3 g tab;
4 tab[4] += 1;
5 tab[5] += 1;
6 g tab;
7 tab[4] += 1;
8 tab[5] += 1;
9
10 // D declaration souhaitee
11 // Mode "block" on utilise tab[0] comme dependance sur le block entier
12 #task dep(inout:tab[0]) dep(in:tab)
13 f tab;
14 #task dep(in:tab[0]) dep(in:tab)
15 g tab;
16
17 #task dep(inout:tab) // Synchro
18 {}
19
20 // Mode "element" on utilise tab[x] comme dependance sur l'element x
21 #task dep(inout:tab[4]) dep(in:tab)
22 tab[4] += 1;
23 #task dep(inout:tab[5]) dep(in:tab)
24 tab[5] += 1;
25
26 #task dep(inout:tab) // Synchro
27 {}
28
29 // Mode "block" on utilise tab[0] comme dependance sur le block entier
30 #task dep(in:tab[0]) dep(in:tab)
31 g tab;
32
33 #task dep(inout:tab) // Synchro
34 {}
35
36 // Mode "element" on utilise tab[x] comme dependance sur l'element x
37 #task dep(inout:tab[4]) dep(in:tab)
38 tab[4] += 1;
39 #task dep(inout:tab[5]) dep(in:tab)
40 tab[5] += 1;

Code 4 – Les différents modes de déclaration de dépendances sur un tableau.