# Contributions pour l'utilisation des machines parallèles, réparties et hétérogènes à travers le prisme de la gestion des données partagées

Loïc Cudennec

► To cite this version:

Loïc Cudennec. Contributions pour l'utilisation des machines parallèles, réparties et hétérogènes à travers le prisme de la gestion des données partagées. Calcul parallèle, distribué et partagé [cs.DC]. Université de Rennes 1, 2022. tel-03798812

HAL Id: tel-03798812

https://theses.hal.science/tel-03798812

Submitted on 5 Oct 2022

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>
# THÈSE D'HABILITATION
## À DIRIGER LES RECHERCHES

présentée à

L'UNIVERSITÉ DE RENNES 1

spécialité

Informatique

soutenue par

Loïc CUDENNEC

le 28 septembre 2022

CONTRIBUTIONS POUR L'UTILISATION DES MACHINES PARALLÈLES, RÉPARTIES ET HÉTÉROGÈNES À TRAVERS LE PRISME DE LA GESTION DES DONNÉES PARTAGÉES

## JURY

### Rapporteurs

Camille

Frédéric

Raymond

COTI

DESPREZ

NAMYST

Professeure, Université du Québec à Montréal

Directeur de recherche, INRIA

Professeur, Université de Bordeaux

### Examinateurs

Michaël

Vania

Christine

KRAJECKI

MARANGOZOVA-MARTIN

MORIN

Professeur, Université de Reims Champagne-Ardennes

Maîtresse de Conférence, Université Grenoble Alpes

Professeure, Université de Rennes 1
# Résumé

Ces deux dernières décennies ont été marquées par des évolutions technologiques majeures dans le domaine des composants électroniques et des moyens de calcul informatiques. Premièrement, la miniaturisation de la gravure des transistors a permis d'offrir des capacités de calcul toujours plus importantes pour un facteur de forme équivalent et une enveloppe thermique en baisse. Dès 2007, les objets connectés, et notamment les smartphones deviennent des biens de consommation courants, accélérant l'innovation d'usage dans le quotidien, l'industrie et la défense. Deuxièmement, les limites physiques de la miniaturisation poussent les constructeurs à proposer de nouvelles architectures de calcul, privilégiant le parallélisme massif ou la spécialisation des unités de traitement. En 2009 la course est lancée pour concevoir des processeurs embarquant des milliers de cœurs de calcul. Quelques années plus tard, des accélérateurs spécifiques aux tâches d'apprentissage machine sont intégrés dans les centres de calcul et les systèmes embarqués, pour traiter de grands volumes de données et déployer des tâches complexes sur des objets communicants.

Une conséquence directe liée à cette grande diversité d'architectures de calcul est la complexification du modèle de programmation. Désormais, il est courant de recourir à un langage, une interface ou un système d'exploitation spécifique à chaque architecture. Ainsi, un programme écrit pour un processeur classique (CPU) devra être ré-écrit pour exploiter efficacement une nouvelle architecture telle qu'un accélérateur graphique (GPU), un accélérateur reprogrammable (FPGA) ou un processeur massivement parallèle (many-coeur). Cette opération est bien souvent laissée à la charge du développeur. Si des initiatives de normalisation et d'unification de modèles de programmation existent, elles se heurtent rapidement à la problématique de la performance face à l'hétérogénéité grandissante des systèmes.

Cette thèse d'Habilitation à Diriger des Recherches revient sur une dizaine d'années de contributions théoriques et pratiques aux systèmes distribués, parallèles, hétérogènes et embarqués. Le fil rouge de ces travaux est la gestion des données partagées, ou comment rendre les accès transparents pour le développeur d'application tout en restant indépendant de l'architecture matérielle. Les domaines d'application sont les processeurs massivement parallèles, les serveurs de calcul hétérogènes et les nouvelles architectures dédiées aux applications d'intelligence artificielle. Un ensemble d'outils pour l'optimisation des systèmes et l'aide à la décision sont présentés permettant une gestion efficace des ressources tant sur le plan de l'intensité calculatoire que de la consommation d'énergie. Enfin, des perspectives de recherche sont proposées, ancrées dans la profonde mutation en besoins de puissance de calcul et de maîtrise de l'énergie requis par le développement de l'intelligence ambiante.
Remerciements

Je tiens à remercier chaleureusement Camille COTI, Frédéric DESPREZ, Michaël KRAJECKI, Vania MARANGOZOVA-MARTIN, Christine MORIN et Raymond NAMYST pour avoir accepté de participer à mon jury d'HDR. Merci à eux d'avoir pris le temps d'étudier ce manuscrit, malgré la petite taille de la police de caractère :)

Maintenir un cap et construire une activité de recherche cohérente n'est pas chose aisée. Pour cela il faut établir un subtil mélange constitué de persévérance individuelle et d'émulsion collective. Je remercie donc avec une grande gratitude mes amis et collègues du Commissariat à l'Énergie Atomique et aux Énergies Alternatives ainsi que de la Direction Générale de l'Armement pour toutes les idées que nous avons pu échanger et qui constituent le fondement d'un travail de recherche. Je remercie tout particulièrement Caaliph ANDRIAMISAINA, Pascal AUBRY, Selma AZAIEZ, Sergiu CARPOV, Cyril FAURE, François GALÉA, Thierry GOUBIER, Julien HERVÉ, Hana KRICHEN, Stéphane LOUISE, Oana STAN, Thibaud TORTECH et Kods TRABELSI avec lesquels j'ai partagé une dizaine d'années d'activités foisonnantes, toujours passionnantes et synonymes de bonne humeur et de bienveillance !

Je remercie tout spécialement Safae DAHMANI et Erwan LENORMAND que j'ai encadrés en thèse et qui poursuivent de belles carrières dans le monde de la recherche. Les travaux présentés ici sont bien évidemment aussi le fruit de leur créativité ! Je souhaite autant de réussite à Cédric PRIGENT que je co-encadre avec Gabriel ANTONIU et Alexandru COSTAN.

J'exprime ma grande reconnaissance à ceux qui ont largement favorisé ce parcours, en particulier Renaud SIRDEY pour être venu dès ma soutenance de thèse en 2009 me proposer de travailler avec lui au CEA, Guy GOGNIAT et Henri-Pierre CHARLES pour les collaborations fructueuses lors de l'encadrement de thèses, Dominique CHAUVEAU pour son accueil remarquable à la DGA et son soutien déterminant à la réalisation de cette HDR. Merci aussi à Marie-Aline CAVARROC, Arnaud RAMEY et Eric MOLINÉ pour leur accueil dans leurs unités respectives, et le soutien concret dont ils ont fait preuve. Je souhaite aussi remercier Karine JONES pour son aide précieuse dans la préparation de la soutenance.

Enfin, un tel projet déborde inévitablement dans la vie privée et je remercie ma famille qui a été d'un grand soutien et une grande source d'encouragements tout au long de ce chemin.
<figure><img src="image_2.png" /></figure>

A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable [Lamport, 1987].

<figure><img src="image_3.png" /></figure>
# Table des matières

1 Introduction 9

2 Gestion des ressources à l'échelle des processeurs many-cœurs 13

2.1 Σ-C : un langage flot-de-données cyclo-statique 21

2.1.1 Une chaîne de compilation source-à-source 23

2.1.2 Réduire le parallélisme à la compilation 27

2.1.3 Calculer les accès aux tampons partagés 32

2.1.4 Programmation chimique sur Σ-C 35

2.2 Gestion de la cohérence des données sur many-cœur 38

2.2.1 Protocoles de cohérence de caches coopératifs 39

2.2.2 Évaluation analytique et simulateurs de réseaux sur puce 45

2.2.3 Aide à la décision pour le choix des protocoles de cohérence 47

2.3 Discussion 51

3 Données partagées pour les machines hétérogènes réparties 53

3.1 Une MVP (Mémoire Virtuellement Partagée) pour micro-serveur hétérogène 57

3.1.1 Éléments de conception de la MVP. 58

3.1.2 Modèle de programmation événementiel 61

3.1.3 Comparaison des performances de la MVP avec MPI (Message Passing Interface) et ZeroMQ 64

3.2 Maîtrise de la consommation d'énergie dans une MVP 67

3.2.1 Aide à la décision pour la configuration d'une MVP 67

3.2.2 Économie d'énergie dans les communications MPI, application à la MVP 71

3.2.3 Intégration d'accélérateurs matériels reprogrammables (FPGA (Field-Programmable Gate Array)) dans une MVP 75

3.3 Discussion 81

4 Conclusion et perspectives 83

4.1 Conclusion 83

4.2 Perspectives 84

Glossaire 88

Bibliographie 89
# Chapitre 1

## Introduction

L'histoire de l'informatique est marquée par diverses vagues de systèmes centralisés, parallèles et distribués. Depuis les années 1950, plusieurs architectures se sont ainsi succédées ou ont cohabité : les terminaux connectés à un ordinateur central, les ordinateurs personnels mis en réseau, les grappes et grilles de calculateurs, le modèle centralisé de l'informatique dans les nuages ou encore l'aspect massivement décentralisé de l'internet des objets et de l'ubiquité numérique. Ces solutions architecturales sont dirigées par les applications, les usages ainsi que les avancées technologiques. En premier lieu, nous pouvons observer des avancées technologiques importantes et rapides depuis l'avènement de la microélectronique, bousculant le domaine d'application de l'informatique numérique. Principalement orientée vers le calcul scientifique à ses débuts, l'informatique est aujourd'hui ancrée dans le quotidien, supportée par des centres de données gigantesques et la myriade annoncée d'équipements embarqués exécutant des applications de communication, de mobilité et d'assistance basées sur l'intelligence artificielle. Dans ce contexte, il n'est pas étonnant de constater que les architectures de calcul ont évolué significativement pour répondre aux objectifs et contraintes du moment.

Ces évolutions concernent plusieurs points : un premier point est le recours au **parallélisme** massif dans les unités de traitement. Cette évolution, popularisée avec l'arrivée des processeurs multi-cœurs au début des années 2000 est devenue courante dans tous les domaines applicatifs, de l'accélérateur graphique dédié au calcul haute-performance au processeur basse-consommation équipant les smartphones. Un deuxième point est la **distribution** des applications sur plusieurs nœuds de calcul. La mutualisation de ressources distantes interconnectées par un réseau est une technique largement éprouvée depuis les premières expérimentations menées sur les réseaux d'entreprises et les instituts de recherche dans les années 1980 puis généralisée avec le déploiement d'internet et l'interconnexion des centres de calcul. Un troisième point est l'**hétérogénéité** des architectures de calcul qui consiste à agréger des unités de traitement suffisamment différentes pour nécessiter un effort de programmation spécifique. L'hétérogénéité est actuellement en plein essor, poussée par les besoins en accélération de certains noyaux de calcul liés à l'intelligence artificielle.

Ces trois propriétés, le parallélisme des tâches, la distribution des calculs et l'hétérogénéité des unités de traitement ont des implications fortes sur l'organisation des calculs et la gestion des données partagées. Si ces problématiques sont largement étudiées par la communauté scientifique depuis de nombreuses années, l'émergence d'architectures combinant les trois propriétés nécessitent de nouvelles approches et innovations. C'est notamment le cas dans le domaine de l'embarqué, par exemple pour l'automobile avec les véhicules autonomes ou encore les satellites avec le *New Space*. Ces systèmes connaissent ces dernières années une évolution majeure sur le plan de l'électronique et de l'informatique : à l'origine pensés de manière monolithique, c'est-à-dire avec une architecture de calcul mono-cœur éprouvée pour des raisons de sécurité et de déterminisme à l'exécution, ils sont désormais des exemples d'intégration de nouvelles technologies sur plusieurs plans. Sur le plan du parallélisme, avec le recours à des processeurs multi-cœurs basse-consommation, sur le plan de la distribution des calculs avec l'interconnexion par des réseaux embarqués ou des réseaux sur puce de différentes unités de traitement spécialisées, et enfin sur le plan de l'hétérogénéité avec l'intégration d'accélérateurs graphiques, de processeurs many-cœurs ou de processeurs à la logique programmable. Ainsi pouvons-nous trouver des accélérateurs Nvidia dans les voitures pour des tâches liées à la conduite autonome ou au divertissement, et des FPGA Xilinx dans les satellites pour du traitement du signal ou de la reconnaissance d'objets.

Ces nouveaux systèmes hétérogènes ont en commun de profiter d'un changement de méthode de conception en ayant recours à des composants sur étagère. Ces produits à l'origine conçus pour des équipements grand public tels que les ordinateurs de bureau ou les smartphones, offrent un coût d'intégration significativement plus faible qu'une architecture dédiée produite en petit volume. Ils fournissent de plus bien souvent un environnement de développement mature et continuellement amélioré par les retours des utilisateurs. Ceci facilite leur intégration dans des projets plus flexibles, par exemple menés en suivant les méthodes agiles. En contrepartie, la multiplicité des architectures proposées rend l'établissement de normes de programmation illusoire et l'intégration de plusieurs unités différentes dans un même système conduit rapidement à un casse-tête de génie logiciel.

Pourtant, il existe un enjeu réel à fournir des méthodes et outils permettant une exploitation efficace de ces nouvelles architectures. La première raison est la **performance calculatoire**, dirigée par le besoin d'effectuer des calculs au plus proche des utilisateurs, notamment pour gagner en réactivité et rationaliser les communications face au déluge
de données. Une deuxième raison est la nécessité de maîtriser la **consommation d'énergie** afin de gagner en autonomie pour les systèmes fonctionnant sur batterie, ou tout simplement pour concevoir des systèmes plus respectueux des normes environnementales. Et force est de constater que l'aspect énergétique est devenu aussi important que la puissance de calcul ces dix dernières années, comme en témoigne la création des listes du GREEN500, mettant en valeur les super-calculateurs les plus efficaces sur le plan du **compromis calculatoire et énergétique**.

**Travaux présentés dans ce manuscrit.** La problématique principale étudiée réside dans la capacité à fournir une abstraction logicielle simple permettant l'exploitation efficace d'une plateforme matérielle complexe. Le fil rouge de ce manuscrit est la recherche du compromis entre la performance calculatoire et la consommation d'énergie pour les architectures massivement parallèles, distribuées et hétérogènes. Les travaux présentés interviennent sur deux plans : le modèle de programmation et le modèle de gestion des données. Ces deux approches sont en réalité intrinsèquement liées : le modèle de programmation détermine souvent la manière dont les données sont accédées ou tout du moins en limite les possibilités. Plusieurs exemples concrets sont étudiés dans ce manuscrit : un modèle de programmation flot-de-données pour un processeur many-cœur, un outil de décision pour les protocoles de cohérence des caches coopératifs et une mémoire virtuellement partagée logicielle pour architectures hétérogènes distribuées.

La réalisation de ces contributions s'est déroulée de 2009 à 2019 au sein de l'institut LIST du Commissariat à l'Énergie Atomique et aux Énergies Alternatives (le CEA) dans un contexte à cheval entre les activités d'un laboratoire de recherche académique et un département de R&D industriel. L'une des missions du CEA est d'apporter un soutien à l'industrie à travers le transfert de briques technologiques innovantes. Les thématiques traitées sont donc largement dirigée par les besoins des industriels, la part du financement étatique du CEA LIST étant très faible. Dès lors, conduire une activité de recherche consolidée sur plusieurs années n'est pas la norme et demande des efforts de justification spécifiques à l'institut. Pour autant, l'histoire du CEA et la variété de ses missions dans tous les domaines de la science conduisent à une multidisciplinarité singulière qui est une incroyable force pour imaginer de riches collaborations transverses.

Les contributions suivantes sont organisées en deux chapitres. Le chapitre 2 présente les travaux menés entre 2009 et 2015 pour l'exploitation des architectures many-cœurs. Le chapitre 3 présente l'ensemble des activités menées entre 2015 et 2020 autour de la conception d'une mémoire partagée logicielle pour les architectures hétérogènes. Quelques contributions annexes concernant le déploiement d'applications sur des chaînes de production industrielles ne sont pas présentées ici.

**Programmabilité des processeurs many-cœurs.** En 2009 est créé le laboratoire commun CEA-Kalray dont l'objectif est de proposer un environnement de programmation pour la puce many-cœur MPPA-256 et d'influencer l'architecture matérielle. Nous proposons un modèle de programmation flot de données basé sur une variation du modèle CSDF (Cyclo-Static Data-Flow) dans lequel des agents communiquent à travers des ports et des liens de communication, suivant une spécification des échanges fournie par l'application. Cette particularité permet d'effectuer de nombreuses vérifications lors de la compilation, notamment l'absence d'interblocages, un cadencement correcte des tâches ou核心 un dimensionnement possible des tampons de communication. Le langage de programmation associé, Σ-C, est supporté par une chaîne de compilation expérimentale qui a été transférée et industrialisée dans l'environnement de développement fourni par Kalray. Pour réaliser cette chaîne de compilation, de nombreux travaux ont été engagés par une équipe d'une dizaine de personnes pendant 3 ans. Dans ce manuscrit, après un état de l'art sur les many-cœurs et une présentation succincte du langage Σ-C, nous décrivons plus précisément deux étapes de la chaîne de compilation : 1) la compilation du parallélisme qui consiste à instancier, vérifier et optimiser le graphe de communication flot-de-données et 2) la réorganisation des accès aux données qui consiste à gérer les tampons partagés implémentant les canaux de communication entre agents. Enfin, pour conclure sur l'utilisation de la chaîne de compilation Σ-C, une troisième contribution est décrite traitant de l'exécution de programmes chimiques.

Un deuxième axe de travail visant à faciliter l'exploitation des many-cœurs porte sur la cohérence des caches. Les processeurs dotés d'un grand nombre de cœurs (plus d'une centaine) n'offrent pas de système matériel de cohérence des caches, ce qui empêche le déploiement d'applications écrites en mémoire partagée à l'échelle de la puce et contraint le développeur à exprimer à la main les transferts de données dans le code. Dans le manuscrit nous présentons des travaux permettant de déployer des protocoles de cohérence adaptés à ces grilles de calculateurs miniaturisées. Pour cela, plusieurs contributions sont présentées : 1) trois protocoles de cohérence des caches reposant sur l'aspect coopératif des cœurs voisins, 2) deux outils pour l'évaluation des protocoles de cohérence des caches, l'un basé sur une méthode analytique et le second sur un simulateur de réseaux sur puce et 3) un outil d'aide à la décision pour le choix et la configuration des protocoles de cohérence basé sur une méthode populationnelle.

**Programmabilité des architectures hétérogènes.** Entre 2014 et 2018 les projets européens H2020 FiPS et M2DC dans lesquels le CEA LIST est impliqué visent à concevoir une architecture micro-serveur, c'est-à-dire un serveur de calcul modulaire dont le matériel peut être configuré avec des processeurs et des accélérateurs hétérogènes. Les architectures ainsi conçues, commercialisées par Christmann en Allemagne, reflètent la tendance des systèmes intégrés actuels, à la frontière des centres de calcul et des systèmes embarqués. Les micro-serveurs ne disposent pas d'une mé-
moire centrale : les extensions supportant les unités de traitement sont interconnectées par un réseau intégré de type Ethernet. Les travaux présentés dans ce manuscrit concernent la conception et le déploiement d'une mémoire virtuellement partagée logicielle sur les micro-serveurs afin d'en abstraire la complexité matérielle pour le placement des tâches sur les ressources et la gestion des données partagées entre les nœuds.

Dans ce manuscrit, les travaux autour de la mémoire partagée sont présentés en deux parties : une première partie concerne la conception et l'efficacité du système. Elle comprend la présentation d'un modèle de programmation hybride inspiré de l'approche événementielle ainsi qu'une comparaison des performances d'une application écrite sur la mémoire partagée avec deux intergiciels populaires de passage de message, MPI et ZeroMQ. Une deuxième partie traite de la dépense d'énergie et des méthodes pour la maîtrise de la consommation sur une architecture hétérogène. Cette partie présente plusieurs contributions : 1) un outil d'aide à la décision pour le choix d'une topologie logique et le dimensionnement de la mémoire partagée basé sur des méthodes d'exploration de solutions par voisinage et menant à un compromis entre performance calculatoire et dépense énergétique, 2) la réduction de la consommation d'énergie dans les communications MPI avec une application à la mémoire partagée et 3) l'intégration d'accélérateurs matériels reprogrammables dans la mémoire partagée avec une application dans le cadre du projet H2020 LEXIS pour la mise en place de systèmes d'alerte aux tsunamis.

☐

<figure><img src="image_4.png" /></figure>
# Chapitre 2

## Gestion des ressources à l'échelle des
processeurs many-cœurs

Les processeurs many-cœurs, aussi appelés MPPA (Multi Purpose Processor Array), sont composés de plusieurs dizaines à plusieurs milliers de cœurs de calcul réunis sur une puce et interconnectés par un réseau sur puce NoC (Network on Chip). À l'instar des processeurs plus classiques les many-cœurs sont des processeurs dont les cœurs peuvent effectuer des opérations génériques et ce de manière indépendante. Ceci les différencie par exemple des accélérateurs de type GPGPU (General Purpose computing on Graphics Processing Unit) pour lesquels les calculs sont orchestrés par une machine hôte et dont le flot de contrôle d'une unité de calcul est possiblement contraint par celui des unités voivesines, notamment pour les instructions conditionnelles et de branchement. Les many-cœurs sont caractérisés par des capacités de calcul importantes dès lors que le parallélisme inhérent à l'architecture est efficacement exploité. De part leur conception basée sur l'accumulation d'éléments simples de calcul, de stockage et de communication, les many-cœurs offrent un excellent rapport entre la puissance de calcul et l'énergie consommée. Ces caractéristiques répondent à des contraintes liées aux contextes du HPC (High-Performance Computing) et des systèmes embarqués, permettant de nouvelles applications et le développement d'un contexte émergent, le HPEC (High-Performance Embedded Computing).

Le renouveau des puces massivement parallèles. Au milieu des années 2000, le monde de l'embarqué connaît un nouvel essor avec le développement de processeurs basse-consommation. Ces processeurs présentent un jeu d'instruction simplifié et des fréquences de fonctionnement plus faibles, en dessous de 700 MHz, là où les processeurs plus traditionnels font la course au delà des 3 GHz. En 2004, le processeur ARM1176JZF-S mono-cœur [arm Limited, 2004] doté du jeu d'instructions 32 bits ARMv6 propose une puissance de calcul suffisante pour exécuter un système d'exploitation complet, pour une consommation énergétique instantanée d'environ 1 W [Astudillo-Salinas et al., 2016]. Ce processeur équipe le premier Iphone 2G en 2007 [Patterson, 2011] et le premier Raspberry Pi en 2012 [Raspberry PI Foundation, 2017]. Ces deux équipements ont alors une influence majeure sur l'électronique grand public dans les télécommunications mobiles et dans le développement et le prototypage de systèmes embarqués, en robotique notamment. Pour répondre aux problématiques de l'embarqué, la tendance est alors de multiplier le nombre de cœurs basse-consommation ou de proposer des cœurs de calcul simplifiés. Par exemple en se basant sur des processeurs de générations plus anciennes telles que le premier Pentium P54C conçu au milieu des années 90 et dont le circuit est à la base des cœurs de calcul du Xeon Phi d'Intel [Barlas, 2015] en 2010. Ces circuits sont miniaturisés grâce à l'utilisation de technologies de gravure plus fines, ce qui permet de colocaliser un nombre important de cœurs sur une même puce et de réduire la puissance nécessaire au fonctionnement du processeur afin de réaliser des économies d'énergie. La puissance de calcul repose alors sur la multiplication des cœurs de calcul embarqués sur la puce.

L'approche n'est pas nouvelle : au début des années 1980 la capacité d'implantation des transistors sur une puce atteint une limite, freinant la conception d'architectures plus complexes. Le Transputer [Wikipedia, 2021] développé par la société Inmos au Royaume-Uni répond à cette problématique. Le principe est de se baser sur un processeur générique capable d'être directement interconnecté à d'autres processeurs sur une carte. Les Transputers sont intégrés dans une matrice pour former une architecture parallèle relativement intégrée pour l'époque. Cette organisation nécessite l'emploi d'un paradigme de programmation parallèle basé sur CSP (Communicating Sequential Processes) implémenté avec le langage occam, ce qui implique potentiellement la réécriture ou le portage des applications et qui n'est pas sans conséquences pour l'adhésion à un tel écosystème. L'évolution technologique dans le domaine de la microélectronique rend de nouveau possible la course à l'intégration des composants et limite l'intérêt pour le Transputer. Cependant, de nombreuses architectures bénéficieront des éléments de conception du Transputer, tels que l'accumulation d'unités de calcul, le réseau intégré et la gestion du multitâche au niveau matériel et logiciel.

Entre les années 1980 et 2010, les architectures parallèles et les systèmes répartis ont bénéficié de plusieurs engouements : les clusters Beowolf, des grappes de calculateurs fédérant des ordinateurs de bureau inutilisés dans les années 80, les grappes de calcul HPC dans les années 90, les grilles de calculateurs telles que définies par Foster [Foster and
<figure><img src="image_5.png" /><figcaption>FIGURE 2.1 – Prévisions pour l'évolution de la complexité des composants dans les systèmes embarqués grand public (SOC Consumer Portable Design Complexity Trends [ITRS, 2011] proposé par l'International Technology Working Group en 2010 (mis à jour en 2011). Figure issue du rapport.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIGURE 2.2 – Prévisions pour l'évolution du nombre d'unités de calcul pour les équipements embarqués et les micro-serveurs (SOC Consumer Portable Design Complexity Trends [ITRS2.0, 2015] proposé par l'International Technology Working Group en 2015. Données compilées à partir du rapport.</figcaption></figure>
Kesselman, 2004] dans les années 2000, l'émergence des processeurs multi-cœurs au milieu des années 2000 et les GPU (Graphics Processing Unit) appliqués au rendu graphique et au calcul numérique (GPGPU).

À la fin des années 2000, alors que la conception des processeurs génériques se heurte aux limites atteintes par l'augmentation de la fréquence d'horloge et la dissipation thermique, les processeurs many-cœurs apparaissent comme une architecture naturelle, faisant une nouvelle fois appel au parallélisme massif pour pallier les problèmes rencontrés par l'approche plus centralisée. Les prévisions émises par l'International Technology Working Group en 2010 dont est issue la figure 2.1 anticipent une croissance géométrique du nombre de cœurs de calcul dans les puces embarquées : de quelques dizaines de cœurs en 2010 à plus d'un millier de cœurs en 2020. Si ces prévisions s'avèrent aujourd'hui large- ment surestimées dans le domaine de l'électronique grand public, elles témoignent d'un engouement important pour cette dynamique de parallélisation massive des processeurs. Une version plus tempérée de ce rapport est proposée en 2015 (les résultats sont compilés dans la figure 2.2), dans lequel les many-cœurs ne sont plus pressentis pour équiper les systèmes embarqués grand public, mais plutôt les architectures de type micro-serveur hétérogènes, comme développé dans le Chapitre 3. Le nombre de cœurs reste cependant modeste, ne dépassant pas la centaine à l'horizon 2025. Les many-cœurs de plus grande taille ne disparaissent pas pour autant et se retrouvent dans des domaines spécifiques : les super-calculateurs et les systèmes embarqués autonomes.

**Panorama des many-cœurs.** La table 2.1 présente plusieurs processeurs many-cœurs conçus depuis le milieu des années 2000. Cette table a été construite en collectant les informations librement accessibles, publiées dans des conférences et journaux, sous forme de fiches techniques ou de sites collaboratifs. Elle permet de dégager plusieurs tendances concernant les choix de conception des many-cœurs sur les critères de taille de circuit, de puissance et de consommation, ainsi que de présenter les principaux acteurs de cet écosystème technologique. Une première observation concerne le nombre de cœurs : pendant la première décennie la stratégie consiste à explorer des architectures comportant un grand nombre de PE (Processing Element) (les cœurs de calcul). De quelques dizaines de cœurs pour les premières architectures proposées par Tilera et Intel en 2007, à plus de 2000 cœurs pour le processeur conçu par PEZY Computing en 2017. Il semble que la course au nombre de PE marque ensuite une pause : les constructeurs se concentrent sur les unités d'accélération spécialisées pour certains noyaux de calcul rencontrés dans les applications en IA (Intelligence Artificielle), tels que les convolutions et la rétropropagation de gradients pour l'apprentissage automatique (ML (Machine Learning)). Par exemple l'évolution du processeur MPPA de Kalray montre une diminution importante du nombre de cœurs entre Bostan en 2015 (256 cœurs) et Coolidge en 2020 (80 cœurs, mais auxquels viennent s'adosser des accélérateurs vectoriels pour le calcul sur les tenseurs utilisés en ML).

Une deuxième observation concerne les objectifs en terme de performance par unité d'énergie consommée, ce qui détermine si le processeur peut être intégré dans un système embarqué, contraint par la dépense énergétique, ou si il est destiné à être utilisé dans un centre de calcul. Les deux tendances sont représentées, avec d'une part les puces consommant entre 100 et 400 W conçues pour le contexte HPC et d'une autre part les puces consommant quelques watts à quelques dizaines de watts susceptibles d'être embarquées dans des équipements tels que les véhicules autonomes, les drones ou les satellites. Par exemple la puce Epiphany IV de la fabless Adapteva est constituée de 64 PE pour une consommation instantanée de seulement 2 W.

Enfin, une troisième observation porte sur le choix d'offrir ou non un mécanisme de cohérence matérielle entre les mémoires des PE (les caches, les scratchpads), indiqué dans la colonne CC. La présence de cohérence matérielle détermine si il est possible de déployer des applications reposant sur le paradigme de programmation en mémoire partagée, comme il est possible de le faire avec les thread POSIX sur un processeur ou sur un multiprocesseur NUMA (Non-Uniform Memory Architecture). Les premiers many-cœurs offrent généralement des mécanismes de cohérence des caches, reposant sur des NoC dédiés : par exemple une superposition de 6 réseaux de type mesh (en grille) pour interconnecter les cœurs dans l'architecture du TILE64, dont 2 réseaux sont réservés à la gestion de la cohérence des caches. Un autre exemple est le réseau sur puce en anneau présent dans les Xeon Phi, basé sur la circulation d'un token (jeton). La topologie de ces réseaux est une propriété importante à prendre en compte pour exploiter correctement les cœurs de calcul, avec pour objectif de limiter le nombre de hops entre la source et la destination et éviter le phénomène de contention sur des routeurs. Avec la multiplication du nombre de cœurs au milieu des années 2010, les mécanismes de CC sont rarement proposés. La CC est réintégrée dans les puces modernes dès lors que le nombre de cœurs ne dépasse pas la centaine, une limite pour le passage à l'échelle des mémoires virtuellement partagées déjà évoquée 35 ans auparavant par [Li, 1988] avec les grappes de calculateurs. Ce choix technique est aussi dirigé par les besoins d'abstraction du matériel pour les applications et intergiciels dédiés à l'intelligence artificielle, jusqu'alors développés pour les architectures parallèles plutôt que réparties.

**Stratégies pour passer à l'échelle.** La course au nombre de cœurs embarqués s'accompagne de problématiques classiques de passage à l'échelle concernant les entrées-sorties du cœur de calcul, le réseau sur puce, la mémoire locale au cœur, la mémoire centrale à la puce, l'alimentation électrique et même la synchronisation du front d'horloge [Teixeira Monteiro, 2016]! Dans ces conditions, les plus gros many-cœurs proposent rarement un mécanisme matériel pour la cohérence de cache et reposent sur deux principales techniques : 1) une architecture hiérarchique composée d'un
<table><caption>TABLE 2.1 – Quelques architectures many-cœurs conçues depuis le début des années 2000. La performance est donnée telle qu'indiquée par les concepteurs ou dans des évaluations académiques. Les unités de mesure pour la performance sont le SP pour GFLOPS (nombre d'opérations en virgule flottante par seconde, en million $10^6$) Simple Précision, le DP pour GFLOPS Double Précision, le GOPS (nombre d'opérations par seconde, en million $10^6$) et le TIPS pour un million de MIPS (nombre d'instructions par seconde, en million $10^6$) ($10^{12}$ IPS (nombre d'instructions par seconde)). La colonne CC (Cohérence de Cache) indique si le processeur est doté d'un système de maintient de la cohérence des caches ou des scratchpads entre les cœurs. Les valeurs entre parenthèses sont à prendre avec précaution.</caption><thead><tr><th>Année</th><th>Puce</th><th>Concepteur Référence</th><th>Cœurs</th><th>MHz</th><th>Perf.</th><th>W</th><th>CC</th><th>Nat.</th></tr></thead><tbody><tr><td>2007</td><td></td><td>Intel Corp. [Vangal et al., 2008]</td><td>80</td><td>4270</td><td>1000 SP</td><td>97</td><td>✓</td><td>✓</td></tr><tr><td>2007</td><td>TILE64</td><td>Tilera Corp. [Bell et al., 2008]</td><td>64</td><td>750</td><td>144 GOPS</td><td>10,8</td><td>✓</td><td>✓</td></tr><tr><td>2010</td><td>MIC Knights Ferry</td><td>Intel Corp. [Wikipedia, 2020]</td><td>32</td><td>1200</td><td>750 SP</td><td>300</td><td>✓</td><td>✓</td></tr><tr><td>2011</td><td></td><td>Intel Corp. [Howard et al., 2011]</td><td>48</td><td>1000</td><td></td><td>125</td><td>✓</td><td>✓</td></tr><tr><td>2012</td><td>Xeon Phi Knights Corner</td><td>Intel Corp. [Wikipedia, 2020]</td><td>61</td><td>1200</td><td>1200 DP</td><td>300</td><td>✓</td><td>✓</td></tr><tr><td>2012</td><td>PEZY-1</td><td>PEZY Computing [WikiChip, 2020]</td><td>512</td><td>533</td><td>533 SP 266 DP</td><td>35</td><td></td><td>✓</td></tr><tr><td>2013</td><td>TILE-Gx72</td><td>Tilera Corp. [Matthew Mattina, 2013]</td><td>72</td><td>1200</td><td></td><td>75</td><td>✓</td><td>✓</td></tr><tr><td>2013</td><td>MPPA Andey</td><td>Kalray Inc. [de Dinechin et al., 2013a]</td><td>256</td><td>400</td><td>211 SP 70 DP</td><td>12</td><td></td><td>✓</td></tr><tr><td>2013</td><td>Epiphany-IV E64G401</td><td>Adapteva Inc. [Adapteva Inc., 2017]</td><td>64</td><td>800</td><td>102 SP</td><td>2</td><td></td><td>✓</td></tr><tr><td>2014</td><td>PEZY-SC</td><td>PEZY Computing [PEZY Computing, 2020]</td><td>1024</td><td>733</td><td>3000 SP 1500 DP</td><td>100</td><td></td><td>✓</td></tr><tr><td>2015</td><td>MPPA-2 Bostan</td><td>Kalray Inc. [de Dinechin, 2015]</td><td>256</td><td>800</td><td>845 SP 422 DP</td><td>20</td><td></td><td>✓</td></tr><tr><td>2016</td><td>Xeon Phi Knights Landing</td><td>Intel Corp. [Wikipedia, 2020]</td><td>72</td><td>1500</td><td>5300 SP 2700 DP</td><td>260</td><td>✓</td><td>✓</td></tr><tr><td>2016</td><td>Sunway SW26010</td><td>ICC (Shanghai) [Dongarra, 2016]</td><td>260</td><td>1450</td><td>3062 DP</td><td>374</td><td></td><td>✓</td></tr><tr><td>2016</td><td>Epiphany-V</td><td>Adapteva Inc. [Richie and Ross, 2018]</td><td>(1024)</td><td>(500)</td><td></td><td>(10)</td><td></td><td>✓</td></tr><tr><td>2017</td><td>PEZY-SC2</td><td>PEZY Computing [WikiChip, 2020]</td><td>2048</td><td>1000</td><td>8192 SP 4096 DP</td><td>200</td><td></td><td>✓</td></tr><tr><td>2017</td><td>KiloCore</td><td>U.C. Davis [Bohnenstiehl et al., 2017]</td><td>1000</td><td>115</td><td>1,78 TIPS</td><td>40</td><td></td><td>✓</td></tr><tr><td>2017</td><td>NEO</td><td>REX Computing Inc. [Sebexen and Sohmers, 2015]</td><td>(256)</td><td></td><td>(512 DP)</td><td>(8)</td><td></td><td>✓</td></tr><tr><td>2017</td><td>Matrix-2000</td><td>NUDT [WikiChip, 2017]</td><td>128</td><td>1200</td><td>4920 SP 2460 DP</td><td>240</td><td>✓</td><td>✓</td></tr><tr><td>2017</td><td>Xeon Phi Knights Mill</td><td>Intel Corp. [Domke et al., 2019]</td><td>72</td><td>1500</td><td>13800 SP 1700 DP</td><td>320</td><td>✓</td><td>✓</td></tr><tr><td>2019</td><td>EPYC 7742</td><td>AMD Inc. [AMD Inc., 2019]</td><td>64</td><td>3400</td><td>(1360 DP)</td><td>225</td><td>✓</td><td>✓</td></tr><tr><td>2020</td><td>INTACT TSARLET</td><td>CEA-Leti [Vivet et al., 2020]</td><td>96</td><td>1150</td><td>220 GOPS</td><td>(23)</td><td>✓</td><td>✓</td></tr><tr><td>2020</td><td>MPPA-3 Coolidge</td><td>Kalray Inc. [Serra, 2020]</td><td>80</td><td>1200</td><td>1150 SP 384 DP</td><td>35</td><td>✓</td><td>✓</td></tr><tr><td>2020</td><td>Prodigy T16128</td><td>Tachyum Inc. [Tachyum, 2020]</td><td>(128)</td><td>(4000)</td><td>(16000 DP)</td><td></td><td>✓</td><td>✓</td></tr><tr><td>2020</td><td>MN-Core</td><td>Preferred Networks [Preferred Networks, 2020]</td><td>512</td><td></td><td>(131000 SP) (32800 DP)</td><td>(500)</td><td></td><td>✓</td></tr><tr><td>TBA</td><td>PEZY-SC3</td><td>PEZY Computing [WikiChip, 2020]</td><td>(8192)</td><td>(1333)</td><td></td><td>(400)</td><td></td><td>✓</td></tr></tbody></table>
<figure><img src="image_7.png" /><figcaption>FIGURE 2.3 – Architecture de la puce Kalray MPPA Andey : une organisation hiérarchique composée de 16 clusters de 16 PE interconnectés par un NoC dont la topologie est un tore 2D entrelacé (pour des raisons de lisibilité le NoC est représenté pour une colonne Nord-Sud, le maillage complet concerne toutes les colonnes et toutes les lignes Est-Ouest).</figcaption></figure>

ensemble de *clusters* de PE. Par exemple la puce MPPA Andey de Kalray propose 256 cœurs organisés en 16 *clusters* de 16 cœurs (Figure 2.3). Dans chaque *cluster*, une mémoire physiquement partagée (*scratchpad*) permet aux processus s'exécutant sur les cœurs du *cluster* d'allouer de la mémoire et de communiquer par le moyen de cet espace partagé. En revanche, deux cœurs localisés dans des *clusters* différents doivent faire appel à une bibliothèque de MP (*Passage de Message*) spécifique pour communiquer. 2) Une deuxième technique pour le passage à l'échelle consiste à simplifier l'architecture globale, comme c'est le cas pour les puces Epiphany d'Adapteva, organisées en un tuilage de PE, chaque tuile comportant un cœur de calcul, une petite mémoire locale et des connexions aux tuiles voisines, ce qui n'est pas sans rappeler le Transputer précédemment évoqué. L'évolution des architectures montre que la cohérence de cache matérielle est souvent présente dans les nouvelles puces, ce qui peut s'expliquer par une demande dirigée par l'applicatif, un nombre de cœurs *raisonnable* (une centaine) et l'arrivée de nouvelles technologies pour l'intégration des NoC telles que le *3D stacking* (l'empilement sur la puce des couches contenant les cœurs, les mémoires et le NoC favorisant les échanges rapides verticaux en plus des communications horizontales classiques). Ces choix architecturaux ont des implications fortes sur les modèles de programmation comme nous le verrons dans la suite de ce document.

**Le many-cœur d'aujourd'hui est-il le multi-cœur de demain ?** Le TOP500 [TOP500, 2020] propose le classement biannuel des super-calculateurs les plus puissants selon les performances mesurées par le benchmark LINPACK [Don-garra, 1987]. Un second classement, le GREEN500, permet de prendre en compte la consommation d'énergie requise pour exécuter le benchmark et ainsi encourager la conception de machines offrant un meilleur compromis entre la performance calculatoire et la dépense énergétique. Depuis les années 2010, les machines classées dans le TOP500 pré-sentent deux types de nœud de calcul : 1) un nœud composé d'un processeur multi-cœur et d'un GPGPU (une grande majorité des machines) et 2) un nœud composé d'un many-cœur ou composé d'un multi-cœur et d'un many-cœur. Les figures 2.4 et 2.5 permettent de mettre en valeur la place des many-cœurs dans les deux classements respectifs. Ces figures représentent le nombre maximal de cœurs présents dans un processeur (processeur hôte ou accélérateur) pour les dix premiers systèmes des classements respectifs. Elles ont été créées en analysant les listes mises à disposition sur le site du TOP500. La figure 2.4 montre l'introduction des premiers many-cœurs dans le TOP500 en novembre 2012 avec le système Stampede (U.Texas) classé 7ᵉ et composé des premiers Intel Xeon Phi SE10P à 60 cœurs. Par la suite, plusieurs systèmes intègrent des many-cœurs, souvent développés spécifiquement pour les super-calculateurs (PEZY, Sunway, Matrix-2000), et aussi parfois pour des activités liées à la défense. Cette figure montre aussi l'évolution du nombre de cœurs dans les processeurs hôtes : de 2 à 4 cœurs tout au plus en 2009, exception faite du processeur IBM PowerXCell 8i à 9 cœurs qui équipe le premier super-calculateur du TOP500 au Los Alamos National Laboratory, à une vingtaine de cœurs en 2020 dans le top 10. Cette augmentation atteint en 2021 jusqu'à 48 cœurs pour le processeur Arm/Fujitsu A64FX [Okazaki et al., 2020] et 64 cœurs pour le processeur AMD EPYC 7742 qui équipent respectivement les super-calculateurs Fugaku du RIKEN (première place) et Selene de Nvidia (5ᵉ place).
<figure><img src="image_8.png" /><figcaption>**FIGURE 2.4** – ⚙️ Nombre de cœurs embarqués par le processeur généraliste (multi-cœur ou many-cœur) le plus important présent sur les nœuds de calcul des systèmes classés dans les 10 premières places du TOP500, de juin 2009 à juin 2022.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**FIGURE 2.5** – ⚙️ Nombre de cœurs embarqués par le processeur généraliste (multi-cœur ou many-cœur) le plus important présent sur les nœuds de calcul des systèmes classés dans les 10 premières places du GREEN500, de juin 2013 à juin 2022.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>FIGURE 2.6 – Modèles de programmation en mémoire partagée (gauche) et par passage de messages (droite).</figcaption></figure>

> L'évolution des architectures de calcul dans le HPC montre une convergence entre les processeurs multi-cœurs haute-performance "classiques" et les processeurs many-cœurs.

Cette convergence est d'autant plus prononcée que les processeurs traditionnels se heurtent depuis les années 2010 à la fin de la loi de Dennard [Dennard et al., 1974]. Cette loi énonce que la miniaturisation des transistors permet de multiplier leur nombre sur une puce et d'augmenter la puissance de calcul tout en conservant la même consommation électrique. Alors que les procédés de fabrication des circuits descendent sous les 3 nm ($3 \times 10^{-9}$ m, en comparaison du diamètre estimé d'un atome d'hélium qui est de $5,96 \times 10^{-10}$ m), les courants de fuite induits par les petites échelles ne permettent plus de dissiper correctement la chaleur et de conserver des fréquences de fonctionnement élevées. L'histoire se répète : les moyens de calculs deviennent massivement parallèles et les processeurs héritent des travaux effectués pour les many-cœurs. Le processeur many-cœur emblématique Intel Xeon Phi est en fin de production [Curtress and Shilov, 2019] alors que les processeurs multi-cœurs AMD EPYC proposent désormais autant de cœurs de calcul que les many-cœurs de l'époque. Dès lors, les processeurs généralistes rencontrent les mêmes problématiques de programmabilité que les puces massivement parallèles.

**Problématique de la programmabilité.** La complexité architecturale des many-cœurs provient de l'accumulation et de la hiérarchisation des briques de calcul et de communication. Concevoir un programme nécessite bien souvent une connaissance minimale de l'architecture cible, ce qui contraint ou détermine le choix du modèle de programmation. Ainsi, il est possible de monter en complexité, du programme séquentiel, au programme parallèle, au programme réparti jusqu'aux approches hybrides mêlant les différents paradigmes de programmation.

La figure 2.6 illustre deux principaux modèles de programmation : la mémoire partagée à gauche, dans lequel un espace est alloué dans une mémoire physiquement partagée par des tâches (dans cet exemple, deux fils d'exécution, des threads). Une donnée partagée est identifiée par une adresse dans l'espace logique, traduite par un emplacement dans la mémoire physique. Les accès concurrents sont alors arbitrés localement par le matériel et/ou la pile logicielle. Cette méthode permet d'écrire des programmes parallèles avec une représentation des données partagées intuitive. Les tâches sont déployées sur une machine dite NUMA, sur laquelle la proximité physique des unités de calcul et des mémoires permettent des temps d'accès faibles (entre la nanoseconde $10^{-9}$ s et la microseconde $10^{-6}$ s). Cependant, les machines NUMA sont aujourd'hui limitées à quelques dizaines ou centaines de cœurs, avec un TCO (Total Cost of Ownership) important lorsque le nombre de cœurs est tel qu'il nécessite des architectures dédiées, bien loin des standards implémentés pour les machines grand public.

Le paradigme de programmation par passage de message illustré à droite de la figure 2.6 peut être utilisé en l'absence d'une mémoire physiquement partagée : c'est-à-dire lorsqu'il n'est pas possible d'allouer un espace logique visible et accessible par les deux tâches. Une donnée partagée est identifiée par un ou plusieurs messages qui sont transmis entre plusieurs tâches. Ces messages peuvent être transmis en empruntant des liens de communication potentiellement complexes en fonction de la topologie réseau tissée entre les deux processus, avec des temps d'accès relativement élevés, entre la microseconde et la milliseconde. Ils peuvent aussi être tout simplement transmis en utilisant un tampon partagé si les deux processus sont localisés sur une machine disposant d'une mémoire physiquement partagée, comme nous le verrons dans la section 2.1.3. Le passage de message permet d'écrire des programmes répartis, faisant fi de l'architecture sous-jacente, ce qui permet d'exploiter des grappes de calculateurs dont le coût unitaire est beaucoup moins élevé qu'une grosse machine NUMA et de passer plus facilement à l'échelle pour le nombre d'unités de traitement. Cependant, le partage de données est plus complexe à gérer dans la partie applicative car il repose sur un mécanisme différent, impliquant de traduire un accès en une suite de messages. Les accès aux données partagées reposent par
ailleurs sur des fondements théoriques différents : sur une machine NUMA il est possible d'utiliser une horloge globale pour séquentialiser les accès en se basant sur un horodatage simple. Ce n'est pas le cas dans un système distribué pour lequel il n'existe pas une telle horloge globale, mais plutôt une multitude d'horloges locales non synchronisées. Dès lors, l'arbitrage sur la séquentialisation des accès repose sur des dépendances causales et l'utilisation d'horloges vectorielles telles que décrites par Lamport [Lamport, 1978], Mattern [Mattern, 1988] et Raynal [Raynal, 1987].

Dans le contexte des many-cœurs, le paradigme de programmation en mémoire partagée facilite le portage d'appli-
cations existantes, le développement et la mise au point de nouvelles applications, favorisant l'adoption du processeur et
de son environnement de développement (IDE (Integrated Development Environment)) par la communauté scientifique
académique et industrielle. Dans le cas contraire, en l'absence de mémoire partagée, le développement des applications
peut s'effectuer selon trois méthodes : 1) reposer sur le paradigme de programmation par passage de messages, soit en
utilisant des intergiciels classiques tels que MPI et ZeroMQ, soit en utilisant un intergiciel propriétaire de MP fourni
par le constructeur de la puce. Cette solution implique souvent de spécialiser le code à l'architecture de la puce afin
d'en exploiter correctement les ressources. 2) Utiliser une MVP pour fournir une couche d'abstraction logicielle offrant
les mécanismes de cohérence de cache, ce qui peut s'avérer coûteux pour les performances mais permet de déployer
des applications écrites pour la mémoire partagée de façon relativement transparente. Enfin 3) utiliser des modèles de
programmation spécifiques tels que le flot de données (dataflow), offrant une couche d'abstraction de la puce, mais au
prix de se conformer à l'organisation des tâches et des données imposées par le modèle choisi.

Plusieurs initiatives ont été proposées pour abstraire la complexité matérielle des many-cœurs, en offrant aux applications une vision logique centralisée de la puce. C'est le cas par exemple du SSI (Single System Image) ALMOS [Almaless, 2014], un système d'exploitation conçu pour le many-cœur de recherche TSAR [LIP6, 2009] développé au laboratoire d'informatique de Paris 6 (Lip6). Tout comme les SSI habituellement déployés sur des grappes de calculateurs, ALMOS offre une MVP ainsi qu'un ordonnanceur de processus donnant l'illusion d'être exécuté sur une machine NUMA. Une autre initiative vers la conception d'un SSI [Penna et al., 2019] propose une HAL (Hardware Abstraction Layer) pour la gestion des cœurs et de la mémoire pour le MPPA Bostan. Un troisième exemple est le développement d'une MVP logicielle sur la puce Epiphany [Richie et al., 2017]. Ces projets montrent l'importance de proposer un environnement logiciel suffisamment haut-niveau afin de masquer la complexité architecturale des many-cœurs. Dans ce contexte, j'ai participé à plusieurs projets et proposé des contributions pour faciliter le déploiement d'applications.

**Contributions pour la programmabilité des processeurs many-cœurs.** En 2008, plusieurs projets académiques et industriels sont lancés afin de concevoir des processeurs many-cœurs. Parmi ceux-ci, une initiative du CEA et de la startup Kalray vise à proposer une architecture pouvant accueillir de 256 à 1024 cœurs. Je rejoins en 2009 le laboratoire commun CEA-Kalray (2009-2012) dont l'objectif est de proposer un environnement de programmation de cette puce et d'influencer l'architecture matérielle. Nous proposons un modèle de programmation flot de données basé sur une variation du modèle CSDF dans lequel des agents communiquent à travers des ports et des liens de communication, suivant une spécification des échanges fournie par l'application. Cette particularité permet d'effectuer de nombreuses vérifications lors de la compilation, notamment l'absence d'interblocages, un cadencement correcte des tâches ou encore un dimensionnement possible des tampons de communication. Le langage de programmation associé, Σ-C [Goubier et al., 2011], est supporté par une chaîne de compilation source-to-source [Aubry et al., 2013] qui a été transférée et industrialisée par Kalray. Dans le laboratoire commun, j'ai été responsable des tests unitaires, des tests d'intégration et de la livraison de la chaîne de compilation Σ-C à Kalray. J'ai aussi contribué à la conception de différentes étapes de la chaîne de compilation décrites dans la suite de ce manuscrit, ce qui représente environ 45 000 lignes de code C sur 245 000 et 6 publications dans des conférences avec actes.

En 2012 je renoue avec certaines thématiques explorées pendant ma thèse réalisée à l'INRIA sur la cohérence des données et les MVP pour grilles de calculateurs. Je propose de lancer une activité sur la mémoire (virtuellement) partagée dans le laboratoire. L'idée directrice est de proposer des protocoles de cohérence adaptés pour les architectures many-cœurs et leurs applications, puis de faciliter le choix et la configuration en fournissant des outils d'aide à la décision. En collaboration avec des collègues, des doctorants et des stagiaires que j'encadre, nous proposons trois protocoles de cohérence basés sur la coopération entre les caches des PE. Une chaîne de compilation est spécifiée, dont le but est d'analyser un code source parallèle et d'aider à déterminer quelles sont les configurations de protocoles de cohérence les plus adaptées pour chaque variable partagée. Plusieurs briques de cette chaîne de compilation sont réalisées dans le cadre de la thèse de Safae Dahmani [Dahmani, 2015] soutenue en 2015, que j'ai proposée et co-encadrée avec Guy Gogniat de l'UBS. Ces travaux se traduisent notamment par une douzaine de publications dans des conférences avec actes et un brevet.
<figure><img src="image_11.png" /></figure>

## 2.1 Σ-C : un langage flot-de-données cyclo-statique

Σ-C [Goubier et al., 2011] est un langage flot-de-données proposé par le CEA pour les architectures processeur massivement parallèles. À l'origine conçu dans le cadre d'une collaboration avec la compagnie fabless<fnref n="1" /> Kalray pour la puce MPPA-256 (une description de la puce se trouve dans la figure 2.3), Σ-C est en fait un langage dédié (un DSL (Domain Specific Language)) mais non spécialisé à une architecture particulière. C'est la chaîne de compilation (le compilateur) conçu pour Σ-C qui permet de cibler différentes architectures d'exécution : par exemple un binaire pour un processeur classique x86 (un programme parallèle utilisant les Posix threads), un binaire pour un simulateur d'architecture (un programme lié avec l'API (Application Programming Interface) d'un ISS (Instruction Set Simulator)) ou un binaire ciblant une architecture many-cœur comme le MPPA. Le compilateur est aussi capable d'effectuer de nombreuses vérifications, les principales étant la cohérence du graphe de communications, la vivacité à l'exécution, le débit de traitement et dans certains cas la latence bout en bout. Le développement de Σ-C répond à un besoin particulier : comment exploiter une puce massivement parallèle, ne disposant pas de mémoire partagée entre les clusters, en respectant des contraintes d'embarquabilité, notamment pour l'empreinte mémoire ? Le flot-de-données apporte un cadre formel pour des applications déployées sur le MPPA, nécessairement distribuées entre clusters, et ce cadre tend vers un déterminisme d'exécution (pouvoir reproduire des exécutions avec un entrelacement des évènements identique) qui est un prérequis pour cibler des applications embarquées pseudo temps-réelles (traitement de flux de données, traitement d'image pour véhicules autonomes...).

Σ-C a permis de programmer le premier processeur MPPA conçu par Kalray et de démontrer la performance calculatoire et énergétique de l'approche : En 2012 Kalray annonce que le MPPA-256 (Andey) est capable d'effectuer un encodage vidéo H264 aussi rapidement qu'un processeur Intel i7 de la même époque, mais avec une consommation d'énergie entre 6 et 20 fois moindre [de Dinechin et al., 2013a] ! Ceci constitue une véritable avancée pour un processeur générique, là où ce genre de résultat est habituellement obtenu par des accélérateurs spécialisés tels que les ASIC (Application-Specific Integrated Circuit), les GPGPU ou les FPGA. Ceci valide aussi les choix et la qualité de la R&D que nous avons menés dans le laboratoire commun du CEA LIST. Mais avant de décrire les contributions effectuées sur le modèle de calcul et la chaîne de compilation, revenons sur les grands principes du flot-de-données.

**Dans un modèle de programmation flot-de-données, les calculs sont exprimés par un ensemble d'acteurs dotés de canaux de communication. L'ensemble forme un graphe orienté dans lequel les nœuds représentent les traitements et les liens représentent les flux de données. Dans les années 1970, Gilles Kahn propose les KPN (Kahn Process Network) [Kahn, 1974], un modèle de calcul distribué dans lequel des processus déterministes communiquent via des canaux FIFO (First In First Out) de taille infinie. Les langages dérivés des réseaux de processus sont rapidement utilisés dans le contexte du traitement du signal [Lee and Parks, 1995] puis dans d'autres contextes HPC et embarqués, pour le multimédia notamment [Denolf et al., 2007, Michalska et al., 2015]. Ils permettent d'exprimer facilement un programme parallèle dans lequel la problématique de la concurrence des accès aux données est décidée par construction. Un cas particulier du KPN est le CSDF [Bilsen et al., 1996], dans lequel les consommations et les productions de chaque acteur

<footnote n="1">1. Dans la microélectronique, une compagnie fabless conçoit des puces mais ne les fond pas, c'est-à-dire qu'elle ne les réalise pas physiquement.</footnote>
Static Dataflow (SDF)

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

Cyclo-Static Dataflow (CSDF)

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

Static Dataflow (SDF) dependencies

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

Cyclo-Static Dataflow (CSDF) dependencies

<figure><img src="image_15.png" /><figcaption>FIGURE 2.7 – Exemples de graphes de communication et de dépendances pour des flots de données SDF (Static Data-Flow) et CSDF.</figcaption></figure>

sont explicitement indiquées dans le programme. L'appellation *Cyclo-Static* provient du fait que ces consommations et productions ne sont pas nécessairement les mêmes à chaque exécution de l'acteur, mais elles doivent suivre une séquence prédéfinie qui est donc répétée de manière cyclique.

Dans un langage flot de données, les acteurs peuvent être vus comme des machines à état dont le fonctionnement est le suivant : A) l'acteur attend que les canaux en entrée contiennent le nombre de données spécifiées par le programme. B) lorsque toutes les données sont présentes, elles sont lues de manière atomiques et utilisées pour le calcul (le code utilisateur). Cette phase est appelée *occurrence* (*firing* en anglais). C) les résultats sont écrits de manière atomique sur les canaux de sortie selon la spécification établie dans le programme. Puis l'acteur reboucle sur A. Il en résulte un fonctionnement sans terminaison. Une propriété fondamentale pour un flot de données est la vivacité (*liveness* en anglais) qui assure que chaque acteur est bien exécuté de manière infinie [Benazouz et al., 2013]. Cette notion se rapproche finalement de la problématique de la réception des messages dans les systèmes distribués avec l'emploi du qualificatif *eventually* en anglais qui signifie que le message finira bien par arriver, sans pour autant être en mesure de déterminer une date pour cet évènement. L'un des intérêts du CSDF est de donner un cadre suffisamment contraint, avec une description du comportement des acteurs suffisamment explicite pour construire des preuves sur des propriétés telles que la vivacité, l'absence d'interblocages ou le dimensionnement minimal des canaux de communication.

La figure 2.7 illustre les graphes de communications et de dépendances respectifs de deux exemples, l'un SDF et l'autre CSDF. Ces deux exemples sont composés de 4 acteurs, la structure du graphe de communications est la même mais les productions et les consommations sont différentes. Celles-ci sont indiquées pour chaque canal de communication : la quantité de données produites par l'acteur émetteur est indiqué à l'origine du canal, sur le port de sortie, alors que la quantité de données consommées est indiqué sur le port d'entrée. Dans le cas du SDF, ces quantités sont les mêmes à chaque occurrence de l'acteur. Dans le cas du CSDF, les quantités sont exprimées sous la forme d'un vector indiquant la séquence des productions ou des consommations émises ou reçues sur le port de communication. Par exemple l'acteur A produit 1 donnée à la première occurrence, 1 donnée à la deuxième occurrence, 2 données à la
troisième occurrence puis reboucle sur le début de la séquence pour la quatrième occurrence. À partir de ces graphes il est possible de construire le graphe des dépendances entre les occurrences. Pour chaque acteur X, les occurrences sont identifiées par la suite infinie ($X_0, X_1, ...$).

Un **graphe de dépendances** est construit en reliant les occurrences par des relations de causalité, c'est-à-dire une dépendance reliant les deux évènements. Les occurrences n'ayant aucune dépendance sont les points d'entrée du graphe, elles sont représentées en vert dans la figure 2.7. Ces occurrences sont directement exécutées lors du lancement de l'application. Une relation de causalité évidente est donnée par $X_i \rightarrow X_{i+1}$, qui indique que l'occurrence $X_{i+1}$ ne peut se produire avant $X_i$. En déroulant symboliquement les productions et consommations spécifiées dans le graphe SDF ou CSDF, il est possible de déterminer les liens de causalité entre les occurrences d'acteurs différents. Ces liens sont de deux types : les dépendances induites par les productions-consommations et les dépendances induites par le dimensionnement des canaux de communication. Pour les productions-consommations, une dépendance $X_i \rightarrow Y_j$ existe si la quantité de données attendue sur le port d'entrée de Y à l'occurrence $j$ a été produite par un nombre suffisant d'occurrences de X se terminant par l'occurrence $X_i$. Ces dépendances sont représentées en violet sur la figure. Pour le dimensionnement des canaux, une dépendance $X_i \rightarrow Y_j$ existe si l'acteur X a suffisamment consommé de données sur le canal $Y \rightarrow X$ pour que Y puisse de nouveau y produire des données. Ces dépendances sont représentées en orange sur la figure. Dans cet exemple, la taille des canaux de communication correspond à la valeur maximale du nombre de productions ou de consommations. Dans le cas présent, cette approche permet un dimensionnement suffisant des canaux, mais c'est en réalité un cas particulier, comme discuté dans la section 2.1.3.

Le graphe de dépendances est un objet apportant de nombreuses informations sur l'application : il est notamment très utile pour le bon paramétrage de l'environnement d'exécution (le *runtime*). Il permet d'effectuer des vérifications hors-ligne et des optimisations pour le dimensionnement des canaux de communication et le placement-routage de l'application sur la puce. Il est aussi utilisé en-ligne pour diriger l'ordonnancement précalculé des tâches, préparer les contextes des prochaines tâches à exécuter ainsi que les espaces de stockage pour transférer les données sur les canaux de communication. Sous la forme présentée en figure 2.7, le graphe est sans terminaison et il faut donc trouver une représentation finie et compacte pouvant être embarquée à l'exécution. Pour cela, il est possible de calculer le vecteur de répétition. Le vecteur de répétition est un sous-graphe du graphe de dépendances identifié comme un motif pouvant être répété à l'infini. À partir de ce motif il est possible de reconstituer le graphe de dépendances, ou tout du moins le *régime établi* de l'application, la phase d'initialisation (le *bootstrap*) nécessitant une description spécifique. Le vecteur de répétition est indiqué en bleu sur la figure 2.7. Dans Σ-C le vecteur de répétition est codé sous une forme compacte afin de limiter l'empreinte mémoire une fois chargé sur la puce et une méthode de compression est appliquée sur le modèle de temps logique vectoriel (LVT (*Logical Vector Time*)) [Dubrulle et al., 2012].

La **chaîne de compilation Σ-C** implémente toutes les étapes nécessaires pour l'analyse d'un programme fourni sous forme de texte, jusqu'à la construction d'un binaire embarquant le code utilisateur, le logiciel système ainsi que les objets décrivant le comportement de l'application. La réalisation de cette chaîne de compilation a nécessité un effort équivalent à une équipe d'une dizaine de personnes sur 3 ans. Un accord de confidentialité et d'exclusivité a été établi entre le CEA et Kalray pour la durée du laboratoire commun, à l'issue duquel il a été possible de communiquer sur les résultats et de publier. Dans ce projet, j'ai effectué plusieurs contributions : l'instanciation du graphe de communication, la compilation et la réduction du parallélisme ou encore le calcul des motifs d'accès aux tampons partagés.

### 2.1.1 Une chaîne de compilation *source-à-source*

> Aubry, P., Beaucamps, P., Blanc, F., Bodin, B., Carpov, S., Cudennec, L., David, V., Dore, P., Dubrulle, P., de Dinechin, B. D., Galea, F., Goubier, T., Harrand, M., Jones, S., Lesage, J., Louise, S., Chaisemartin, N. M., Nguyen, T., Raynaud, X., and Sirdey, R. (2013). Extended cyclostatic dataflow program compilation and execution for an integrated manycore processor. In Alexandrov, V. N., Lees, M., Krzhizhanovskaya, V. V., Dongarra, J. J., and Sloot, P. M. A., editors, *Proceedings of the International Conference on Computational Science, ICCS 2013, Barcelona, Spain, 5-7 June, 2013*, volume 18 of Procedia Computer Science, pages 1624–1633. Elsevier.

[Aubry et al., 2013] CEA LIST, Kalray SA.

Contributions | ☐ initiative ■ idées ■ implémentation ☐ expérimentations ■ rédaction ☐ présentation

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

Écrire un programme flot-de-données est relativement aisé, et peut se faire dans la plupart des langages de programmation, par exemple en C, Python ou Fortran. La plupart du temps, les méthodes et bonnes pratiques issues du génie logiciel poussent naturellement à structurer le code sous forme de tâches qui communiquent par le biais de messages ou de variables partagées. Alors finalement, pourquoi proposer un nouveau langage ? La question est critique à l'échelle d'un projet de recherche, et encore plus lorsqu'il s'agit d'un transfert technologique vers l'industrie. Pour les développeurs d'applications métier, utiliser un nouveau langage est source de nombreux désagréments : l'apprentissage de la syntaxe, des concepts objets et du modèle d'exécution sous-jacent demande un investissement en temps
(et en argent s'il faut recourir à des formations). Les développeurs perdent de plus l'usage des bibliothèques de code maison constituées et éprouvées dans les projets passés. Proposer un nouveau langage répond donc à un besoin, en faisant le pari que l'investissement concédé par les développeurs pour l'adopter sera récompensé à terme par un code plus qualitatif, de meilleures performances, de nouvelles fonctionnalités ou un cycle de développement raccourci.

Listing 1 - Un flot de données écrit en Python avec MPI, sous forme d'une chaîne d'agents (pipeline).

```python
#!/usr/bin/env python3
# $ mpirun -np 3 python3 python_dataflow.py

from mpi4py import MPI
from time import sleep

class DataflowAgent:
    def __init__(self, args=None):
        self.comm = MPI.COMM_WORLD
        self(rank = self.comm.Get_rank())
        self.size = self.comm.Get_size()
        print(str(self(rank) + " started")

# create a pipeline starting from MPI rank 0
if (selfrank > 0):
    self.input_port = selfrank - 1
if (selfrank < self.size - 1):
    self.output_port = selfrank + 1

def firing(self, running=True):
    if (selfrank > 0):
        running = self.comm.recv(source self.input_port)
        # this is the place to compute something
        sleep(1)
    if (selfrank < self.size - 1):
        self.comm.send(running, dest self.output_port)
        print(str(self(rank) + " fired with running value " + str(running))
    return running

def main():
    dataflow_agent = DataflowAgent()
    if (dataflow_agent(rank == 0):
        for i in range(3):
            dataflow_agent.firing(True)
        dataflow_agent.firing(False)
    else:
        while dataflow_agent.firing():
            pass
    if __name__ == "__main__":
        main()
```

Prenons par exemple le code Python présenté dans le listing 1 et dans lequel un flot-de-données simple est implémenté. Le programme permet de déployer une chaîne de *n* agents (un *pipeline*). Chaque agent est exécuté par un processus MPI et peut donc communiquer par ce moyen. Un booléen transite tout le long de la chaîne et est utilisé comme drapeau pour la terminaison : si la valeur reçue est *False*, l'agent écrit cette valeur sur son port de sortie et termine son exécution, ce qui permet la terminaison de l'application. Le code est décomposé en trois parties remplissant des fonctions distinctes et pouvant être généralisées à tout programme flot-de-données : 1) Dans la fonction d'initialisation de l'agent `__init__()`, les ports de communication sont déclarés et *connectés*. Ici, l'identifiant du processus MPI distant est indiqué dans les variables `input_port` et `output_port`. Cette étape permet de décrire le graphe de communication. 2) La fonction *firing* correspond aux instructions exécutées lors d'une occurrence de l'agent. Elle effectue de manière séquentielle la lecture de la donnée reçue sur le port d'entrée, un éventuel traitement utilisateur (ici un simple appel à la fonction `sleep`) suivi de l'écriture du résultat sur le port de sortie. Enfin 3) des boucles dans la fonction main implémentent l'automate distribué en itérant sur les occurrences jusqu'à la terminaison de l'application.
Sur la quarantaine de lignes de code, seule une ligne concerne le code utilisateur, c'est-à-dire directement liée à l'algorithme implémenté pour résoudre un problème (l'instruction `sleep` dans cet exemple). Le reste du programme est ce que l'on appelle un squelette (code skeleton en anglais), c'est-à-dire du code permettant de structurer les traitements et les données, bien souvent générique, compilable, mais dont l'exécution ne produit pas de résultat. Écrire un programme flot-de-données à la main consiste donc à écrire du code utilisateur métier et à l'enrober dans un squelette en charge de construire le graphe de communication. Concevoir ce squelette n'est pas anodin car il détermine la qualité du programme en terme de performance calculatoire, notamment par l'emploi du parallélisme de tâches. C'est aussi un élément déterminant sur le plan fonctionnel : que se passe-t-il si des agents ne sont pas correctement connectés, si une connexion est établie par erreur, si les données qui transitent ne sont pas celles attendues, si un agent produit à une cadence plus élevée que le consommateur ? Ces erreurs ne sont pas détectées par un compilateur classique et les problèmes surgissent trop tard, à l'exécution, parfois de manière silencieuse. Détecter à la compilation des erreurs structurelles nécessite une modification lourde du squelette et justifie : 1) la spécification formelle du squelette afin de contraindre le développeur à écrire des programmes corrects par construction et 2) l'utilisation d'outils d'analyse et de vérification afin de fournir la preuve que l'application peut s'exécuter dans un contexte donné.

> Ces deux points correspondent au besoin de proposer un nouveau langage et d'en assurer la compilation pour vérifier un certain nombre de propriétés avant l'exécution.

Dans la littérature plusieurs langages flot-de-données et chaînes de compilation ont été proposés pour programmer des architectures embarquées massivement parallèles, tels que Streamit [Amarasinghe et al., 2005], Brook [Buck et al., 2004], XC [Watt, 2009] ou OpenCL (qui est aujourd'hui largement répandu pour programmer les GPU et les FPGA). À la fin des années 2000 le modèle de calcul le plus proche de Σ-C est Streamit et son compilateur RAW [Gordon et al., 2002]. Comparé à Streamit/RAW le modèle de calcul Σ-C apporte plusieurs fonctionnalités : 1) Σ-C autorise l'ordonnancement dynamique des tâches sur la puce, 2) le NoC du MPPA implique que les communications doivent être implémentées indifféremment sur une mémoire partagée, sur un DMA (Direct Memory Access) ou du MP, ce qui n'est pas permis par le logiciel système de Streamit, 3) la granularité des tâches est plus fine que le concept de filtre Streamit et 4) le modèle CSDF permet une plus grande expressivité de part la construction très libre de la topologie du graphe de communication, à l'époque plus élaboré que les séries parallèle-séquentiel de RAW. Σ-C apparaît donc comme un compromis satisfaisant entre d'une part un langage doté d'une grande expressivité, notamment sur la construction du graphe de communication, et d'autre part offrant un cadre de développement suffisamment contraint pour produire des applications correctes par construction et dont certaines propriétés critiques peuvent être vérifiées à la compilation. Quelques années après Σ-C, une extension hiérarchique du modèle SDF est proposée par l'IETR/INSA de Rennes en collaboration avec Kalray pour prendre en compte l'aspect dynamique d'une application [Hascoet et al., 2017]. Ceci montre l'intérêt du flot-de-données pour la programmation de puces massivement parallèles, en complément des HAL plus bas-niveau. Mais revenons au début des années 2010.

Dans Σ-C plusieurs choix ont été faits afin de favoriser le portage du code métier existant (legacy code en anglais). Le langage est un sur-ensemble du langage ANSI C. Il est donc possible d'écrire le code utilisateur en C, de le copier à partir d'une application C existante et d'utiliser les bibliothèques tierces. Le langage Σ-C consiste en un ensemble de mots clés spécifiques utilisés pour décorer et structurer un code C. Le but du compilateur est alors de transformer le programme Σ-C en un programme ANSI C qu'il est possible de compiler avec un outil classique tel que gcc. C'est donc un compilateur source-à-source. Un autre avantage de cette approche est de s'abstraire de la plateforme matérielle ciblée, en laissant la possibilité d'utiliser un compilateur spécifique pour produire le binaire et ainsi profiter des optimisations associées. Il est aussi possible d'utiliser une chaîne de compilation croisée pour générer un binaire ciblant une architecture processeur différente du processeur de la machine hôte.

**Listing 2** – Un sous-graphe Σ-C racine permettant de construire (instancier) le graphe de communication, issue d'une application de détection de contours d'une image basée sur un opérateur Laplacien.

```c
subgraph root (int width, int height) {
    interface { spec {}; }
    map {
        agent output = new Writer<int>(ADDROUT, width * height);
        agent sy1 = new Split<int>(width, 1);
        agent sy2 = new Split<int>(width, 1);
        agent jf = new Join<int>(width, 1);
        connect (jf.output, output.input);
        for (i=0; i < width; i++) {
            agent cf = new ColumnFilter (height);
            connect (sy1.output[i], cf.in1);
```
12
13
14
15
16

}

```cpp
connect (sy2.output[i], cf.in2);
connect (cf.out1, jf.input[i]);
```

Listing 3 –

Un agent Σ-C encapsulant un code utilisateur convolutif.

```cpp
1 agent ColumnFilter(int height) {
2     interface {
3         in<int> in1, in2;
4         out<int> out1;
5         spec { in1[height]; in2[height]; out1[height]; };
6     void start () exchange (in1 a[height], in2 b[height], out1 c[height]) {
7         static const int
8             g1 [11] = {-1, -6, -17, -17, 18, 46, 18, -17, -17, -6, -1} ,
9             g2 [11] = {0, 1, 5, 17, 36, 46, 36, 17, 5, 1, 0};
10        int i, j;
11        for (i=0; i < height; i++) {
12            c[i] = 0;
13            if (i < height - 11)
14                for (j=0; j < 11; j++) {
15                    c[i] += g2[j] * a[i + j];
16                    c[i] += g1[j] * b[i + j];
17                }
18        }
19    }
```

**Une application Σ-C** est composée d'agents et de sous-graphes. Un exemple est donné dans les listings 2 et 3 et les graphes de communication correspondant sont respectivement donnés dans les figures 2.8a et 2.8b. Les mots clés ajoutés au langage C sont indiqués en **orange**. Les agents sont des entités autonomes pourvues d'un fil d'exécution et d'un espace mémoire propre. Une interface permet de décrire les ports de communication, leur direction et le type de données acceptées. La section **interface** contient aussi une spécification (section **spec**) du comportement de l'agent définie comme une séquence circulaire de transitions, chaque transition étant caractérisée par des quantités de données reçues et/ou émises sur les ports de communication. Il existe deux types d'agents : les agents utilisateur dont le code est fourni par le développeur, et les agents système spécialisés dans la réorganisation des données (par exemple les agents Split et Join permettent de dispatcher un flux de données sur un ensemble de tâches de traitement puis de regrouper les résultats). Les agents système sont fournis par la chaîne de compilation et leur compilation est décrite en section 2.1.3.

Un sous-graphe **subgraph** est un ensemble d'agents et/ou de sous-graphes interconnectés. Tout comme les agents, un sous-graphe est caractérisé par une interface avec des ports de communication. En revanche, la spécification du comportement du sous-graphe est inférée à partir de la composition des comportements des entités qu'il contient. Une autre particularité est que les ports du sous-graphe sont connectés à l'extérieur et à l'intérieur, ce qui permet aux données d'entrer et sortir du sous-graphe. Les agents et les sous-graphes sont instanciés dans une section du code appelée section **map**, en utilisant le mot clé **new**. Dans cette section il est possible d'écrire du code C classique et d'utiliser notamment des boucles pour instancier et connecter de nombreux agents et sous-graphes via la primitive **connect**. Les définitions récursives sont autorisées et encouragées. La section **map** est compilée et exécutée hors-ligne. Une conséquence directe est que le graphe de communication est statique : aucune nouvelle instance ou modification du graphe n'est possible pendant l'exécution. Ce choix est dirigé par le besoin de maîtriser le comportement de l'application sur la puce et permet d'apporter des preuves notamment sur l'empreinte mémoire ou la bande passante. Une autre conséquence est que l'environnement de compilation est susceptible de différer entre la compilation de la section **map** sur la machine hôte et la compilation du code utilisateur pour la cible : si le recours au langage ANSI C permet d'atténuer largement cette contrainte, certaines bibliothèques tierces peuvent ne pas être disponibles dans les deux cas et il faut donc programmer ces deux sections en conséquence.

**La chaîne de compilation Σ-C** est organisée en plusieurs étapes, chacune intervenant sur des opérations de transformation du code, de vérification de propriétés, d'optimisation du graphe de communication et de génération d'objets pour l'édition des liens. La figure 2.9 présente ces différentes étapes, sous forme d'une chaîne de compilation, du code source à la construction du binaire. Les contributions suivantes concernent les phases d'instanciation, de réduction du parallélisme et de dimensionnement des tampons de communication.
<figure><img src="image_17.png" /><figcaption>FIGURE 2.8 – Graph de communication obtenu après exécution de la section **map** dans le code Σ-C du listing 2 (Figure 2.8a). Agent ColumnFilter (cf) obtenu après la compilation du code Σ-C du listing 3 (Figure 2.8b).</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>FIGURE 2.9 – Les différentes étapes de la chaîne de compilation Σ-C.</figcaption></figure>

### 2.1.2 Réduire le parallélisme à la compilation

“Carpov, S., Cudennec, L., and Sirdey, R. (2013). Throughput constrained parallelism reduction in cyclo-static dataflow applications. In Alexandrov, V. N., Lees, M., Krzhizhanovskaya, V. V., Dongarra, J. J., and Sloot, P. M. A., editors, Proceedings of the International Conference on Computational Science, ICCS 2013, Barcelona, Spain, 5-7 June, 2013, volume 18 of Procedia Computer Science, pages 30–39. Elsevier.

[Carpov et al., 2013] CEA LIST.

Contributions | ☐ initiative ■ idées ☐ implémentation ☐ expérimentations ☐ rédaction ☐ présentation”

“Cudennec, L. and Sirdey, R. (2012). Parallelism reduction based on pattern substitution in dataflow oriented programming languages. In Ali, H. H., Shi, Y., Khazanchi, D., Lees, M., van Albada, G. D., Dongarra, J. J., and Sloot, P. M. A., editors, Proceedings of the International Conference on Computational Science, ICCS 2012, Omaha, Nebraska, USA, 4-6 June, 2012, volume 9 of Procedia Computer Science, pages 146–155. Elsevier.

[Cudennec and Sirdey, 2012] CEA LIST.

Contributions | ■ initiative ■ idées ■ implémentation ■ expérimentations ■ rédaction ■ présentation”

Σ-C permet d'écrire des programmes parallèles et répartis. Le parallélisme peut s'exprimer au niveau de l'agent, en écrivant du code parallèle, par exemple avec les *Posix Threads* ou *OpenMP* si l'architecture cible le permet. Le parallélisme est aussi naturellement exprimé par le flot de données, dans lequel les instances d'agents sont autant de processus exécutés de manière concurrente. Dans cette section nous considérons uniquement le parallélisme induit par le flot-de-données.

La compilation du parallélisme consiste à identifier et instancier les agents et les liens de communication déclarés dans la section **map** de l'application. Cette étape construit un graphe de communication dans lequel les noeuds sont des instances d'agent et les liens sont des connexions entre ports de communication. De l'information sémantique est attachée sur le graphe afin de faire le lien avec le code source et les autres résidus de compilation. Différentes
analyses sont effectuées sur ce graphe afin de vérifier qu'il est correctement formé. Dans le code Σ-C, l'instanciation des agents s'effectue hors-ligne, en exécutant un code utilisateur écrit dans la section *map*. Le modèle de programmation encourage le développeur à exprimer un haut degré de parallélisme, c'est-à-dire une granularité de tâches très fine. Par exemple, un traitement appliqué à une matrice peut s'exprimer en déclarant une tâche pour chaque ligne, ce qui peut entraîner un nombre important d'agents à instancier dans le graphe, et donc à déployer sur l'architecture cible.

Le parallélisme pour many-cœurs est caractérisé par une courbe d'accélération (le speed-up) proche des multi-cœurs dans lequel une utilisation raisonnable du CPU consiste à exécuter autant de processus que de cœurs physiques disponibles. Si l'application présente moins d'instances que de PE alors la puce est sous-exploitée (ce qui ne veut pas dire pour autant que l'application n'est pas correctement dimensionnée). Si l'application présente plus d'instances que de PE alors il y existe un seuil à partir duquel la puce devient surexploitée et les performances s'écroulent. Ce seuil est atteint lorsqu'un élément matériel placé sur le chemin critique est saturé. Par exemple lorsque le processeur passe trop de temps à effectuer des changements de contexte entre les processus, lorsque la hiérarchie de cache est polluée par les changements de contexte ou encore lorsqu'il existe trop de contention sur le NoC. Ces phénomènes de saturation et de contention apportent de plus beaucoup d'incertitude sur les temps d'exécution et ne permettent que peu de garanties dans un environnement contraint ou pseudo temps-réel. Utiliser efficacement un processeur multi-cœur consiste donc à trouver le bon compromis entre d'une part 1) une application suffisamment parallèle, possiblement composée d'un nombre de tâches supérieur au nombre de cœurs, ce qui permet de masquer les temps d'attente lorsque des tâches effectuent des entrées-sorties, et d'autre part 2) réduire le parallélisme afin de ne pas tomber dans une situation de saturation ou de contention d'un élément matériel.

Dans le contexte d'un programme Σ-C compilé pour le MPPA, les contraintes liées à la maîtrise de l'exécution imposent de déterminer le nombre d'instances d'agents à la compilation, et ce afin de conserver un déterminisme d'exécution. Un travail de recherche a donc été effectué afin de réduire, si nécessaire, le parallélisme de l'application en fonction de divers objectifs tels que le nombre de tâches par cœur ou encore le débit de traitement de l'information désiré pour le flot de données, ce qui s'avère important pour les applications temps-réel.

## L'approche par substitution de motifs

[Cudennec and Sirdey, 2012] consiste à remplacer des parties du graphe de communication du flot de données par des sous-graphes équivalents. Le graphe de communication obtenu est structuellement différent mais il conserve la même spécification fonctionnelle. La réduction du parallélisme est possible dès lors que les sous-graphes substitués présentent un nombre d'instances utilisateur différent. Ceci concerne uniquement les agents utilisateurs, qui seront effectivement compilés sous forme de processus et nécessitent d'être déployés sur un PE (contrairement aux agents systèmes dont la compilation ne donne pas lieu à un processus et aux sous-graphes *subgraph* qui n'ont pas d'existence au-delà de la construction du graphe de communication). Des exemples de motifs sont présentés dans les figures 2.10a, 2.10b et 2.10c. Ces motifs sont paramétrés, c'est-à-dire que la description structurelle du sous-graphe s'accompagne de règles de transformation vers un sous-graphe équivalent, ces règles étant paramétrées par un *facteur de réduction f*. Le rôle de *f* est d'appliquer la transformation du motif avec plus ou moins de force : c'est un réel compris entre 0 et 1, la réduction étant plus forte lorsque celui-ci tend vers 1 et son application est linéaire.

Considérons un motif Split-*-Join composé d'un agent système Split ouvrant sur *n* sous-graphes identiques et sans état (les *) et se fermant sur les *n* entrées d'un Join (c'est un cas particulier du motif cascade présenté en figure 2.10a avec une profondeur de 1). Le principe d'un Split est de distribuer les données entrantes sur les ports de sortie en utilisant un tourniquet (round-robin en anglais). Ce motif est détecté dans le graphe de communication à l'aide d'algorithmes d'isomorphisme de graphes. Pour chaque détection, la capacité de réduction (*c*) est calculée, c'est-à-dire le nombre maximal d'instances utilisateur pouvant être supprimées lorsque la fonction de réduction est appliquée avec *f* = 1. Dans le cas d'un Split-*-Join cette capacité est $c = n - 1$ car il faut au minimum une branche active pour conserver la fonctionnalité d'origine. Il est alors possible de remplacer le Split-*-Join par une structure équivalente mais dont le degré d'ouverture est $n'$ avec $(n-c) \le n' < n$. Les branches restantes traitent alors plus de données puisque le degré de parallélisme est plus faible. Le nouveau degré d'ouverture $n'$ est obtenu en choisissant une valeur de *f* correspondante, ce qui s'avère être une tâche plus complexe qu'il n'y paraît et ce pour plusieurs raisons :

- un graphe de communication peut contenir plusieurs instances de différents motifs (par exemple plusieurs Split-*-Join). Il faut donc attribuer une valeur de *f* à chacune de ces instances. Une approche naïve consiste à déterminer le nombre d'instances utilisateur à supprimer (*s*) dans le graphe de communication entier, à calculer la capacité de réduction du graphe complet comme la somme des capacités des instances de motifs détectés ($c_g = \sum_{i=0}^{I} c_i$), de calculer un $f_g$ global à partir de *s*, $c_g$ et d'un objectif en terme de nombre de tâches à conserver dans l'application, et enfin d'appliquer ce $f_g$ à toutes les instances de motifs en espérant que l'objectif soit atteint. Cette méthode est simple à mettre en œuvre mais n'est pas généralisable à cause du point suivant :

- des instances de motifs peuvent se trouver imbriquées dans d'autres instances de motifs. La conséquence directe est que lors de la réduction du parallélisme d'une instance, les instances imbriquées peuvent disparaître et l'objectif de réduction ne sera pas tenu (non atteint ou dépassé). Une autre conséquence est que l'opérateur de réduction n'est pas commutatif : l'ordre dans lequel les réductions sont appliquées sur les instances de motifs a une influence sur le résultat. Une solution pour réduire le parallélisme n'est donc pas seulement constituée des facteurs de réduction $f_i$, mais aussi de l'ordre dans lequel ils sont appliqués.
Un moteur de réduction du parallélisme a été implémenté dans la chaîne de compilation Σ-C, tel que décrit en figure 2.10d. Celui-ci détecte les motifs et construit différentes solutions pour appliquer une réduction dans un ordre particulier. La détection s'effectue par isomorphisme de graphes avec l'aide d'une table de Floyd-Warshall pour déterminer les distances des plus courts chemins entre deux instances dans le graphe. Cette table permet de vérifier rapidement des propriétés de symétrie et accélère la détection des motifs. L'exploration des solutions est un problème complexe car sujet à une forte combinatoire. En pratique, les applications rencontrées exhibent un nombre restreint de motifs, tout au plus une dizaine, et il est envisageable de mener une recherche exhaustive pour trouver une solution optimale. Dans le cas contraire, des stratégies métaheuristiques détaillées dans le papier permettent de classer les instances de motifs selon une relation d'ordre arbitraire (par capacité de réduction décroissante, par degré de recouvrement croissant avec d'autres motifs, par tri aléatoire...) et de ne considérer que les *n* premières instances afin de limiter l'espace de recherche. L'évaluation d'une solution nécessite la modification du graphe de communication pour calculer et évaluer le graphe transformé. Cette exploration est massivement parallélisable car la construction des solutions n'est pas dépendante des résultats précédents.

<figure><img src="image_19.png" /><figcaption>FIGURE 2.10 – Exemples de motifs structurels reconnus dans le graphe de communication de Σ-C et moteur de réduction du parallélisme, de la reconnaissance de motif à la recherche de solution.</figcaption></figure>

La qualité des solutions trouvées par le moteur de réduction du parallélisme a été évaluée dans le cadre de deux applications synthétiques et d'une application de traitement d'image. Les résultats sont présentés sur la figure 2.11. Les principales conclusions sont les suivantes : réduire le parallélisme en présence d'un motif Split-*-Join est relativement précis car la granularité pour supprimer des tâches est fine. C'est ce qui est constaté sur la figure 2.11a. En revanche, le motif de multiplication de matrices implique de supprimer ligne par ligne et colonne par colonne, ce qui implique des ajustements à plus gros grain et explique un écart plus important avec les objectifs de réduction imposés. Enfin, la réduction du parallélisme sur le filtre Deriche illustrée en figure 2.11b montre qu'il est possible de redimensionner le graphe avec beaucoup de précision jusqu'à un certain seuil en dessous duquel il n'est plus possible de supprimer
des tâches. Le moteur de réduction du parallélisme retourne alors un graphe de communication minimal pour cette
application.

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

(a) Pourcentage d'écart entre l'objectif fixé en terme de nombre de tâches et le nombre obtenu après réduction du parallélisme pour deux applications simples formées respectivement d'un motif Split-*-Join et d'un motif de multiplication de matrices. Les valeurs négatives indiquent que le moteur de réduction a supprimé plus de tâches que nécessaire.

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

(b) Nombre d'instances utilisateur supprimées et facteur de réduction appliqué pour un objectif fixé en terme de nombre de tâches après réduction du parallélisme pour une application de traitement d'image (un filtre Deriche composé de 2 motifs Split-*-Join, 1461 instances utilisateur et une capacité de réduction de 958 instances). Les barres d'erreur verticales représentent le nombre d'instances n'ayant pu être supprimées.

<caption>FIGURE 2.11 – Évaluation des solutions trouvées par le moteur de réduction du parallélisme.</caption>

L'approche de réduction du parallélisme par substitution de motifs redimensionne le graphe de communication avec une grande précision afin de cibler une architecture matérielle spécifique. Si cette approche structurelle permet de conserver les fonctionnalités de l'application, elle modifie cependant le graphe sans prendre en compte la performance calculatoire de l'application. Ainsi les temps de calcul, les débits et latences bout en bout peuvent être dégradés suite à une décision malheureuse du moteur de réduction. La contribution suivante, complémentaire à cette approche, permet de réduire le parallélisme en prenant en compte le débit du flot-de-données.

L'approche par factorisation des instances équivalentes [Carpov et al., 2013] consiste à factoriser des instances d'agents et de multiplexer les communications entrantes et sortantes. Cette approche s'inspire des travaux menés dans la chaîne de compilation Streamit dans laquelle les tâches peuvent être fusionnées afin d'adapter la granularité de l'application à la plateforme matérielle [Gordon et al., 2006]. La méthode implémentée dans Streamit se limite cependant à 1) la fusion de tâches organisées sous forme de *pipeline*, ce qui revient à colocaliser les tâches sur un même *PE* et de faire en sorte que les communications entre ces tâches soient remplacées par un partage d'information efficace et 2) la fusion de tâches organisées sous forme d'un rideau de tâches dans un motif Split-*-Join, ce qui est similaire aux mécanismes de réduction du parallélisme par substitution de motifs présentés précédemment.

Dans ce travail, nous considérons toutes les instances d'agents équivalentes, indépendamment de leur organisation
dans le graphe de communication, ce qui rend l'approche générique contrairement à celle de Streamit qui repose plus
sur la notion de motifs. La réduction du parallélisme est appliquée de la manière suivante :

1. Pour chaque instance d'agent la fréquence d'exécution représente le nombre d'occurrences (*firings*) par unité de temps. Une fréquence d'exécution globale est fixée pour l'application complète en spécifiant la fréquence des occurrences des entrées et des sorties du graphe de communication. Les fréquences d'occurrence sont ensuite inférées pour chaque instance connectée à l'intérieur du graphe en se basant sur la spécification des productions et des consommations.

2. Les instances d'agent sont regroupées par classe d'équivalence, c'est-à-dire qu'elles sont regroupées dès lors qu'elles ont été instanciées à partir du même code source.

3. Chaque classe d'équivalence est partitionnée et les instances d'argent appartenant à une même partition sont remplacées par une seule instance fusionnée de la même classe. Un nouveau graphe de communication est créé en multiplexant les entrées des instances fusionnées par un Join et en démultiplexant les sorties des instances fusionnées par un Split. De plus, le partitionnement est établi de telle sorte que la composition des fréquences d'occurrences des instances formant le nouveau graphe de communication préserve à minima la fréquence d'occurrence de l'application complète.

La réduction de parallélisme générique a été implémentée dans la chaîne de compilation Σ-C et son efficacité a été évaluée en utilisant une application de détection de contours dans une image. Cette application basée sur un filtre Laplacien à impulsion Gaussienne (LoG) décompose les images pour appliquer des traitements ligne par ligne puis
<figure><img src="image_22.png" /><figcaption>FIGURE 2.12 – Réduction du parallélisme par fusion de tâches et multiplexage des communications appliquée à une application Σ-C implémentant un filtre LoG (Laplacian of Gaussian).</figcaption></figure>

colonne par colonne. Le graphe de communication est présenté en figure 2.12a. Des agents systèmes Transpose<fnref n="2" /> ($T_i$) sont utilisés pour effectuer des transpositions entre le traitement des lignes et le traitement des colonnes, puis entre le traitement des colonnes et l'écriture sur la sortie. Deux exemples de réduction sont présentés :

- Une réduction partielle dans laquelle l'opérateur $T_3$ n'est pas considéré équivalent aux deux autres opérateurs $T_1$ et $T_2$. Ces trois instances ne peuvent donc pas être factorisées. Le graphe calculé par le moteur de réduction est présenté dans la figure 2.12b. Les instances utilisateur pour le traitement des lignes ($L_i$) et des colonnes ($C_j$) ont été factorisées deux à deux.

- Une réduction complète dans laquelle le *pipeline* central multiplexe aussi la transposition finale avant d'écrire le résultat sur la sortie *W*. Cette solution peu intuitive montre les possibilités de restructuration du graphe de communication que ne peuvent atteindre les approches implémentées dans *Streamit* ou par substitution de motifs.

Les résultats en terme de temps de compilation et d'exécution sont présentés dans la figure 2.13. Les principales conclusions sont les suivantes : L'augmentation du degré de parallélisme s'accompagne de la multiplication du nombre d'instances dans le graphe, ce qui implique des temps de compilation plus longs, notamment dans les phases de placement-routage, de dimensionnement des tampons de communication et de génération des objets binaires. C'est ce qui apparaît dans le cas où l'application n'est pas réduite (Figure 2.13a). La compilation du parallélisme permet donc de garder un temps de compilation constant en factorisant suffisamment d'instances. Les temps d'exécution de l'application (ici compilée pour une exécution Posix sur la machine hôte) montre qu'au-delà d'un degré de parallélisme de 4 les performances ne progressent plus, minées par une granularité trop fine et des communications trop présentes. À contrario, la factorisation des instances permet d'alimenter les tâches de traitement avec plus de données et de mieux

<footnote n="2">2. Dans Σ-C la transposition d'une matrice s'écrit comme un Split-Join dont le degré d'ouverture est égal au nombre de colonnes, avec la production élément par élément en sortie du Split et la lecture colonne par colonne sur chaque entrée du Join.</footnote>
<figure><img src="image_23.png" /><figcaption>FIGURE 2.13 – Évaluation du moteur de réduction du parallélisme par factorisation pour l’application LoG écrite avec différents degrés de parallélisme, comparaison entre l’application non réduite, partiellement réduite et complètement réduite.</figcaption></figure>

utiliser la bande passante entre les instances grâce au multiplexage/démultiplexage des flux. Le temps d'exécution diminue sans pour autant augmenter le parallélisme de manière effective.

En conclusion, la réduction du parallélisme est une étape nécessaire dans la chaîne de compilation Σ-C dont l'objectif est de produire des applications correctement dimensionnées. La réduction par substitution de motifs permet de maîtriser le nombre de tâches déployées sur la puce, de limiter l'empreinte mémoire et de s'assurer que l'exécution puisse se réaliser avec une mémoire embarquée contrainte. La réduction par factorisation est une méthode générique qui permet d'adapter le nombre tâches tout en garantissant que les performances calculatoires sont préservées. Ces deux méthodes sont complémentaires et peuvent être appliquées séquentiellement à la compilation en appliquant la substitution puis la factorisation afin de ne pas altérer le graphe une fois que la factorisation ait ajusté les performances en terme de débit. Une approche plus intégrée est cependant souhaitable, afin de ne pas dissocier ces deux phases et de considérer le problème multiobjectifs. Une perspective pour cette étape de compilation est de reposer sur un DSL tel que proposé dans [de Oliveira Castro et al., 2010]. Ce langage haut-niveau permet d'exprimer des réorganisations de données en utilisant des concepts simples comme les itérateurs, plutôt que de construire un graphe complexe avec des agents système, dont le degré de parallélisme est directement exposé au développeur. Ce langage est ensuite compilé en une composition d'agents système, ce qui pourrait être fait de manière à favoriser l'étape de réduction du parallélisme, notamment en privilégiant la construction de motifs et en adaptant en amont les productions et consommations pour satisfaire des contraintes de débit.

### 2.1.3 Calculer les accès aux tampons partagés

> Cudennec, L., Dubrulle, P., Galea, F., Goubier, T., and Sirdey, R. (2014). Generating code and memory buffers to reorganize data on many-core architectures. In Abramson, D., Lees, M., Krzhizhanovskaya, V. V., Dongarra, J. J., and Sloot, P. M. A., editors, Proceedings of the International Conference on Computational Science, ICCS 2014, Cairns, Queensland, Australia, 10-12 June, 2014, volume 29 of Procedia Computer Science, pages 1123-1133. Elsevier.

[Cudennec et al., 2014] CEA LIST.

Contributions | initiative | idées | implémentation | expérimentations | rédaction | présentation

Dans la plupart des langages flot-de-données certains acteurs sont dédiés au découpage, à la distribution et à la réorganisation des données. C'est le cas par exemple dans les langages CAL [Eker and Janneck, 2003], GreenStreams [Bartenstein and Liu, 2013], Streamit ou encore τ-C [Goubier et al., 2014]. Dans Σ-C ces acteurs, nommés agents système incluent principalement les opérations de distribution (Split), regroupement (Join), duplication (Dup) et de défausse (Sink). Leur interface et leur spécification est fixée par le langage mais il est possible de les paramétrer à l'instanciation dans les sections map : par exemple en indiquant le degré d'ouverture d'un Split (le nombre de branches de sortie), la taille de la donnée produite sur chaque branche de sortie ainsi que le type de la donnée, comme dans un template C++. La manière dont sont effectivement réorganisées les données est décidée par la chaîne de compilation. Ceci procure
<figure><img src="image_24.png" /><figcaption>FIGURE 2.14 – (haut) Graphe de communication d’une application de détection de contours composée de deux rideaux de tâches pour traiter les lignes puis les colonnes. La taille de la donnée *k* : consommée lors d’une occurrence est indiquée pour chaque instance d’agent. (bas) Découpage et réorganisation du flot de données par les agents système Split et Join pour alimenter les tâches de traitement avec des lignes et des colonnes.</figcaption></figure>

deux avantages : 1) la mise en œuvre est transparente pour le développeur et 2) la chaîne de compilation peut effectuer des optimisations relativement triviales car ces agents sont clairement identifiés et leur instanciation se conforme à un cadre prédéfini (ce qui n’est pas le cas avec des agents utilisateur, dont l’interface et la spécification sont libres).

Un exemple d'application utilisant des agents système est présenté dans la figure 2.14. Ce graphe de communication lit une image en entrée sous forme d'une suite de pixels, ligne par ligne (cette représentation est courante pour stocker une image ou une matrice en mémoire). Les consommations *k* indiquées sur les agents Split et Join permettent de distribuer les lignes sur le premier rideau de tâches puis de réorganiser les données pour distribuer les colonnes sur le deuxième rideau de tâches (ce qui est équivalent à une transposition). Une implémentation naïve des agents système consiste à créer un espace mémoire (un tampon partagé) pour chaque lien de communication puis de générer une boucle qui recopie les données entre les tampons partagés en entrée et en sortie de chaque agent en suivant les spécifications. Cette approche génère un grand nombre de tampons partagés, notamment lorsque des agents système sont instanciés avec un grand degré d'ouverture, ce qui est préjudiciable pour l'empreinte mémoire de l'application. La recopie entre les tampons est aussi un processus défavorable car il nécessite du temps processeur et est susceptible de polluer des caches. Une approche plus efficace repose sur la stratégie du zéro-copie, dans laquelle un unique tampon partagé est utilisé par les producteurs et les consommateurs. Pour cela, nous avons introduit le concept de *surface d'agents système*.

**Une surface d'agents système** est définie comme un sous-graphe sans îlots du graphe de communication tel que tous les nœuds sont des instances d'agents système. La compilation de ces surfaces repose sur les principes suivants : 1) un tampon partagé est créé pour chaque surface, 2) pour chaque lien de communication entrant dans la surface, c'est-à-dire dont l'origine n'est pas un agent système et la destination est un agent système de la surface, un motif d'accès mémoire en lecture sur le tampon partagé de la surface est calculé, et 3) de la même façon un motif d'accès mémoire en écriture sur le tampon partagé est calculé pour tous liens de communication sortant de la surface. A partir des motifs d'accès mémoire ainsi calculés il est possible de déduire la taille minimale du tampon partagé, ce qui répond à la problématique du dimensionnement.

**L'équivalence de pointeur (EoP (Equivalence of Pointer))** est une propriété garantissant que lors d'une occurrence de tâche, les espaces mémoire mis à disposition de la tâche pour accéder à ses ports de communication sont individuellement contigus. Cette propriété est fondamentale dans Σ-C car le modèle de programmation autorise l'usage de l'arithmétique de pointeurs<fnref n="3" /> sur les canaux de communication. Cette propriété permet au développeur d'accéder directement aux données sans passer par une phase de recopie dans des structures de données propres à l'algorithme, comme cela peut être le cas avec certains systèmes de sérialisation des objets.

<footnote n="3">3. l'arithmétique de pointeur consiste à accéder à des éléments d'un espace mémoire en additionnant des adresses mémoire avec des entiers. Lors d'une allocation, le système garantit que l'espace demandé est réservé dans une zone contiguë en mémoire, et non fragmenté à divers endroits.</footnote>
<figure><img src="image_25.png" /><figcaption>FIGURE 2.15 – Illustration de la non-conservation de l'EoP dans une cascade de Split-*-Join. (gauche) Le graphe de communication avec les consommations et productions. (droite) Motifs d'accès en lecture pour chaque instance d'agent sur le tampon partagé écrit séquentiellement par le producteur *p*. Pour chaque occurrence de tâche un segment délimité par des flèches ←→ est indiqué sur le tampon partagé avec le numéro d'occurrence au dessus. Les segments rouges correspondent à des accès non-contigus qui ne respectent pas l'EoP.</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>FIGURE 2.16 – Comparaison en nombre de cycles processeur requis pour exécuter différentes applications Σ-C avec la compilation des agents système en mode tampon partagés (SEQ) et en mode utilisateur (USR).</figcaption></figure>

Une illustration de la non-conservation de l'EoP est donnée dans la figure 2.15. Le graphe de communication est constitué d'une cascade Split-*-Join de profondeur 2. La branche S0 conserve l'EoP contrairement à la branche S1. Dans cet exemple, l'EoP n'est pas conservée car les consommations de S1 ne divisent pas les productions de S, tout comme les consommations de J1 ne divisent pas les productions de S1. Il en résulte des accès fragmentés sur le tampon partagé représentés en rouge : l'espace mémoire mis à disposition du code utilisateur ne permet alors pas d'effectuer de l'arithmétique de pointeur, ce qui ne respecte pas le modèle de calcul Σ-C. Ces instances d'agents système ne peuvent donc pas être compilées en un unique tampon partagé : la chaîne de compilation va donc compiler les instances violettes comme un tampon partagé et décider d'un autre mécanisme pour les instances oranges.

Lorsqu'il n'est pas possible de compiler les accès mémoire dans un tampon partagé, un microcode DMA peut est
généré pour programmer des motifs d'accès mémoire et reconstituer un espace contigu. Cette solution est par exemple
souhaitable lorsque des tâches s'exécutent dans des clusters différents et ne partagent donc pas de mémoire physique.
Cette approche génère cependant des interactions plus coûteuses qu'un accès mémoire. Elle est de plus limitée par la
dimension du DMA, c'est-à-dire la profondeur maximale d'imbrication des boucles itérant sur les adresses mémoire
et qui permettent de décrire des motifs plus ou moins complexes (des strides pour décomposer un espace mémoire en
segments, en blocs, en volumes...). Une autre solution lorsque l'usage du DMA n'est pas possible est de générer un
code Σ-C utilisateur pour chaque agent système décrivant les recopies et les réorganisations des données entre les
ports de communication en entrée et en sortie. Cette dernière méthode est inefficace car elle ajoute des instances dans
l'application, ce qui augmente la complexité des phases de compilation suivantes (partitionnement, placement-routage,
édition des liens), augmente l'empreinte mémoire et alimente l'ordonnancement en ligne. Cependant, la compilation
des agents système sous forme de code utilisateur permet de traiter les cas les plus complexes et est utilisée comme
solution de dernier recours.

La compilation des agents système a été implémentée dans la chaîne de compilation Σ-C. Contrairement à la ré-
duction du parallélisme, c'est une phase non optionnelle du processus. La figure 2.16 illustre l'importance de traduire
les réorganisations de données dans des mécanismes bas-niveau efficaces. Différentes applications sont évaluées sur
un ISS fourni par Kalray et simulant fidèlement la puce MPPA-256 (un cycle processeur dans l'ISS correspond à 2,5 ns avec une fréquence d'horloge de 400 MHz). Le nombre de cycles processeur est comparé pour chaque application lors d'une compilation des agents système avec tampons partagés et lors d'une compilation avec des agents utilisateur. Un exemple extrême est donné par le programme synthétique Identity composé de deux agents système chaînés produisant sur leur port de sortie les données reçues sur leur port d'entrée : l'exécution est 2000 fois plus lente en mode utilisateur (USR). L'application de détection de mouvement (Motion) est composée de 50 instances d'agents utilisateur embarquant du code de traitement d'image et de 13 instances d'agents système, dont 11 sont potentiellement compilées par des accès à un tampon partagé. Sur cette application de classe industrielle le gain se traduit par une exécution 1,5 fois plus rapide.

**En conclusion,** La composition d'agents système permet d'exprimer des réorganisations de données complexes, notamment grâce à la grande expressivité offerte par le langage Σ-C lors de la compilation et l'exécution hors-ligne des sections map. Cette approche est de plus très intuitive avec un retour visuel pour le développeur sous forme de graphe de communication. Comme bien souvent, offrir un haut niveau d'abstraction au développeur s'accompagne d'une gestion plus complexe du logiciel système pour obtenir de bonnes performances. La compilation des agents système est un problème simple au premier abord et dont la réalisation relève de l'ingénierie. En fait sa résolution a nécessité de proposer de nouveaux concepts et algorithmes pour partitionner les surfaces d'agents systèmes et décider quelle type de compilation doit être appliquée (motifs d'accès à un tampon partagé, génération de microcode DMA ou génération de code Σ-C), ce qui est loin d'être trivial. La compilation des agents système a été transférée à Kalray pour être intégrée dans l'environnement de développement du MPPA-256 [de Dinechin et al., 2013a]. Tout comme la phase de réduction du parallélisme, l'efficacité de cette phase de compilation repose sur la présence de sous-graphes de communication dont la spécification des productions et des consommations permet la compilation en mémoire partagée. Ceci requiert une compréhension fine des techniques de compilation de la part du développeur, ce qui ne peut être exigé et ne favorise pas l'adoption d'un nouveau langage. Une perspective est donc d'apporter des règles de transformation du graphe de communication qui permettent à la compilation de s'assurer que toutes les surfaces d'agents système préservent l'EoP : s'il est difficile de modifier les quantités pour les productions et les consommations sans remettre en cause le bon fonctionnement du code utilisateur, il est toutefois possible de contraindre un agent utilisateur connecté à une surface système d'écrire dans un tampon partagé selon un schéma d'accès précalculé, et non plus séquentiellement, ce schéma d'accès favorisant la préservation de l'EoP pour les agents système connectés en aval. Pour autant, décider s'il existe une transformation du graphe préservant la réorganisation des données spécifiée par le développeur tout en apportant l'EoP relève de la théorie et n'a pas été étudiée ici.

### 2.1.4 Programmation chimique sur Σ-C

> “Cudennec, L. and Goubier, T. (2015). A short overview of executing Γ chemical reactions over the Σ-C and τ-C dataflow programming models. In Koziel, S., Leifsson, L. T., Lees, M., Krzhizhanovskaya, V. V., Dongarra, J. J., and Sloot, P. M. A., editors, Proceedings of the International Conference on Computational Science, ICCS 2015, Computational Science at the Gates of Nature, Reykjavík, Iceland, 1-3 June, 2015, 2014, volume 51 of Procedia Computer Science, pages 1413–1422. Elsevier.”
> 
> [Cudennec and Goubier, 2015] CEA LIST.
> 
> Contributions | ■ initiative ■ idées ■ implémentation ■ expérimentations ■ rédaction ■ présentation

Le principe d'un DSL est de fournir une interface de programmation adaptée à un modèle de programmation particulier. En ce sens Σ-C est un DSL flot-de-données dont le compilateur traduit les concepts d'acteurs et de liens de communication vers un modèle de programmation hybride en mémoire partagée et par passage de messages. Avec Σ-C le développeur doit écrire le code des acteurs et décrire les liens pour construire le graphe de communication. Mais peut-on imaginer un DSL dans lequel cette phase de description du graphe de communication n'est plus requise, et ainsi permettre au développeur de se concentrer uniquement sur le code métier ? Dans un tel système auto-organisant, un ensemble d'agents Σ-C est instancié et la construction du graphe de communication est laissée à la charge du compilateur. Cette approche soulève deux problématiques : 1) un nombre potentiellement important de possibilités à explorer pour construire ce graphe avec la perte du déterminisme à l'exécution et 2) la difficulté d'apporter un cadre de programmation garantissant que quelque soit le graphe de communication retenu à la compilation, le résultat de l'exécution préserve la sémantique exprimée par le développeur (l'application est fonctionnellement correcte). Dans ce travail, j'ai proposé de recourir au modèle de programmation chimique pour apporter ce cadre de programmation haut-niveau.

**Le modèle de programmation chimique** GAMMA [Banâtre and Métayer, 1990] a été introduit à la fin des années 1980 comme une manière élégante de définir mathématiquement des programmes répartis. Le principe repose sur l'analogie des réactions chimiques, dans lequel un ensemble de molécules réagissent pour en former de nouvelles selon la formule *replace P by M if C* (avec *P* et *M* des molécules et *C* une condition). La programmation chimique consiste à déclarer des données initiales typées ainsi que des opérateurs. L'ordre des réactions - la manière dont
sont appliqués les opérateurs sur les données - est résolu à l'exécution, sans indications de la part du développeur. Les programmes chimiques sont par nature parallèles et non déterministes. Ce paradigme a été utilisé pour les grappes et grilles de calculateurs et il reste pertinent pour les processeurs many-cœurs. Des exemples d'applications sont proposés dans [Radenac, 2007] et incluent des algorithmes de parcours de graphes, un serveur de messagerie électronique, un système de versionnage de fichiers, du traitement d'image et même un noyau de système d'exploitation [Banâtre et al., 2000]. Une grande part de la complexité des programmes chimiques réside dans le logiciel système qui a la charge d'orchestrer les réactions. L'implémentation de ce logiciel fait resurgir les problèmes classiques d'exécution en environnement réparti pour des applications irrégulières, ce qui explique qu'il est difficile de mettre au point une implémentation efficace du langage chimique. Plusieurs pistes pour une implémentation ont été proposées, de la version séquentielle [Creveuil, 1991] jusqu'à une exécution sous forme d'un flux de travaux (workflow en anglais) sur grille de calculateurs [Németh et al., 2006]. L'implémentation que nous avons proposée est basée sur une approche de compilation itérative dans laquelle les prochaines réactions sont décidées à la compilation, le résultat est calculé à l'exécution puis réutilisé lors d'une nouvelle compilation pour déterminer quelles sont les réactions suivantes. Cette approche est en rupture avec une implémentation où les réactions se décident à l'exécution, de manière décentralisée.

<figure><img src="image_27.png" /><figcaption>FIGURE 2.17 – Compilation et exécution d'un programme chimique Σ-C appliqué à un opérateur max à deux entrées.</figcaption></figure>

Le calcul chimique peut être comparé à un flot de données, dans lequel les réactions sont représentées par les agents et les molécules par les liens de communications. Réciproquement, une application flot de données peut décrire un ensemble de réactions chimiques appliquées sur des molécules, dans un ordre partiel. Dans cette analogie, écrire un programme chimique en Σ-C consiste à déclarer un état initial composé d'un ensemble d'agents représentant les molécules (un agent avec un unique port de communication typé sur lequel est émis la valeur de la molécule) et un ensemble d'agents représentant les réactions (un agent avec au moins un port en entrée et au moins un port en sortie). Les connexions entre agents ne sont cependant pas décrites dans le programme (absence de section *map*). L'une des particularité de l'approche est de choisir un ordre partiel d'exécution des réactions chimiques lors de la phase de compilation. C'est lors de cette phase que les connexions sont établies afin de former un graphe d'instanciation de l'application, comme présenté dans la figure 2.17a. Lors de la compilation les agents représentant les molécules initiales ne peuvent pas être instanciés plus d'une fois alors que les agents représentant les réactions peuvent être instanciés autant de fois que nécessaire. Pour chaque terminaison du graphe, un agent représentant la molécule produite est instancié (un port de communication en entrée) afin de collecter le résultat du calcul. Ce graphe est ensuite exécuté sur la cible, produisant un ensemble de résultats assimilés aux molécules obtenues. Ces résultats peuvent alors être utilisés comme données initiales d'un nouveau programme chimique Σ-C (Figure 2.17b). Cette compilation rebouclée peut s'alimenter jusqu'à l'obtention d'un état stable, c'est à dire ne permettant plus de construire un nouveau graphe de communication. Les instances d'agent restantes constituent le résidu de la réaction et la solution trouvée à l'issue de l'exécution du programme.

Une implémentation de l'approche itérative pour la programmation chimique a été mise en œuvre dans Σ-C ainsi que dans τ-C [Goubier et al., 2014], une chaîne de compilation similaire à Σ-C, mais avec un objectif expérimental là où Σ-C vise un transfert industriel. La figure 2.18 illustre la modification opérée sur la chaîne de compilation. Elle consiste en 1) l'ajout d'une étape de construction du graphe de communication entre la phase d'instanciation et la phase d'optimisation du déploiement et 2) la collecte des résultats à l'issue de l'exécution suivie de l'écriture d'un nouveau code Σ-C représentant les molécules ainsi obtenues. Cette deuxième modification implémente le rebouclage entre les
<figure><img src="image_28.png" /><figcaption>FIGURE 2.18 – Modification de la chaîne de compilation Σ-C pour compiler des programmes chimiques.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>FIGURE 2.19 – Graphe de communication construit à partir d'un opérateur max et de 200 molécules initiales.</figcaption></figure>

cycles de compilation et d'exécution. Un exemple de graphe de communication construit par la chaîne de compilation est donné en figure 2.19 à partir d'un opérateur max et de 200 molécules initiales. Cette application donne lieu à la construction d'un seul graphe du fait de la simplicité de l'opérateur max et de l'unique type de donnée déclaré (un entier). Pour des applications plus complexes, plusieurs graphes de communication indépendants (des îlots) sont créés et exécutés en parallèle sur le processeur many-cœur.

**En conclusion**, le modèle de programmation flot-de-données apporte un formalisme et une structuration des applications suffisamment haut niveau pour pouvoir y projeter des modèles de programmation abstraits tels que la programmation chimique. Cette approche n'implémente cependant pas toute l'expressivité rendue possible par le modèle GAMMA, notamment la possibilité pour une réaction de créer de nouvelles réactions en sus de nouvelles molécules, comme dans le modèle HOCL [Banâtre et al., 2004]. Si la compilation itérative sur Σ-C est une contribution modeste pour l'implémentation efficace du langage de programmation chimique, celle-ci démontre tout de même les avantages apportés par une structuration claire du code et un modèle de calcul exposés en amont au développeur, associés à une chaîne de compilation modulaire.

Une seconde observation est que les accélérateurs visés par l'approche itérative sont classiquement connectés à un processeur hôte par un bus PCIe (Peripheral Component Interconnect Express). Ce type de bus est performant lorsque le programme charge des données en un seul bloc vers l'accélérateur, déporte le calcul puis récupère les résultats en un seul bloc sur le processeur hôte. Dans ces conditions, les temps de transfert bien supérieurs à un accès mémoire sont idéalement masqués par un temps de calcul long sur l'accélérateur. Dans le cas de la compilation itérative d'un programme chimique, le bus PCIe est un facteur limitant car cette utilisation nécessite des échanges fréquents avec une granularité de données fine : le graphe complet ne peut en effet être déterminé en amont et sa construction itérative s'effectue au rythme des résultats partiels calculés sur l'accélérateur. Cependant, les accélérateurs bénéficient aujourd'hui d'une intégration matérielle plus efficace, à travers des bus d'interconnexion pour composants hétérogènes et permettant l'accès à de la mémoire physique partagée ou directement à la mémoire des composants distants, sans copie. Ces architectures sont donc plus adaptées à un programme dont le comportement tient plus de la collaboration entre un processeur et un accélérateur, plutôt qu'une organisation asymétrique maître-esclave. La compilation itérative de programmes chimiques pourraient donc bénéficier des avancées technologiques présentes sur de tels systèmes.
<figure><img src="image_30.png" /></figure>

## 2.2 Gestion de la cohérence des données sur many-cœur

Les processeurs many-cœurs sont des architectures singulières, à cheval entre les composants électroniques intégrés et les systèmes massivement parallèles et distribués, ou comment concevoir une grille de calculateurs sur quelques centaines de mm². Dès lors, les problématiques rencontrées pour gérer les données partagées relèvent de deux principaux domaines déjà bien étudiés : les hiérarchies de caches pour les processeurs et les systèmes de caches répartis pour les architectures distribuées. Ce qui en fait une thématique de recherche à part entière est l'addition des contraintes et des opportunités issues de ces deux domaines bien souvent étudiés par des communautés de chercheurs distinctes. Des architectures processeurs, les many-cœurs héritent des technologies de caches et des réseaux sur puce performants mais qui ne passent cependant pas à l'échelle facilement du fait de la complexité matérielle sous-jacente. Des architectures distribuées, les many-cœurs héritent de l'accumulation des unités de traitement et de stockage, ainsi que des organisations décentralisées pour le passage à l'échelle. Dans ce contexte, l'enjeu est de conserver la vision simple d'un processeur classique tout en exploitant cette accumulation de ressources de manière transparente.

En 2012, lorsque j'initie un sujet de recherche sur la cohérence des données pour les architectures MPPA, les processeurs many-cœurs sont scindés en deux catégories (cf. table 2.1) : la première, représentée par Intel et Tilera propose des mécanismes de cohérence des caches matériels. Avec les architectures TILE, deux NoC sur six sont exclusivement réservés à la gestion des caches pour les messages de contrôle et de transfert de données. Les architectures MIC/Xeon Phi se basent sur un anneau bidirectionnel interconnectant les PE [Rahman, 2013]. Ces approches permettent d'offrir un système programmable avec des outils conventionnels, tels que le modèle *Posix Threads* en mémoire partagée. La taille de ces architectures reste cependant modeste, de l'ordre de quelques dizaines de cœurs. La deuxième catégorie, représentée par Adapteva, Kalray et PEZY n'offre pas de mécanismes de gestion de la cohérence de cache à l'échelle de la puce. La programmation de ces architectures se base sur un modèle distribué ou hybride, bien souvent par l'intermédiaire d'une API propriétaire. Cette approche permet de concevoir des puces avec un grand nombre de cœurs mais au prix d'imposer un modèle de programmation et de forcer le portage ou la réécriture des applications. Les puces de la première catégorie sont adaptées au contexte HPC dans lequel les applications s'exécutent sur des processeurs génériques, alors que les puces de la seconde catégorie visent un marché de niche dans lequel les applications sont développées pour une architecture spécifique. La gestion de la cohérence des caches dans les many-cœurs est donc un enjeu en terme de programmabilité et détermine d'une certaine manière les contextes d'utilisation.

**La cohérence des données** est un sujet traité dans les architectures parallèles et réparties dès lors que les données sont accédées par des processus concurrents. La question est alors de savoir pour chaque lecture quelle version de la données est retournée, ce qui implique de déterminer quelles modifications sont visibles et dans quel ordre. Pour répondre à cette question, un modèle de cohérence est utilisé, qui peut être vu comme un contrat passé entre le développeur et le système en charge de la cohérence. Ce contrat spécifie formellement l'ordre partiel des modifications appliquées à une donnée partagée pour chaque accès en lecture. Un protocole de cohérence consiste en une implémentation d'un modèle de cohérence, c'est-à-dire une spécification de la séquence des messages de contrôle (des métadonnées) et des données échangées entre les participants lors d'un évènement tel qu'une demande d'accès en lecture ou en écriture. Un protocole de cohérence peut être modélisé à l'aide d'un automate fini réparti.
Il existe des modèles de cohérence plus ou moins relâchés, c'est-à-dire qui établissent un ordre plus ou moins strict sur les évènements. Nous pouvons citer quelques exemples : le modèle de cohérence le plus contraignant est le modèle strict *atomic consistency*, un modèle idéal où chaque lecture rend la dernière valeur écrite dans la donnée. Dans les systèmes distribués, un tel modèle nécessite l'utilisation d'une horloge globale, ce qui rend son implémentation impossible. Le modèle séquentiel *sequential consistency* [Lamport, 1979] assure que les évènements sont vus dans le même ordre sur chaque participant. Le modèle causal (*causal consistency*) [Lamport, 1978] se base sur la notion de causalité pour déterminer l'ordre entre deux évènements. Ce modèle permet de lier certains évènements entre eux par un ordre bien fondé tout en relâchant les contraintes sur les évènements indépendants. Les protocoles de cohérence implémentant ces modèles de cohérence génèrent un nombre important de messages, parfois inutiles lorsqu'il s'agit de mettre à jour des données qui ne seront plus accédées par la suite. Ces implémentations sont peu adaptées pour passer à l'échelle dans des grands systèmes distribués. D'autres modèles dits *relâchés* permettent de diminuer la pression sur le protocole de cohérence et de favoriser le passage à l'échelle. Certains modèles peuvent autoriser des écritures et des lectures concurrentes, et le développeur de l'application doit accepter que la donnée lue n'est pas nécessairement la plus récente à un *instant*. Un exemple de modèle de cohérence utilisé dans les travaux présentés dans ce manuscrit est la cohérence à l'entrée (*entry consistency*) [Bershad et al., 1993]. Dans ce modèle un verrou est associé à chaque donnée partagée, il permet de protéger les accès au sein d'une portée délimitée par l'acquisition du verrou et sa libération. En dehors de cette portée la donnée est considérée comme indéterminée. Ce modèle limite le faux-partage en discriminant les accès sur une donnée partagée et non pas un espace mémoire complet. Il permet de plus de faire varier la granularité des données partagées pour optimiser le comportement du protocole de cohérence.

> Choisir un modèle de cohérence consiste donc à trouver le bon compromis entre
> le maintient d'une cohérence suffisamment stricte requise par l'application tout en déployant un protocole
> de cohérence adapté à l'architecture cible en terme de performance calculatoire ou énergétique.

Dans ce manuscrit nous ne détaillons pas les différents modèles et protocoles de cohérence des données, ces informations pouvant par exemple être trouvées dans le cadre de ma thèse [Cudennec, 2009]. J'ai étudié ce sujet dès 2004 [Cudennec, 2005], notamment en proposant un protocole de cohérence spécialisé dans la visualisation de données partagées pour du couplage de code [Antoniu et al., 2006a]. L'évaluation de ce protocole fait partie des toutes premières expérimentations multi-sites menées sur la grille expérimentale GRID'5000 [Antoniu et al., 2006b]. Dans ce document, les travaux effectués sur la thématique de la cohérence des données pour les architectures many-cœurs sont classés en trois axes. Un premier axe concerne l'étude de nouveaux protocoles de cohérence basés sur le préchargement de motifs d'accès mémoire et sur la coopération de caches voisins. Un deuxième axe concerne l'évaluation de ces protocoles de cohérence à l'aide de méthodes analytiques et de simulateurs de NoC. Enfin, un troisième axe traite de l'aide à la décision pour le choix d'un protocole de cohérence adapté à une application et un contexte d'exécution.

### 2.2.1 Protocoles de cohérence de caches coopératifs

“Marandola, J., Louise, S., Cudennec, L., Acquaviva, J., and Bader, D. A. (2012). Enhancing cache coherent architectures with access patterns for embedded manycore systems. In 2012 International Symposium on System on Chip, ISSoC 2012, Tampere, Finland, October 10-12, 2012, pages 1–7. IEEE.
[Marandola et al., 2012] CEA LIST, Georgia Institute of Technology.
Contributions | ★ initiative ■ idées ☐ implémentation ☐ expérimentations ■ rédaction ☐ présentation”

“Dahmani, S., Cudennec, L., and Gogniat, G. (2013). Introducing a data sliding mechanism for cooperative caching in manycore architectures. In 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, Cambridge, MA, USA, May 20-24, 2013, pages 335–344. IEEE.
[Dahmani et al., 2013] CEA LIST, Lab-STICC.
Contributions | ★ initiative ■ idées ☐ implémentation ☐ expérimentations ■ rédaction ☐ présentation”

“Dahmani, S., Cudennec, L., Louise, S., and Gogniat, G. (2014). Using the spring physical model to extend a cooperative caching protocol for many-core processors. In IEEE 8th International Symposium on Embedded Multicore/Manycore SoCs, MCSoC 2014, Aizu-Wakamatsu, Japan, September 23-25, 2014, pages 303–310. IEEE Computer Society.
[Dahmani et al., 2014] CEA LIST, Lab-STICC.
Contributions | ★ initiative ■ idées ☐ implémentation ☐ expérimentations ■ rédaction ☐ présentation”

Proposer un protocole de cohérence pour un processeur many-cœur nécessite de prendre en compte les spécificités de ces architectures pour assurer un passage à l'échelle dans de bonnes conditions tout en offrant une implémentation
<table><caption>TABLE 2.2 – Protocoles de cohérence des caches et bus d'interconnexion pour quelques architectures processeur.</caption><thead><tr><td>Protocole</td><td>Constructeur</td><td>Références</td><td>États</td><td>Premières cibles</td><td>Année</td></tr></thead><tbody><tr><td>Hammer HyperTransport</td><td>AMD</td><td>[Keltcher et al., 2002]</td><td>MOESI</td><td>Opteron, Athlon64</td><td>2002</td></tr><tr><td>QuickPath Interconnect</td><td>Intel</td><td>[Intel, 2009]</td><td>MESIF</td><td>Core Nehalem</td><td>2008</td></tr><tr><td>AMBA 5 CHI ACE</td><td>ARM</td><td>[ARM, 2017]</td><td>(MO)ESI</td><td>Cortex A</td><td>2013</td></tr><tr><td>Infinity Data Fabric</td><td>AMD</td><td>[Lepak et al., 2017]</td><td>MDOEFSI</td><td>EPYC</td><td>2017</td></tr><tr><td>Ultra Path Interconnect</td><td>Intel</td><td>[Mulnix et al., 2017]</td><td>MESIF</td><td>Xeon Skylake</td><td>2017</td></tr><tr><td>TAG Directory</td><td>Fujitsu</td><td>[Fujitsu Limited, 2020]</td><td>MESI</td><td>A64FX</td><td>2019</td></tr></tbody></table>

réaliste sur le plan matériel et logiciel. Les approches classiques sont héritées des protocoles déployés sur les processeurs multi-cœurs. Elles reposent sur le principe du répertoire [Culler et al., 1999] avec une description de l'état des données partagées. Dans la table 2.2 plusieurs protocoles de cohérence de cache sont présentés pour des architectures multi-cœurs très largement répandues ciblant des domaines d'application grand public, HPC et embarqué. Ces protocoles reposent sur des briques matérielles spécifiques, comme des bus d'interconnexion ou des NoC propriétaires qui rendent les solutions non portables et non applicables pour d'autres architectures (à l'exception de l'approche ARM qui permet d'accéder aux spécifications et d'en effectuer une implémentation).

**Le répertoire (directory-based protocol)** est un espace regroupant des métadonnées sur l'état global ou partiel du système de caches. Ce répertoire peut être centralisé ou décentralisé, c'est-à-dire distribué sur plusieurs unités de traitement de la puce. Les informations ainsi stockées concernent notamment l'état courant des données partagées ainsi que leur présence ou non sur les différents espaces mémoire. Ces informations sont utilisées par le protocole de cohérence pour localiser les données, autoriser ou non un accès ou encore commander un transfert. Lorsque le répertoire est distribué, une méthode courante pour connaître quelle unité contacter lors d'un accès à une donnée est d'utiliser la notion de nœud référent (HN (Home-Node)). Pour chaque donnée partagée, un HN est associé suivant une politique connue par tous les nœuds. Pour connaître le HN, une fonction de hachage prend un identifiant de donnée partagée et retourne l'identifiant du nœud référent. Une fonction classique (mais naïve) consiste à effectuer un modulo sur les identifiants des nœuds, ce qui revient à effectuer une assignation par la méthode du tourniquet (round-robin).

**L'état d'une donnée partagée** dépend des accès en cours et/ou des derniers accès effectués. Le nombre et le type des états dépend directement du protocole de cohérence implémenté. Les 4 états les plus courants sont MESI, correspondant à Modifié (un processus a modifié la donnée et les copies ne sont plus à jour), Exclusif (un processus est en cours d'écriture et les accès suivants doivent attendre la fin de cet accès), Shared (un processus est en cours de lecture et des accès concurrents en lecture seule sont possibles) et Invalidée (la donnée est une copie et nécessite une mise à jour). Dans cet exemple, MESI est associé à un protocole permettant des lectures concurrentes et des écritures exclusives (MRSW (Multiple Readers, Single Writer)). D'autres états ont été proposés pour optimiser la gestion des données, par exemple l'état Forward du protocole MESIF permet de désigner le cache ayant effectué le dernier accès en lecture comme détenteur de la donnée plutôt que de la chercher dans la mémoire physique. L'état Owner du protocole MOESI est équivalent à l'état Forward de MESIF, à l'exception du fait que chaque modification donne lieu à une mise à jour de la mémoire physique, ce qui peut pénaliser l'application dans certains cas.

**La coopération des caches** consiste à mutualiser les ressources matérielles, par exemple en stockant des données sur des caches distants lorsque le cache local est saturé, ou encore en profitant d'une bande passante agrégée lors d'un accès à une donnée présente sur plusieurs caches. L'intérêt pour la mise en place d'une coopération des caches grandit à mesure que la taille de la puce augmente : les problématiques classiques rencontrées avec le passage à l'échelle nécessite la mise en place de stratégies de groupe et l'équilibrage de charge sur les ressources. Cet aspect n'est pas développé dans les processeurs multi-cœurs traditionnels du fait du nombre modeste de cœurs. Dans les architectures many-cœurs dotées de mécanismes de cohérence, l'organisation des caches est calquée sur les grandes machines NUMA, avec une structuration hiérarchique qui ne favorise pas des collaborations directes, notamment au voisinage. C'est la raison pour laquelle nous avons exploré différentes stratégies de collaboration : un mécanisme logiciel-matériel permettant la gestion répartie de motifs d'accès mémoire et des mécanismes logiciels ou matériels permettant l'utilisation de caches voisins par glissement de données.

**Le projet CoCCA (Co-designed Coherent Cache Architecture)** [Marandola et al., 2012] propose d'étendre un protocole de cohérence de caches classique avec une unité de traitement matérielle de motifs d'accès mémoire pour effectuer du préchargement de données. Cette unité de traitement située sur chaque cœur, permet d'intercepter des accès à des adresses identifiées préalablement puis de déclencher une série d'accès correspondant à un motif mémoire afin de remplir le cache par anticipation. L'unité comprend une table associative, chaque entrée étant composée d'un déclencheur (trigger en anglais) et de la description du motif sous forme compacte. Une version simple du déclencheur consiste à
indiquer la première adresse mémoire du motif. La forme compacte d'un motif consiste en un quadruplet (adresse de base, taille, décalage, longueur) permettant de décrire un motif 2D.

Les motifs d'accès mémoire sont déterminés hors-ligne et construits de différentes manières : 1) en se basant sur une analyse de code, et plus précisément les boucles imbriquées, 2) en effectuant une exécution du binaire sur le processeur hôte, instrumenté par l'outil de compilation JIT (Just in Time) Pin/Pintools [Bach et al., 2010] et en analysant les accès mémoire dans les traces d'exécution ou 3) en acceptant directement des motifs décrits par l'application. La figure 2.20 illustre le comportement du protocole CoCCA lors d'un accès à un motif connu. Une simple requête à une adresse déclenche le transfert de plusieurs données de la mémoire principale vers le cache du cœur émetteur. Cette version du protocole peut encore être optimisée en fusionnant les deux premières étapes présentées en figures 2.20a et 2.20b.

<figure><img src="image_31.png" /><figcaption>FIGURE 2.20 – Fonctionnement du protocole CoCCA sur un processeur à 4 cœurs pour un accès à un motif 2D.</figcaption></figure>

Des évaluations analytiques du protocole ont été menées dans [Marandola et al., 2012] et [Marandola et al., 2016]. La méthodologie consiste à instrumenter une application avec l'outil *pinatrace* de Pin/Pintools qui permet de journaliser les accès aux données partagées pour chaque cœur. Une machine à état permet ensuite, en fonction d'un protocole de cohérence et d'une architecture donnés, de reconstituer l'état du cache et les messages de cohérence échangés. La table 2.3 donne le nombre de messages de cohérence générés par un filtre convolutif en cascade sur une architecture composée d'une grille de 7 × 7 cœurs. Le protocole CoCCA réduit le nombre de messages de cohérence de l'ordre de 37%. Par ailleurs, le préchargement des données dans les caches permet de réduire le temps de latence à la mémoire. Pour
<table><caption>TABLE 2.3 – Nombre de messages de CC émis lors de l'exécution d'un filtre convolutif en cascade sur une image de taille 640 × 480, sur une architecture composée d'une grille de 7 × 7 cœurs et pour les protocoles MESI et CoCCA. L'image est découpée en 49 rectangles de tailles identiques, chaque cœur travaille sur un rectangle. Une zone de recouvrement (shadowing en anglais) est présente sur les bords : certaines données sont donc partagées entre 2 ou 4 cœurs.</caption><thead><tr><th>Messages de CC ↓ Protocole →</th><th>MESI</th><th>CoCCA</th></tr></thead><tbody><tr><td>Invalidation de ligne de cache partagée</td><td>34560</td><td>17283</td></tr><tr><td>Accès exclusif à une ligne de cache partagée entre 2 cœurs</td><td>12768</td><td>12768</td></tr><tr><td>Accès exclusif à une ligne de cache partagée entre 4 cœurs</td><td>1344</td><td>772</td></tr><tr><td>Total</td><td>48672</td><td>30723</td></tr></tbody></table>

obtenir un ordre de grandeur, nous avons mesuré le nombre de cycles nécessaire à l'exécution du filtre convolutif sur un unique cœur d'un processeur Intel Xeon Nehalem, ce qui s'apparente à l'utilisation du protocole CoCCA lorsque tous les motifs sont préchargés dans les caches. La valeur obtenue est comparée avec une exécution utilisant le protocole par défaut, ce qui donne un temps d'exécution 67% plus lent pour MESI par rapport à CoCCA (le détail du calcul se trouve dans [Marandola et al., 2012]).

J'ai pris la direction du projet interne CoCCA sur financement CEA Challenge Innovation de 2010 à 2012. Les résultats ont donné lieu à la soutenance de thèse de Jussara Marândola Kofuji [Marândola Kofuji, 2011], à un dépôt de brevet [Cudennec et al., 2012] et à trois publications internationales. En 2019, le processeur Fujitsu A64FX équipant la machine Fugaku (RIKEN, Japon) classée première du TOP500 depuis juin 2020, intègre un circuit de préchargement de données en cache basé sur les motifs d'accès mémoire [Okazaki et al., 2020]. Ce circuit effectue du prefetch matériel soit par détection automatique d'une séquence d'adresses en ligne, soit par une méthode appelée injection qui prend en charge des motifs d'accès par décalage (strided access patterns en anglais) directement déclarés par le programme. L'intégration de tels mécanismes dans le processeur A64FX démontre la pertinence de l'approche proposée dans le projet CoCCA une dizaine d'années plus tôt.

**Le protocole coopératif par glissement de données** (data-sliding protocol) [Dahmani et al., 2013] est un protocole de cohérence mettant à contribution les caches voisins pour soulager l'activité d'un cache en particulier. La coopération entre caches n'est pas une nouveauté en soi : c'est une technique éprouvée dans de nombreux domaines, par exemple pour les serveurs internet [Holmedahl et al., 1998] ou les réseaux sans-fil non-structurés [Cho et al., 2003]. Dans le domaine des architectures multiprocesseurs, une approche de cache coopératif est proposée dans [Dybdahl and Stenström, 2007]. Dans cette approche, le cache de chaque cœur est segmenté en deux parties : une partie privée et une partie partagée dans laquelle d'autres cœurs peuvent stocker des données. Une extension est proposée sous forme de cache élastique [Herrero et al., 2010] autorisant la segmentation dynamique des caches, ce qui permet de s'adapter aux besoins opérationnels. Cependant, dans le cas d'un ensemble de caches voisins fortement sollicités, ces protocoles ne permettent pas de répondre à la demande de coopération et génèrent des évictions qui se traduisent ensuite par des défauts de cache.

Sur une puce composée d'un grand nombre de caches locaux comme cela est le cas pour certains processeurs many-cœurs, une telle zone d'activité (hot spot en anglais) entraîne un déséquilibre entre les caches voisins fortement sollicités et les caches distants potentiellement sous-utilisés. Une approche naïve consiste à mettre à contribution des caches de plus en plus éloignés. C'est le principe du N-Chance Forwarding, un équivalent de la patate chaude qui repousse une donnée aussi loin que nécessaire. Cette stratégie s'accompagne cependant d'une augmentation de la latence pour accéder aux données à travers le NoC. Et ce NoC peut s'avérer être complexe (par exemple le tore 2D entrelacé de la puce Kalray) et induire une latence plus élevée pour atteindre certains caches distants qu'un accès à la mémoire externe! Pour répondre à cette problématique nous avons proposé un mécanisme de glissement de données dont le principe est le suivant : A) lorsqu'un cache $N_1$ est saturé, celui-ci effectue une demande de coopération à un cache voisin $N_2$. B) Si le cache $N_2$ est saturé, celui-ci choisit une ligne dans son cache privé à migrer et effectue une demande de coopération à un cache voisin $N_3$ afin de libérer cet espace pour y stocker la donnée du cache $N_1$. Le mécanisme opère donc un glissement plutôt qu'un transfert, en poussant les données autour du cache saturé. De cette manière, les données restent statistiquement plus proches de leur cache propriétaire.

La figure 2.21 illustre le mécanisme de glissement de données entre 3 caches. Sur tous les caches, un espace libre flottant est maintenu afin d'honorer les requêtes de coopération en garantissant une latence correspondant à un hop (au plus loin un voisin direct). En l'absence d'une telle stratégie, et parce que cette primitive est synchrone, le cache à l'origine de la requête de coopération serait susceptible d'attendre la terminaison de toute la chaîne de coopération avant de considérer que la donnée est bien stockée. Le glissement de données peut être implémenté comme une extension d'un protocole de cohérence classique. Lors d'un accès à une donnée, le protocole classique consulte le cache local. En cas d'absence de celle-ci, le protocole coopératif consulte les caches distants. Enfin, en dernier recours, le protocole classique effectue les opérations suite à défaut de cache, qui consistent à contacter le HN et/ou déclencher un accès en mémoire externe.

Une évaluation analytique du protocole de glissement de données a été menée et des comparaisons ont été effectuées
<figure><img src="image_32.png" /><figcaption>FIGURE 2.21 – Protocole de glissement de données entre 3 caches $N_1$, $N_2$ et $N_3$.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>(a) Scénario à un point chaud.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>(b) MESI + Cache élastique.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>(c) MESI + Glissement de données.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>(d) Scénario à 4 points chauds.</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>(e) MESI + Cache élastique.</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>(f) MESI + Glissement de données.</figcaption></figure>

FIGURE 2.22 – Nombre de messages de CC émis sur chaque cœur d'une grille 8 × 8, pour des scénarios à 1 et 4 points chauds. Comparaison des résultats analytiques obtenus pour le protocole de cache élastique [Herrero et al., 2010] et le protocole de cache par glissement de données. Ces figures sont issues du manuscrit de thèse de Safae Dahmani [Dahmani, 2015].

avec le protocole de cache élastique. La figure 2.22 représente sous forme d'une carte de chaleur (heatmap en anglais) le nombre de messages de CC émis par chaque cœur. L'architecture choisie est une grille de 8 × 8 cœurs interconnectés par un NoC à 4 voisins. Les scénarios sont constitués de points chauds, c'est à dire qu'une application synthétique effectue un nombre important d'accès à des données partagées sur un cœur et ses voisins afin de rapidement saturer puis polluer les caches locaux. En comparaison du protocole élastique, le glissement de données permet un étalement plus important de la surface de coopération ainsi qu'une augmentation du nombre de messages de CC. Cette augmentation du nombre de messages est cependant à mettre en perspective avec le gain obtenu en terme de défaut de caches. Dans cet exemple chaque utilisation d'un nœud voisin correspond à une donnée conservée dans les caches de la puce, et non évincée en mémoire externe. Un autre paramètre à prendre en compte est la distance un nombre de hops entre un nœud effectuant une requête d'accès et le cache détenant la donnée. Bien que conçu pour limiter globalement cette distance, le protocole par glissement peut entraîner un éloignement important si le mécanisme est appliqué de manière itérative dans la même direction. Pour résoudre ce problème, une extension du protocole de glissement inspirée du modèle masse-ressort a été proposée pour limiter l'éloignement des données sur la puce.

**Le protocole de glissement avec modèle masse-ressort** (mass-spring protocol) [Dahmani et al., 2014] permet d'adapter dynamiquement la distance d'éloignement d'une donnée du cœur propriétaire. Cette distance d'éloignement est un élément paramétrable du protocole de glissement de données, sur le principe du *N-Chance Forwarding*, indiquant un nombre maximum de hops possibles au-delà duquel la donnée n'est plus conservée sur la puce. Conserver la donnée sur la puce reste avantageux dans de nombreuses situations : la figure 2.23a montre que le taux de succès au cache augmente à mesure que la distance maximale d'éloignement autorisée augmente, jusqu'à un certain stade à
partir duquel la surface constituée par les caches coopératifs est devenue suffisante. Ce paramètre d'éloignement n'est cependant pas complet car les migrations de données ne s'effectuent pas nécessairement dans la direction opposée au cœur propriétaire : si un glissement rapproche la donnée, il sera tout de même considéré comme un éloignement au sens du nombre de hops. Un point crucial porte donc sur le choix du voisin lors d'une demande de coopération afin de ne pas systématiquement migrer dans la même direction. Dans le protocole original, le meilleur voisin est déterminé à l'aide de compteurs locaux incrémentés à chaque requête de glissement. Cette technique permet de classer les voisins par niveau de sollicitation, tout en évitant une implémentation centralisée ayant une vue globale de l'état des caches de la puce. Le choix du cœur voisin sur lequel migrer la donnée n'est donc pas dépendant de la localisation du cœur propriétaire, et aucun mécanisme ne permet de limiter la distance physique.

Le principe de l'extension de protocole masse-ressort est de s'inspirer du modèle physique du même nom pour décider sur quel voisin migrer les données (figure 2.23b). Dans cette analogie, le processeur est vu comme un bac-à-sable dans lequel les caches forment des creux et des bosses en fonction de leur niveau de saturation : un creux pour un cache sous-utilisé et une bosse pour un cache sur-utilisé. Les données partagées sont représentées par des billes de masse constante (en fait la masse peut être ajustée pour varier l'inertie et donc la propension à changer de direction sur la puce). Enfin, le modèle comprend un ressort dont les extrémités sont connectées au cœur propriétaire d'une part et à la donnée d'autre part. Afin d'éliminer les effets de résonance et donc éviter qu'une donnée passe son temps à osciller entre deux caches, le modèle intègre des frottements visqueux. Une modélisation mathématique donne l'équation suivante lorsque projeté sur l'axe x avec $\Delta h$ la différence de potentiel entre le cœur source et le cœur destination, m la masse de la donnée, k la constante de raideur du ressort et c la constante de viscosité.

$$m \frac{d^2 x}{dt^2} = \alpha mg \Delta h - c \frac{dx}{dt} - kx$$

Après application d'un changement de variable, d'une simplification et d'une discrétisation temporelle (transformations décrites dans [Dahmani et al., 2014]) nous obtenons l'équation suivante.

$$D_i = 2AD_{i-1} - A^2D_{i-2} + B\Delta h$$

Cette équation détermine la distance $D_i$ entre la donnée et le cœur propriétaire, avec A et B des constantes intégrant les différentes constantes de raideur du ressort, de viscosité et de masse. Elle offre par ailleurs de bonnes propriétés pour une implémentation matérielle : 1) le résultat est dépendant des deux précédentes distances calculées, ce qui n'implique donc pas de conserver un historique de grande taille pour chaque donnée, 2) les opérations mathématiques sont simples et peuvent faire l'objet d'un traitement dans une petite unité matérielle dédiée. Cette équation a été implémentée et évaluée pour être comparée au protocole de glissement de données par défaut, avec des distances de glissement fixées au minimum (1 hop), à la valeur moyenne et au maximum (la taille de la puce moins 2 hops, c'est-à-dire 14 hops). Les résultats sont présentés dans la figure 2.23c et montrent que le protocole masse-ressort trouve un compromis entre les solutions extrêmes et domine la solution consistant à prendre un rayon moyen (la moitié de la puce) en offrant un meilleur taux de succès dans les caches tout en générant moins de hops cumulés.

<figure><img src="image_39.png" /><figcaption>(a) Nombre de succès d'accès au cache (cache hit) en fonction de la distance maximale autorisée entre le cœur propriétaire et la donnée (le rayon) lors de l'utilisation du protocole de glissement de données avec différents scénarios applicatifs.</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>(b) Analogie entre la gestion des données dans un protocole de cache coopératif et le modèle physique masse-ressort.</figcaption></figure>

<figure><img src="image_41.png" /><figcaption>(c) Nombre de hops cumulés et pourcentage de succès d'accès au cache (cache hit rate) pour le protocole de glissement de données à rayon fixe et le protocole masse-ressort.</figcaption></figure>

FIGURE 2.23 – Principe et évaluation d'un protocole de cohérence basé sur le modèle physique masse-ressort. Ces figures sont issues du manuscrit de thèse de Safae Dahmani [Dahmani, 2015]

En conclusion, les processeurs many-cœurs offrent de nouvelles possibilités pour répondre efficacement à la problématique de la cohérence de cache pour les architectures massivement parallèles. Pour les grandes puces, la tendance est de favoriser une organisation plate ou faiblement hiérarchique (un niveau) dans laquelle les PE se voient attribuer
un petit cache local, notamment pour limiter la surface de la circuiterie et contenir le facteur de forme de la puce. Dès lors, pour compenser ce faible espace de stockage local, plusieurs pistes sont explorées : 1) reposer sur un NoC haute-performance permettant d'accéder à la mémoire externe sans faire chuter les performances calculatoires. Cette stratégie peut faire usage de nouvelles technologies telles que l'empilement 3D (3D stacking en anglais) de couches contenant des circuits pour les PE et la mémoire, comme c'est le cas dans la puce INTACT [Vivet et al., 2020]. Les communications verticales permettent alors de diminuer la distance pour accéder aux données. 2) S'inspirer des techniques de coopération et de communication de groupes pour construire un espace de stockage logique tirant partie des caches voisins. Une piste d'étude consiste à déployer des espaces logiques auto-organisants qui s'étendent et se rétractent en fonction des besoins en mémoire exprimés par les processus. Une telle organisation s'apparente à une MVP et rejoint les thématiques de recherche décrites dans le chapitre 3. Enfin 3) offrir des outils à même d'anticiper les accès et optimiser le contenu du cache. Pour cela, nous pouvons imaginer utiliser des algorithmes de recherche opérationnelle, des heuristiques et de l'apprentissage machine en ligne pour détecter des motifs d'accès au cours de l'exécution de l'application et ainsi déclencher des mécanismes de préchargement.

### 2.2.2 Évaluation analytique et simulateurs de réseaux sur puce

> Chaker, H., Cudennec, L., Dahmani, S., Gogniat, G., and Sepúlveda, M. J. (2015). Cycle-based model to evaluate consistency protocols within a multi-protocol compilation tool-chain. In Wang, Z., Petoumenos, P., and Leather, H., editors, Proceedings of the 2015 International Workshop on Code Optimisation for Multi and Many Cores, COSMIC@CGO 2015, San Francisco Bay Area, CA, USA, February 8, 2015, pages 8:1–8:10. ACM.
> 
> [Chaker et al., 2015] Lab-STICC, CEA LIST, École Centrale de Lyon.
> 
> Contributions | ★ initiative ■ idées ☐ implémentation ☐ expérimentations ■ rédaction ☐ présentation

> Cudennec, L., Dahmani, S., Gogniat, G., Maignan, C., and Sepúlveda, M. J. (2016b). Network contention-aware method to evaluate data coherency protocols within a compilation toolchain. In 10th IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip, MCSOC 2016, Lyon, France, September 21-23, 2016, pages 249–256. IEEE Computer Society.
> 
> [Cudennec et al., 2016b] CEA LIST, UPMC, Lab-STICC, TU Munich.
> 
> Contributions | ★ initiative ■ idées ☐ implémentation ☐ expérimentations ■ rédaction ■ présentation

Évaluer les protocoles de cohérence de cache sur des processeurs nécessite bien souvent de recourir à des modèles et des simulations du fait de la complexité ou de l'impossibilité de modifier et substituer un protocole sur une architecture donnée. Différentes méthodes existent, caractérisées par un niveau de précision pour le résultat et une complexité algorithmique pour le temps de calcul, l'optimisation de ces deux caractéristiques étant contradictoire. La méthode analytique utilisée dans les évaluations précédentes (section 2.2.1) permet de déterminer les défauts de cache, de dresser une carte des communications et de générer une heatmap pour identifier les liens et les caches ayant été sollicités. Cette méthode ne permet cependant pas de déterminer les temps d'accès aux données. Dans les travaux suivants, nous avons proposé deux modèles temporels de complexité incrémentale : 1) un modèle basé sur les cycles processeur permettant de calculer le nombre de cycles nécessaires pour chaque accès et 2) un modèle basé sur un simulateur de NoC permettant de calculer la contention sur les liens réseau.

#### La méthode analytique basée sur les cycles processeur

[Chaker et al., 2015] consiste à modéliser les différents types d'accès à une donnée selon sa localisation sur la puce, de décomposer les étapes nécessaires pour y accéder puis de calculer le nombre de cycles processeur requis pour compléter ces étapes. Quatre types d'accès ont été identifiés (représentés sur la figure 2.24a) : 1) l'accès au cache local, 2) l'accès dans le cache d'un voisin, 3) l'accès dans le cache d'un cœur distant et 4) l'accès dans la mémoire externe. Chaque type d'accès a été décomposé en une séquence d'actions sur la puce correspondant au cheminement de la requête à travers les caches, les liens et les routeurs du NoC ainsi que vers la mémoire externe. Pour chaque action il alors possible d'attribuer un coût en nombre de cycles processeur en se basant sur des valeurs fournies par l'utilisateur. Dans ce travail nous avons paramétré le modèle en suivant les recommandations pour la conception des caches fournies dans [Patterson and Hennessy, 2012] et les recommandations pour la conception de la mémoire et du NoC fournies dans [Hennessy and Patterson, 2012].

Les figures 2.24b et 2.24c présentent les résultats obtenus avec les approches analytiques par comptage de messages de CC et par comptage des cycles processeur. L'application est un noyau de convolution de taille 3 exécuté sur une puce de 8 × 8 cœurs avec le protocole de cache masse-ressort. Ces figures montrent bien une forte corrélation entre les messages de CC émis sur chaque cœur et le nombre de cycles processeur dédiés à la réalisation d'une requête d'accès. Une comparaison plus fine des protocoles de cohérence de cache MESI, glissement de données et masse-ressort a de plus été effectuée, notamment en faisant varier les stratégies de pistage des données migrées (comment retrouver un donnée ayant été migrée plusieurs fois et quelle stratégie consomme le plus de cycles processeurs). Les résultats peuvent être
consultés dans [Chaker et al., 2015]. Si cette approche analytique permet d'affiner la modélisation du comportement d'un protocole de CC sur la puce, elle reste cependant éloignée des conditions opérationnelles, notamment car les ressources matérielles sont toujours considérées comme disponibles en l'absence de contention. Une extension de ce travail permet de prendre en compte la contention sur le NoC à l'aide d'un outil de simulation.

<figure><img src="image_42.png" /><figcaption>(a) Quatre types d'accès à une donnée à partir d'un cœur sur un NoC 2D (mesh). 1) accès au cache local, 2) accès dans le cache voisin, 3) accès dans un cache distant et 4) accès dans la mémoire externe.</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>(b) Nombre de messages de CC émis lors de l'exécution d'un noyau de convolution de taille 3. Résultats obtenus selon la méthode analytique basée sur les messages (section 2.2.1).</figcaption></figure>

<figure><img src="image_44.png" /><figcaption>(c) Temps d'accès en nombre de cycles processeur cumulés lors de l'exécution du noyau de convolution. Résultats obtenus en appliquant le modèle analytique basé sur les cycles processeur.</figcaption></figure>

FIGURE 2.24 – Comparaison des résultats d'exécution d'un noyau de convolution pour un protocole de cohérence massressort avec les méthodes analytiques basées sur le rejeu de messages et sur les cycles processeur.

La méthode analytique basée sur un simulateur de NoC [Cudennec et al., 2016b] consiste à préparer une trace d'exécution contenant les accès aux données partagées (en utilisant la méthode précédemment présentée basée sur l'instrumentation du binaire par Pin/Pintools) puis de les rejouer dans un simulateur afin d'observer les phénomènes de contention sur les ressources du NoC. Le simulateur utilisé [Sepúlveda et al., 2007] est écrit en System-C sur le principe de la transaction (TLM (Transaction Level Modelling)) avec une précision au niveau du cycle. Ce simulateur a été choisi car il propose un bon compromis entre précision et rapidité d'exécution. Les fichiers de configuration permettent de décrire et paramétrer une topologie réseau arbitraire, d'injecter des communications puis de récupérer des métriques à l'aide de sondes placées sur les routeurs ou les liens de communication.

L'injection des communications nécessite un horodatage des évènements afin de les cadencer sur la puce simulée. Cette information temporelle n'est cependant pas disponible lors de la constitution des journaux d'accès mémoire à l'aide de l'outil Pin/Pintools (et plus spécifiquement le greffon pinatrace). Ce n'est pas une information critique car ce journal est généré en exécutant l'application sur une architecture hôte potentiellement très différente de l'accélérateur many-cœur cible. Il en résulte un comportement très différent en terme d'entrelacement des accès mémoire, et à fortiori en terme d'horodatage. En conséquence, un cadencement de la trace d'accès mémoire est reconstitué lors de la simulation. Ce cadencement est établi comme suit : 1) un niveau de parallélisme d'injection des accès mémoire est choisi, avec 0% correspondant au rejeu des accès pleinement séquentiels et avec 100% correspondant au rejeu des accès complètement concurrents (la figure 2.25 illustre différents niveaux de parallélisme). Les niveaux de parallélisme intermédiaires sont obtenus en partitionnant le journal d'accès mémoire en autant d'ensembles de traces contiguës dans le journal. Les accès appartenant à un même ensemble sont injectés en parallèle dans le simulateur. Les ensembles d'accès sont traités séquentiellement. De cette manière, il est possible de générer un comportement applicatif plus ou moins dense en terme d'accès mémoire : une configuration plutôt séquentielle permettant au NoC de traiter un évènement avant que le suivant ne se réalise, alors qu'une configuration tendant vers un haut degré de parallélisme génère de la contention sur le réseau.

L'évaluation de l'approche temporelle basée sur un simulateur de NoC a été effectuée pour différentes traces d'accès mémoire, topologies réseau et niveau de parallélisme d'injection d'évènements. La table 2.4 présente les résultats. Les accès mémoire sont générés en déployant des tâches exécutant un noyau de convolution susceptible de saturer rapidement le cache local. La simulation porte sur une puce de taille 8 × 8 cœurs et utilise le protocole MES I + glissement de données. Le mécanisme de coopération est enclenché aux abords des cœurs effectuant les traitements. Ces expérimentations ont permis d'observer de nouveaux phénomènes en comparaison des approches purement analytiques. Un premier résultat porte sur le choix de la topologie du NoC. Une organisation en tore semble intuitivement plus efficace qu'une grille classique car elle étend cette dernière avec de nouveaux liens sur les extrémités. Pour certains jeux de données (1 et 4) ce n'est pas le cas : une explication est que l'absence de voisins sur les quatre bords de la grille permet de préserver l'autre coté de la puce de l'influence croisée des migrations de données dues aux hot spots, tel un brise-lames. Un deuxième résultat porte sur le niveau de parallélisme d'injection des traces. Il montre que certains jeux de données (2 et 5) génèrent de hauts niveaux de contention sur le réseau indépendemment du niveau de parallélisme d'injection. Dans ce cas, le triptyque application-NoC-protocole de cohérence ne fonctionne pas correctement et d'autres combinaisons doivent être évaluées.
<figure><img src="image_45.png" /><figcaption>FIGURE 2.25 – Niveau de parallélisme pour l'injection des accès mémoire dans le simulateur de NoC.</figcaption></figure>

<table><caption>TABLE 2.4 – Temps de simulation du NoC, nombre de cycles simulés et taux de contention maximal observé sur le réseau pour 5 jeux de données correspondant à des accès mémoire générés par des noyaux de convolution. Le protocole de cohérence simulé est MESI + glissement de données présenté en section 2.2.1, sur une puce de taille 8 × 8. Les temps de simulation sont obtenus sur un processeur mobile Intel Core i5-3360M (2012).</caption><thead><tr><th rowspan="2"></th><th colspan="2">Jeu de données</th><th rowspan="2">Temps de simulation (ms)</th><th colspan="2">Topologie (nb. cycles)</th><th colspan="5">% Parallélisme → % Contention</th></tr><tr><th>Données</th><th>Accès</th><th>Grille 2D</th><th>Tore 2D</th><th>0%</th><th>25%</th><th>50%</th><th>75%</th><th>100%</th></tr></thead><tbody><tr><td>Jeu 1</td><td>136</td><td>329</td><td>1549</td><td>7778</td><td>9813</td><td>39%</td><td>39%</td><td>28%</td><td>45%</td><td>57%</td></tr><tr><td>Jeu 2</td><td>265</td><td>669</td><td>963</td><td>89625</td><td>87588</td><td>83%</td><td>88%</td><td>93%</td><td>89%</td><td>95%</td></tr><tr><td>Jeu 3</td><td>598</td><td>3396</td><td>1760</td><td>828885</td><td>772475</td><td>80%</td><td>76%</td><td>87%</td><td>87%</td><td>89%</td></tr><tr><td>Jeu 4</td><td>1071</td><td>3403</td><td>3661</td><td>1836805</td><td>1969467</td><td>66%</td><td>76%</td><td>73%</td><td>80%</td><td>66%</td></tr><tr><td>Jeu 5</td><td>1690</td><td>13758</td><td>10885</td><td>3719665</td><td>3584895</td><td>97%</td><td>81%</td><td>71%</td><td>78%</td><td>92%</td></tr></tbody></table>

**En conclusion**, La méthode analytique par comptage de cycles processeur offre une complexité algorithmique très simple qui permet d'obtenir les résultats sur un temps de calcul court. La précision reste cependant à grosse maille, principalement car l'approche ne prend pas en compte les limitations matérielles de la puce. Le recours à un simulateur de niveau TLM apporte de nouvelles informations sur le taux de contention des liens et des routeurs du NoC, pour un temps de calcul significativement plus important, mais qui reste raisonnable dans le cadre d'une phase de profilage de système complexe. Cette approche n'est cependant pas complète du fait de la génération de journaux d'accès mémoire ne représentant pas l'activité réelle sur la puce : les traces sont générées en exécutant le programme sur un multi-cœur classique et ne contiennent pas les informations de placement-routage ni d'horodatage.

Les trois approches d'évaluation de protocoles de CC (analytique par comptage de messages, temporelle par comptage de cycles processeur, temporelle reposant sur un simulateur de NoC) montrent comment construire incrémentalement un modèle offrant graduellement plus de précision, au prix de complexifier l'implémentation et demander plus de temps de calcul. Comme dans de nombreux domaines, la bonne approche est souvent déterminée par le contexte opérationnel : la ligne directrice que nous avons fixée pour cette thématique de recherche consiste à rendre le choix du protocole de cohérence transparent pour l'utilisateur. Ceci implique de pouvoir explorer différentes solutions : quel protocole déployer, comment le configurer pour telle application s'exécutant sur tel processeur many-cœur ? Dans ce contexte de recherche opérationnelle il est important de pouvoir disposer d'outils d'évaluation des solutions adaptés aux algorithmes d'exploration et d'optimisation, tant sur les critères de précision que de temps de calcul. En ce sens, les contributions effectuées sur l'évaluation des protocoles de CC nous ont permis de réaliser de nombreuses études exploratoires et de proposer une chaîne de compilation pour l'aide à la décision sur la cohérence des données.

### 2.2.3 Aide à la décision pour le choix des protocoles de cohérence

> Dahmani, S., Carpov, S., Cudennec, L., and Gogniat, G. (2015). A multiobjective consistency decision engine for a manycore compilation platform using an evolutionary approach. In Evolutionary Multiobjective Optimization (EMO 2015), held in conjunction with the 23rd Intl. Conf. on Multiple Criteria Decision Making (MCDM 2015), Hamburg, Germany.
> 
> [Dahmani et al., 2015] CEA LIST, Lab-STICC.
> 
> Contributions ★ initiative ■ idées ☐ implémentation ☐ expérimentations ■ rédaction ☐ présentation
<figure><img src="image_46.png" /></figure>

FIGURE 2.26 – Solutions trouvées pour la configuration d'un protocole de cohérence par glissement pour chaque donnée partagée. La configuration porte sur la variation du rayon maximum de glissement. Les critères d'évaluation sont respectivement représentés en abscisse et en ordonnée par le nombre de défauts de caches et le nombre cumulés de hops effectués sur le NoC pour atteindre une donnée. Le front de Pareto apparaît avec des étoiles. Deux solutions dominées sont représentées par des triangles. Cette figure est issue du manuscrit de thèse de Safae Dahmani [Dahmani, 2015].

L'évaluation des protocoles de CC que nous avons proposés a montré qu'il n'existe pas un protocole universel répon-
dant à toutes les combinaisons d'application, de cible matérielle et d'objectifs de performance. Le choix d'un protocole
et sa configuration reste donc dirigé par l'expertise du développeur dans les trois domaines sus-cités, ce qui éloigne
de la compétence purement métier. Une approche légitime est de proposer un système d'aide à la décision permettant
à partir d'une application et d'une architecture cible d'offrir un ensemble de solutions optimales répondant à divers
contextes opérationnels. C'est le principe du front de Pareto pour les problèmes d'optimisation multicritères, qui per-
met de conserver les solutions non-dominées, c'est à dire que pour chacune d'elles, aucune solution meilleure sur tous
les critères n'a été trouvée. Avec un tel outil, l'utilisateur obtient donc automatiquement des configurations adaptées
au déploiement de son application sur la puce, toute l'expertise sur le comportement des protocoles de cohérence se
situant désormais dans une étape d'analyse et de compilation.

La figure 2.26 présente un exemple de front de Pareto appliqué à l'exploration de la configuration du protocole coopératif par glissement de données. La configuration porte sur la distance maximale autorisée pour repousser une donnée de voisins en voisins. Cette distance est potentiellement différente pour chaque donnée partagée. Les deux critères retenus pour évaluer les solutions sont 1) le nombre de défauts de cache et 2) la distance cumulée sur le NoC entre le cœur hébergeant une donnée et le cœur propriétaire. Ces deux critères doivent être minimisés, c'est à dire trouver des solutions qui se rapprochent de l'origine sur cette figure. Cette recherche n'est pas triviale car avec ce protocole de CC, autoriser les données à migrer de caches en caches permet de les conserver sur la puce, ce qui diminue les défauts de cache (absence de requêtes vers la mémoire externe), mais augmente dans le même temps le nombre de hops pour les retrouver, et donc la latence. L'exploration automatique permet alors de sélectionner des solutions jugées satisfaisantes sur ces deux critères puis de les fournir à un autre outil d'aide à la décision en charge d'orienter le choix final. Ceci peut être effectué par pondération des deux critères en se basant sur les caractéristiques techniques de l'architecture ciblée : combien coûtent des accès à la mémoire externe et aux caches distants.

**Un moteur de décision multiobjectifs.** Afin de construire un front de Pareto pertinent, il est nécessaire d'explorer un nombre de solutions suffisamment grand et diversifié pour ne pas tomber dans le piège du minimum local, c'est à dire se cantonner à quelques solutions proches qui semblent bonnes, alors que des solutions meilleures se situent dans des zones non couvertes par l'exploration. La méthode la plus simple est la recherche exhaustive qui évalue toutes les combinaisons possibles et retourne la ou les meilleures solutions possibles. Cette recherche n'est pas applicable lorsque le temps de calcul, qui dépend du nombre de solutions et du temps nécessaire à leur évaluation est trop important. Les méthodes approchées permettent alors d'explorer un sous-ensemble des solutions en dirigeant les recherches à l'aide d'heuristiques et de prédictions. Pour donner un ordre de grandeur, des temps de calcul sont donnés dans la table 2.27a pour comparer une recherche exhaustive et une méthode approchée basée sur un algorithme génétique. La méthode exhaustive est caractérisée par une explosion de la combinatoire qui entraîne une croissance géométrique du nombre de solutions à évaluer, là où la méthode génétique permet de maîtriser le nombre de solutions à évaluer, indépendamment de la complexité du problème (figure 2.27b). Avec des traces de seulement quelques dizaines d'accès mémoire le temps de calcul de la méthode exhaustive devient rapidement déraisonnablement long avec presque 18 heures de calcul pour une trace constituée de seulement 20 accès mémoire.

Dans ce travail nous avons défini le problème d'optimisation de la cohérence de cache de la sorte : une trace d'exé-
<table><thead><tr><th rowspan="2">Taille de la trace</th><th colspan="2">Exhaustif</th><th colspan="2">Génétique</th></tr><tr><th>(s)</th><th>#</th><th>(s)</th><th>#</th></tr></thead><tbody><tr><td>6</td><td>24</td><td>64</td><td>53</td><td>100</td></tr><tr><td>10</td><td>240</td><td>1024</td><td>53</td><td>100</td></tr><tr><td>15</td><td>10312</td><td>32768</td><td>54</td><td>100</td></tr><tr><td>20</td><td>63976</td><td>1048576</td><td>54</td><td>100</td></tr></tbody></table>

(a) Temps de calcul (secondes) nécessaire à l'exploration de la configuration des protocoles de CC pour les algorithmes de recherche exhaustif et génétique, en fonction du nombre d'accès mémoire contenus dans les traces d'exécution. Le rayon de glissement maximal *r* est fixé à 2 pour limiter les temps de calcul. Le nombre de solutions (#) est donc *r*<sup>n</sup> avec *n* la taille de la trace. L'algorithme génétique est configuré pour 10 itérations et une population de 10 individus.

<figure><img src="image_47.png" /><figcaption>(b) Temps de calcul pour l'algorithme génétique.</figcaption></figure>

**FIGURE 2.27** – Comparaison du temps de calcul entre l'algorithme exhaustif et l'algorithme génétique. Expériences menées sur 4 cœurs d'un processeur AMD Opteron 6172. Ces résultats sont issus du manuscrit de thèse de Safae Dahmani [Dahmani, 2015].

cution contient $N$ accès mémoire. Chaque accès mémoire $n \in N$ porte sur une donnée partagée $d$. $P$ est un ensemble de protocoles de CC. Chaque protocole $p \in P$ peut être configuré avec un nombre variable de paramètres. L'ensemble des configurations possibles pour un protocole $p$ est noté $C_p$. Un premier problème consiste à associer pour chaque donnée partagée $d$ un protocole de cohérence $p \in P$. Un deuxième problème consiste à choisir une configuration $c \in C_p$ du protocole de cohérence $p$ à chaque accès mémoire $n$ auquel il est associé. L'espace de recherche est donc potentiellement très grand. Pour limiter le temps calcul, deux solutions complémentaires peuvent être mises en œuvre : 1) limiter la taille de la trace en sélectionnant des parties représentatives de l'exécution et 2) utiliser des algorithmes de RO (Recherche Opérationnelle) adaptés à la résolution de ce type de problèmes, et c'est justement la spécialité des algorithmes génétiques.

Le principe d'un algorithme génétique est de faire évoluer une population définie par un ensemble de solutions (des individus) pendant un certain nombre d'itérations. La taille de la population reste constante mais les individus qui la composent évoluent en appliquant des mécanismes inspirés de la biologie : 1) la sélection permet de conserver un sous-ensemble de solutions plus adaptées aux critères d'évaluation, 2) le croisement permet de recombiner de nouvelles solutions en empruntant des caractères à des solutions existantes et 3) les mutations introduisent de l'aléa en altérant certaines solutions de manière aléatoire. L'efficacité d'un algorithme génétique est en grande partie déterminée par le paramétrage des ces trois mécanismes pour obtenir de bonnes solutions dans la population en un minimum d'itérations. Dans ce travail nous utilisons l'approche FastPGA [Eskandari et al., 2006] qui inclut dans l'étape de sélection des solutions de l'algorithme génétique la notion de solutions dominées pour construire un front de Pareto.

Un facteur de diversité caractérise la distance entre les solutions contenues dans la population, ce qui est obtenu en paramétrant l'ampleur des croisements entre individus et les probabilités de mutation notées $\rho$. Ce facteur de diversité est utilisé à chaque itération pour paramétrer dynamiquement $\rho$ dans l'algorithme génétique, et ainsi conserver une diversité asservie aux générations précédentes. La figure 2.28 présente le front de Pareto obtenu en affichant les solutions trouvées par les trois stratégies : un paramétrage de $\rho$ constant minimal, maximal, et variable. Les résultats montrent que le paramétrage maximal donne de meilleurs résultats que le paramétrage minimal, permettant d'explorer des solutions plus éloignées en terme de configuration. Cependant, l'usage d'un $\rho$ élevé mène à une diversité plus importante et à la possible perte des informations utiles qui ne sont alors plus exprimées sur les individus. Les résultats montrent aussi que le paramétrage dynamique est en mesure de trouver des solutions meilleures qu'un paramétrage maximal, pour un même nombre d'itérations et donc à complexité calculatoire identique : si l'on fusionne les deux fronts de Pareto correspondants au paramétrage maximal et au paramétrage dynamique, des solutions du premier disparaissent, ce qui n'est pas le cas pour le second.

Le moteur de décision multiobjectifs est une brique technologique déterminante pour offrir un système permettant d'automatiser le choix et la configuration des protocoles de CC. En ce sens, le travail réalisé dans le cadre de la thèse de Safae Dahmani est important car il démontre la faisabilité de l'approche en levant un verrou technologique et en s'attaquant à un problème "dur". Cette brique est un élément d'une chaîne de compilation ambitieuse dans laquelle les contributions présentées dans ce manuscrit sont assemblées pour permettre d'automatiser les traitements à partir du code source.

**Une chaîne de compilation pour le choix d'un protocole de CC.** Choisir et paramétrer des protocoles de cohérence est une tâche complexe : le comportement des protocoles, et donc leur performance, dépend de nombreux paramètres tels que les motifs d'accès mémoire générés par l'application, la configuration du déploiement, les caractéristiques de la plateforme matérielle et les objectifs en terme de performance calculatoire ou énergétique. Rendre ce
<figure><img src="image_48.png" /><figcaption>FIGURE 2.28 – Front de Pareto obtenu pour le paramétrage du protocole de cohérence de glissement de données en appliquant l’algorithme génétique FastPGA sur une trace contenant 2080 accès mémoire. Les solutions proches de l’origine sont les meilleures. Les points verts correspondent à une faible probabilité de croisement et de mutation, les points rouges à une forte probabilité et les points bleus à une probabilité variable calculée dynamiquement à chaque itération. Cette figure est issue du manuscrit de thèse de Safae Dahmani [Dahmani, 2015].</figcaption></figure>

service de décision de manière transparente à l'utilisateur fait donc intervenir de nombreuses étapes spécialisées dans l'analyse et l'évaluation de ces paramètres. Le développement de la thématique sur la cohérence des données pour les architectures many-cœurs a permis de dessiner une vision plus globale du problème dans laquelle les contributions deviennent complémentaires et forment un processus de compilation. La figure 2.29 illustre l'organisation d'une telle chaîne de compilation. Cette dernière est constituée des étapes suivantes :

1. Un code source décrivant une application parallèle est fourni en entrée,

2. (a) Le code source est compilé sur la plateforme hôte et le binaire est instrumenté (par exemple par Pin/Pintools),

(b) Le binaire est exécuté sur la plateforme hôte et différentes traces d'exécution sont collectées afin de constituer une base représentative des accès aux données partagées,

3. (a) Le code source est analysé par un outil d'analyse statique de code (par exemple Frama-C [Kirchner et al., 2015]) permettant d'extraire les accès aux données partagées et de construire un graphe de dépendances entre ces accès,

(b) Un partitionnement des accès est produit, reflétant les différentes phases de fonctionnement de l'application, par exemple *initialisation*, *calcul*, *terminaison*...

4. Une brique de décision associe à chaque accès mémoire une configuration du protocole de cohérence choisi pour cette donnée partagée. Pour ce faire, cette brique de décision prend en entrée une bibliothèque de protocoles de CC ainsi que des objectifs et des fonctions de coût. Les solutions explorées peuvent être évaluées en faisant appel à un modèle analytique ou temporel présentés précédemment,

5. Les décisions sont inscrites dans le logiciel système généré et appliquées lors du déploiement sur la cible matérielle.

Plusieurs étapes de cette chaîne de compilation ont été conçues, implémentées, expérimentées, combinées et ont donné lieu à des publications. Certaines étapes n'ont cependant pu être suffisamment étudiées, ce qui n'a pas permis d'effectuer des expérimentations de *bout en bout*, ni d'observer si l'optimisation des mécanismes de cohérence entraîne un bénéfice réel au niveau applicatif (les démonstrations ont été effectuées à l'aide de modèles analytiques). C'est le cas de l'analyse statique de code et de la génération du logiciel système pour appliquer les décision de cohérence à l'exécution. 1) Pour l'analyse statique de code, des travaux préliminaires ont été menés dans le cadre de deux stages de master co-encadrés avec Selma Azaiez et Safae Dahmani au CEA. Ces stages ont donné lieu à la construction d'un modèle représentant les dépendances entre les accès aux données, basée sur la relation de causalité et des outils tels que les réseaux de Pétri et les arbres de décision. Ces travaux préliminaires sont présentés dans [Dahmani, 2015]. 2) L'application des configurations de protocoles de CC sur la plateforme cible renvoie au problème du déploiement ou de la substitution des protocoles de cohérence dans les processeurs. Cette opération est difficilement implémentable au niveau matériel ou au niveau système d'exploitation. L'approche la plus simple consiste à fournir un intergiciel de gestion de données partagées implémenté au niveau utilisateur. Un tel intergiciel s'apparente à une MVP dans laquelle l'utilisateur a toute la liberté d'expérimenter des stratégies de cohérence. Malheureusement, la MVP présentée en section 3.1 était encore aux toutes premières étapes de sa conception lorsque nous avons refermé cette thématique
<figure><img src="image_49.png" /><figcaption>FIGURE 2.29 – Chaîne de compilation pour le choix et le paramétrage de protocoles de CC. Les étapes n'ayant pu être menées jusqu'à l'implémentation dans cette thématique de recherche sont l'analyse statique de code et la génération du logiciel système en charge de l'application des décisions de cohérence sur les accès mémoire.</figcaption></figure>

de recherche. Ceci rappel l'importance d'assurer la maîtrise des outils nécessaires à l'évaluation des prototypes de recherche, de concert avec la temporalité des projets engagés.

**En conclusion,** concevoir un système d'optimisation de la cohérence des données, transparent pour l'utilisateur, repose sur deux principales difficultés : 1) la brique de prise de décision doit faire face à un nombre important de combinaisons possibles. L'évaluation des solutions est coûteuse, ce qui implique l'utilisation de méthodes approchées pour maîtriser la combinatoire. Sur ce point, l'utilisation de l'algorithme génétique FastPGA répond à la problématique tant sur le plan de la complexité calculatoire que sur la qualité des résultats. 2) Cette brique de prise de décision doit être correctement alimentée avec une description fidèle du comportement de l'application. Les applications parallèles considérées dans ce travail sont écrites en langage C et le parallélisme est exprimé dans le modèle *Posix Threads*, en conformité avec les recommandations de Frama-C, ce qui offre un grand degré d'expressivité sur le plan du langage. Cette expressivité rend difficile l'analyse de l'application parallèle et plus spécifiquement lorsque celle-ci est caractérisée par des accès irréguliers à la mémoire. Ces accès irréguliers sont souvent générés par des imbrications complexes de boucles (*for*, *while*) dont les bornes peuvent parfois être uniquement connues à l'exécution. Une approche possible est de recourir au modèle polyédrique [Benabderrahmane et al., 2010] qui offre un cadre algébrique pour représenter l'imbrication des boucles sous forme de polyèdre. Cette représentation permet ensuite d'effectuer des optimisations sur des parties complexes du code et fait le lien avec la compilation du parallélisme et l'ordonnancement des instructions basés sur l'analyse des boucles imbriquées [Karp et al., 1967]. L'analyse statique d'applications parallèles reste un sujet de recherche ouvert et il est bien souvent tentant de demander à l'utilisateur de décorer son code pour aider le compilateur à identifier les variables partagées et les accès concurrents. Une telle solution rend l'approche moins transparente pour l'utilisateur et demande un travail supplémentaire pour porter les applications existantes. Par ailleurs, la décoration de code est un premier pas vers l'utilisation de modèles de programmation fortement structurés, tels que le flot-de-données, pour lequel le déploiement d'un protocole de cohérence est rendu caduc par la pré-planification et la synchronisation des accès mémoire. Une autre perspective est l'utilisation des techniques d'IA pour l'optimisation des protocoles de cohérence. Cette technique est déjà appliquée à la problématique du préchargement de données dans les caches [Hashemi et al., 2018] et il est possible d'imaginer qu'elle soit étendue au choix et à la configuration du protocole de cohérence. Enfin, la conception d'une chaîne de compilation universelle incluant des étapes pour l'optimisation des mécanismes de cohérence des données, et capable d'analyser des programmes parallèles exhibant des accès irréguliers en mémoire reste peut-être aujourd'hui un objectif illusoire : une approche plus pragmatique relevant plus du principe de l'aide à la décision et s'attelant à conserver l'expertise du développeur dans la boucle.
## 2.3 Discussion

Les processeurs many-cœurs représentent une architecture de calcul particulière, concentrant les problématiques classiques des systèmes distribués à l'échelle d'une puce de calcul. La gestion des données partagées, le placement des tâches et d'une manière plus générale le modèle de programmation sont des thématiques bien maîtrisées pour les architectures multi-cœurs. Cependant, dans le contexte des many-cœurs, ces thématiques se heurtent au passage à l'échelle et leur résolution devient critique pour permettre une exploitation efficace des ressources sur la puce. En 2007, lorsque le français Kalray se lance dans la conception d'une telle puce, le MPPA 256 cœurs représente une architecture à l'état de l'art, si ce n'est en avance sur ses compétiteurs Intel et Tilera offrant alors des puces entre 60 et 100 cœurs. Dans ce contexte le laboratoire commun entre le CEA et Kalray a constitué une opportunité unique pour la conception finement liée d'une architecture matérielle et d'un environnement d'exploitation logiciel. Cela a aussi été l'occasion de concilier projet industriel et activités de recherche au sein du laboratoire commun, avec toutes les fertilisations croisées qui ont donné lieu au transfert technologique réussi de la chaîne de compilation Σ-C, ainsi qu'à de nombreuses publications dans des conférences internationales.

**Retour d'expérience sur Σ-C.** Proposer un nouveau langage pour programmer un accélérateur est un choix audacieux et difficile à justifier : les concepteurs d'applications, que ce soit dans les milieux académique ou industriel restent attachés à des langages éprouvés, possiblement moins adaptés à l'architecture ciblée, mais offrant de fortes garanties pour la réussite et la pérennité du projet. Ainsi la maturité du langage et le suivi du compilateur, le support pour l'aide, l'importance de la communauté active, la portabilité du code sur différentes architectures sont autant de critères pouvant justifier un tel choix. L'absence d'ouverture de Σ-C à la communauté internationale explique que le langage n'a jamais été utilisé en dehors de la sphère de développement. Cette stratégie du secret se traduit par plusieurs problématiques critiques : 
1) le projet ne peut bénéficier d'un retour de la communauté scientifique à même d'orienter les choix de conception pour coller au mieux aux besoins des utilisateurs, 
2) lorsque le langage est révélé, aucune communauté scientifique n'est constituée et certaines contributions ne sont plus à l'état de l'art face à une concurrence importante dans le domaine et 
3) le choix de ne pas diffuser la chaîne de compilation sous licence libre exclut de facto la possibilité de tester, comparer et de s'impliquer dans le projet, le reléguant ainsi au statut de produit fantôme.

Pour autant, les briques technologiques constituant la chaîne de compilation Σ-C ont une grande valeur scientifique et technologique, valorisées individuellement dans des publications internationales. De plus, la chaîne de compilation a permis d'exploiter très tôt le parallélisme offert par la puce MPPA, ce qui est une véritable réussite. Dans un projet tel que Σ-C, plusieurs initiatives peuvent être envisagées pour capitaliser sur les travaux engagés. 
1) Distribuer sous licence libre les premières étapes de la chaîne de compilation comprenant le parseur, la construction du flot-de-données et les étapes nécessaires au paramétrage d'un intergiciel d'exécution générique, pour un portage Posix ou OpenMP [Louise, 2017]. Cette approche vise à promouvoir le langage Σ-C tout en préservant la propriété intellectuelle sur les briques d'optimisation de la puce Kalray MPPA. 
2) Proposer un compilateur source-à-source permettant de traduire des programmes écrits dans des langages flot-de-données ou assimilés vers du Σ-C, par exemple du Streamit ou de l'OpenCL. Cette approche permet de bénéficier de la base applicative de ces langages source et d'effectuer une comparaison sur les performances des compilateurs respectifs.

Si le constat peut sembler sévère sur la stratégie suivie pour le développement de Σ-C, il n'en reste pas moins que l'expertise acquise dans le laboratoire suite à ce projet s'est traduite par de nombreuses innovations dans le domaine des DSL pour le flot de données, notamment pour le temps-réel critique mixte [Louise et al., 2014] ou les many-cœurs en général [Goubier et al., 2014].

**Le many-cœur et l'hétérogénéité.** L'une des forces des architectures many-cœur, le nombre élevé de cœurs, constitue aussi leur faiblesse : comment tirer partie efficacement de toutes ces ressources, en alimentant de manière homogène les unités de calcul ? Si les applications de traitement du signal peuvent facilement bénéficier de ce type d'architecture, de nombreuses applications présentant moins de régularité dans la décomposition des tâches et des accès mémoire peinent difficilement à passer à l'échelle sur des centaines de cœurs. Avec le développement des applications liées à l'IA, notamment pour l'apprentissage machine, les nouvelles architectures de calcul incluent désormais des unités de traitement spécialisées dans la réalisation de convolutions et d'opérations vectorielles. Cette tendance est perceptible pour certains many-cœurs (MPPA Coolidge, MN-Core) dont l'architecture devient hétérogène. Ceci introduit de nouvelles problématiques sur le plan matériel (moins de régularité pour une circuiterie plus complexe) et sur le plan logiciel (comment sélectionner et déployer des noyaux de calcul issus d'applications sur certaines parties matérielles de la puce). Mais l'hétérogénéité dans les architectures de calcul n'est pas une nouveauté, comme nous allons le voir dans le chapitre suivant, et les many-cœurs sont partie intégrante de cette évolution. □

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