La programmation par contraintes : une nouvelle approche pour la conception et la compilation pour architecture reconfigurable à gros grain 

Télécharger le fichier pdf d’un mémoire de fin d’études

Architectures reconfigurables

Origines et définitions

Aujourd’hui encore, le terme reconfigurable est associé aux « circuits logiques program-mables » et surtout au type d’architecture qui l’a popularisé, le FPGA (Field-Programmable Gate Array). Introduit sur le marché au milieu des années 80 par l’un des leaders mon-diaux actuels (Xilinx), le FPGA est formé de trois différents éléments de base : la table de correspondance ou LUT (Look Up Table) ou encore CLB (Configurable Logic Bloc) selon le fabricant, le multiplexeur et la bascule. A noter que la notion de reconfigurable, telle qu’on la connaît aujourd’hui, est bien plus ancienne et pourrait être attribuée à Estrin qui présente dans son papier de 1960 (récemment évoqué dans [39]) une architecture hybride composée d’un processeur standard et d’une matrice matérielle « reconfigurable ».
Définition 1.1 : Une architecture reconfigurable est une architecture capable de modifier son comportement par la modification du schéma de connexion entre ses éléments de base.

Évolutions

Les architectures reconfigurables ont énormément évolué ces dernières années pour sa-tisfaire des besoins applicatifs toujours croissants. Une des évolutions est apparue comme incontournable pour exploiter pleinement la flexibilité apportée par les FPGA ; il s’agit de la reconfiguration dynamique. En effet, avant cette évolution, il fallait arrêter toute activité sur le composant avant de pouvoir en modifier son comportement et obtenir ainsi une nou-velle fonctionnalité. C’est à la fin des années 90 que la reconfiguration dynamique partielle est apparue sur les composants Xilinx notamment, permettant d’améliorer le compromis performance/flexibilité.
Parmi ces évolutions, on trouve aussi l’apparition de différents niveaux de reconfigura-tion : du plus petit (niveau bit) au plus gros (unité fonctionnelle), on parle de granularité ou de grain de reconfiguration. Les caractéristiques d’une architecture reconfigurable va-rient selon la granularité à laquelle elle peut être reconfigurée. On distingue communément trois niveaux de reconfiguration : logique, fonctionnel et système.

Reconfiguration au niveau logique (grain fin)

La reconfiguration au niveau logique appelée aussi reconfiguration à grain fin est typi-quement représentée par les systèmes FPGA1 . Leur reconfiguration se fait au niveau bit ce qui permet une grande flexibilité, comme notamment d’adapter la largeur des données en fonction des besoins. Mais à ce niveau, certains désavantages apparaissent.
Tout d’abord, on observe qu’une grande partie de la surface d’un circuit FPGA est occupée par les multiplexeurs et les bascules utilisées pour réaliser le câblage entre éléments logiques réalisant la fonctionnalité souhaitée et que ces derniers n’occupent qu’une faible surface. De plus, les outils de placement et de routage (P&R) utilisés pour configurer un FPGA sont très complexes et peu efficaces car le problème de P&R est connu pour être difficile à résoudre. Cela l’amène même à être considéré comme « nuisible » par Hartenstein qui écrit : « Avec de sévères difficultés, les FPGA commercialisés routent dans la plupart des designs moins de 80-90% des LUT disponibles et même dans certains cas seulement environ 50% » [52].
Le coût global de la reconfiguration est un autre désavantage majeur. En effet, la mé-moire utilisée pour stocker les différentes configurations, le temps et l’énergie nécessaires pour effectuer une reconfiguration (importants transferts de données de configuration) sont loin d’être négligeables dans la conception d’un système sur FPGA.
Parmi les solutions proposées pour pallier ces désavantages, les architectures reconfi-gurables à un plus gros grain ont fait leur apparition.

Reconfiguration au niveau fonctionnel (gros grain)

Ce niveau de reconfiguration, nommé aussi reconfiguration à gros grain, permet d’amé-liorer la surface, la consommation et la performance des systèmes comparés aux FPGA tout en en maîtrisant la perte de flexibilité pour ne pas la rendre pénalisante. Selon [41], on peut observer deux principales familles d’architecture : les architectures orientées chemin de données et celles orientées instructions. Dans la première famille, la fonctionnalité des unités de calcul est fixée par une étape de configuration et le flot de données entre ces unités est organisé par un contrôle spécifique sur les interconnexions. Dans la seconde, chaque élément exécute une suite d’opérations définies par un élément de contrôle à partir d’une instruction. Il existe aussi des architectures pouvant supporter les deux types de fonctionnement.

Reconfiguration au niveau système

Les architectures reconfigurables au niveau système, communément appelées proces-seurs programmables, sont des architectures purement orientées instructions. Plusieurs modèles, plus ou moins anciens, ont été proposés en fonction de la manière dont sont dé-finies et traitées les instructions. On différencie ainsi principalement les processeurs dont le jeu d’instructions est réduit (RISC – Reduce Instruction Set Processor ) ou complexe (CISC – Complex Instruction Set Processor ) ; ceux dont on sépare le flot d’instructions et de données comme le modèle d’architecture Harvard des processeurs de traitement du signal (DSP – Digital Signal Processor ) dans lequel sont physiquement séparées les mé-moires d’instructions et de données ainsi que les bus associés ; ou encore les processeurs qui adressent plusieurs unités fonctionnelles en parallèle dans la même instruction, exploitant ainsi le parallélisme d’instructions (processeurs VLIW – Very Long Instruction Word ) ; enfin ceux qui comportent des mécanismes matériels complexes permettant une exécution concurrente des instructions (processeurs superscalaires) et ceux qui sont capables d’exé-cuter des instructions vectorielles (processeurs vectoriels).

Reconfiguration à plusieurs niveaux

Certaines architectures supportent plusieurs niveaux de reconfiguration comme c’est le cas de l’architecture DART présentée plus loin (1.4.1) qui combine l’utilisation d’un bloc FPGA pour les traitements logiques et de plusieurs blocs reconfigurables à gros grain pour les traitements arithmétiques.

Remarque

Plusieurs classifications ont été proposées concernant les architectures reconfigurables, permettant ainsi de mieux appréhender leur diversité. Le lecteur souhaitant élargir son champ de connaissance sur la diversité des architectures reconfigurables peut se référer à la taxonomie publiée par Radunovic [90] qui sert souvent de référence.

Architectures reconfigurables à gros grain

Les CGRA représentent une alternative pour la conception de systèmes embarqués multimédia où les contraintes de taille, de consommation énergétique, de performance mais aussi de flexibilité sont très fortes. Elles sont un compromis entre les FPGA dont la grande flexibilité a des conséquences négatives pour une intégration dans un système embarqué en particulier sur les aspects de consommation énergétique et de densité d’intégration, et les processeurs programmables dont la généricité implique une sous-utilisation des ressources et donc une taille et une consommation énergétique plus importante qu’une CGRA.
La définition précédente d’une architecture reconfigurable (cf. 1.1.1) est un peu for-melle et bien adaptée au FPGA. Elle peut être élargie comme telle.
Un système reconfigurable est un système capable d’adapter ses ressources en fonction d’un traitement. « Une architecture matérielle est généralement constituée d’une collection d’éléments de calcul, de stockage et d’un dispositif d’échange d’informations entre ces élé-ments et, éventuellement, d’un contrôleur pour gérer l’ensemble. Une configuration précise à la fois la fonctionnalité des éléments et les chemins de données entre ces éléments, voire le contrôle. Le terme reconfiguration apporte, quant à lui, une notion supplémentaire de dynamicité. Il exprime le fait qu’une configuration n’est pas fixée définitivement (comme pour les circuits ASIC2 ), mais qu’il existe un mécanisme qui, au cours du temps, puisse modifier à la fois la fonctionnalité des éléments de calcul et leur interconnexion. » [34].
Il est alors plus aisé de définir la notion de CGRA en opposition au grain fin.
Définition 1.2 : Contrairement aux architectures reconfigurables à grain fin, la reconfi-guration d’une CGRA s’effectue sur des chemins de données dont la taille est supérieure au bit.
Un grand nombre de CGRA ont été proposés ces dernières années. Hartenstein propose de revisiter dix ans de recherche et de développement sur le reconfigurable (1990-2000) démontrant que cet axe de recherche est prometteur et mettant en avant le besoin de mettre en place des outils de compilation performants pour tirer pleinement partie de ces architectures [53]. De nombreuses autres études sur les systèmes reconfigurables et les méthodes de conception et de compilation associées ont été publiées ces dernières années [60, 111, 108, 109, 28]. Chacune de ces études présente les problématiques liées à la concep-tion et à la programmation des CGRA sous différents angles.
Celle de Theodoridis [108] nous est apparue comme particulièrement pertinente au vu des travaux présentés dans cette thèse car elle est dédiée au CGRA et elle propose de les différencier en fonction de leur flexibilité et ainsi de les classer en deux catégories : les systèmes spécifiques à un domaine d’application notés ADSS (Application Domain-Specific System) et les systèmes spécifiques à une classe d’applications notés ACSS (Application Class-Specific System), la première catégorie étant plus flexible que la seconde. Cette dis-tinction permet d’adapter la méthode de conception d’une CGRA en fonction du type d’architecture choisi selon les caractéristiques du spectre applicatif ciblé mettant en rela-tion trois aspects majeurs : le modèle d’architecture (ici ADSS ou ACSS), les applications (domaine ou classe) et le flot de conception et de compilation. Cette relation est discutée à la fin de ce chapitre.
Une chose est claire, la caractéristique omniprésente dans les CGRA de tout type réside de façon incontestable dans le fait qu’elles sont conçues pour accélérer des applications et que donc l’adéquation architecture application est au cœur des problématiques rencontrées lors de leur conception.

Couplage Processeur – CGRA

La place d’une CGRA au sein d’un système sur puce (ou SoC pour System on Chip) peut varier. La majorité du temps, une CGRA est associée à un processeur programmable qui exécute le reste de l’application, c.-à-d. hors parties critiques ou potentiellement accé-lérables. Ce dernier possède une mémoire locale de type cache. La notion de couplage est utilisée pour exprimer la relation entre le processseur et la CGRA. La figure 1.1, adaptée de [109], illustre les différents types de couplage ainsi que les dénominations associées. Du plus proche au plus éloigné du processeur (noté CPU sur la figure pour Computational Processing Unit ce qui signifie littéralement « unité centrale de traitement »), les types de couplage sont :
– L’extension du chemin de données d’un processeur par une ou plusieurs unités recon-figurables à gros grain (figure 1.1(a)), on parle communément d’ASIP (Application-Specific Instruction-set Processor ). Dans ce cas, la spécialisation prend la forme de nouvelles instructions disponibles pour le compilateur ou pour le programmeur. Les deux modèles d’exécution, séquentielle ou parallèle, peuvent être utilisés.
– Le co-processeur (figure 1.1(b)), c’est un schéma dans lequel le processeur contrôle la CGRA en lui attribuant des tâches de calcul intensif courtes qui ne requièrent pas ou peu de contrôle, ainsi le processeur peut exécuter des tâches en parallèle. La mé-moire cache est partagée entre le processeur et le coprocesseur ce qui implique la mise en place de mécanismes de synchronisation plus complexes que dans le cas précédent.
– Un couplage intermédiaire (figure 1.1(c)) dans lequel, à l’inverse du co-processeur, le cache n’est pas visible par la CGRA. Dans ce cas, cette dernière est plus autonome et accède uniquement à la mémoire externe (mémoire globale partagée) à travers les interfaces d’entrée/sortie partagées avec le processeur.
– L’accélérateur (figure 1.1(d)), c’est le couplage le plus lâche dans lequel la CGRA est autonome vis-à-vis du processeur. Les communications avec celui-ci étant lentes, ce type de couplage est intéressant lorsque la CGRA prend en charge de longues périodes de calculs ne nécessitant que très peu de communications avec le CPU.

Synthèse et fusion de motifs de calcul

Une fois l’identification des motifs de calcul effectuée, ceux-ci sont synthétisés pour être implémentés en tant qu’unités spécialisées. Par exemple, dans le cas d’un ASIP dont le modèle contient une seule extension reconfigurable (RPU), ces motifs doivent-être syn-thétisés en une seule unité. Dans l’idéal, cette synthèse doit assurer le meilleur compromis surface-performance. Il existe plusieurs méthodes pour « fusionner » des motifs de calcul et elles sont prin-cipalement issues de recherches sur les architectures reconfigurables. La majorité des mé-thodes utilise une modélisation des motifs de calcul sous forme de graphe acyclique orienté où chaque nœud représente une opération et chaque arc un transfert de données. Ainsi les algorithmes proposés sont logiquement issus de la théorie des graphes comme celui d’iso-morphisme de sous-graphes utilisé dans [27] par exemple. Le problème d’isomorphisme de sous-graphes est connu pour être NP-complet [36] et donc les méthodes qui permettent de le résoudre sont de deux sortes : les méthodes exactes, utilisant l’ILP par exemple, et les méthodes basées sur des heuristiques comme dans [81] ; les premières pouvant permettre de prouver la pertinence des secondes.
Katherine Compton propose dans sa thèse [29] trois méthodes pour partager les liaisons entre unités de calcul et ainsi limiter l’ajout de multiplexeurs et de démultiplexeurs lors du routage des données. Les trois algorithmes proposés : un algorithme glouton, un bipartite et un basé sur la recherche d’une clique, utilisent des heuristiques basées sur la notion de similarité qui, dans ces travaux, est exprimée de deux manières différentes. Les résultats montrent que d’une manière générale, la méthode basée sur la clique est la meilleure.
D’autres approches ont été proposées. Par exemple Brisk dans [17] se base sur un al-gorithme permettant de trouver la plus grande sous-séquence commune entre deux (ou plus) séquences (ou chaines de caractères) pour transformer un ensemble d’instructions spécialisées en un unique chemin de données matériel capable d’exécuter toutes ces ins-tructions. La solution proposée donne de bon résultat comparée à une synthèse par ILP qui n’exploite pas le partage de ressources avec 85,33% de surface en moins.
La contribution que nous avons jugée la plus pertinente pour débuter nos recherches sur ce sujet a été proposée par les chercheurs de Princeton dans le cadre du projet Mescal [3]. Ce projet propose un environnement de conception pour le développement d’architecture spécifique à une application [57]. Pour chaque partie critique de l’application, un chemin de données optimal est extrait. Ces chemins de données sont ensuite fusionnés (ou combi-nés) dans un seul chemin de données reconfigurable, une RPU. Le but de la fusion est de partager au mieux les unités de calcul matérielles ainsi que les interconnexions pour mini-miser la surface de la RPU. Suite à ces travaux, Moreano propose dans [81] une méthode quasi optimale pour la fusion de chemins de données mais sans maîtriser la performance de la RPU résultante. Cette lacune a été comblée par l’une des contributions présentées dans cette thèse.

Méthodologie de déploiement

La mise en place de la méthodologie de déploiement (ou mapping) représente l’une des étapes les plus difficiles à traiter dans le flot de conception et de compilation pour CGRA.
Comme nous l’avons dit dans l’introduction, l’étape d’ordonnancement, de placement et de routage est au cœur de l’outil de conception et de compilation pour CGRA. La figure 1.8 issue de [108] positionne cette étape au centre du flot de développement d’un ADSS. Durant cette étape, les trois principaux problèmes interdépendants que sont l’ordonnancement des opérations, l’assignement aux RPU et le routage des données sur le ou les réseaux d’interconnexion doivent être résolus.
A l’inverse des systèmes classiques, l’approche dans la conception de CGRA et de la chaine d’outils associés consiste à disposer d’une architecture simple et de repousser la complexité au niveau des outils. En effet, les architectures des processeurs généralistes récents de type superscalaire (comme les dernières versions de Pentium d’Intel ou de PowerPC d’IBM) sont très complexes, à tel point que certaines instructions machine ne sont pas exploitables ou atteignables par le compilateur ; ce qui est couramment le cas de l’instruction de décalage circulaire.
De plus, en comparaison d’une synthèse de haut niveau, les problèmes lors du déploie-ment d’un algorithme sur CGRA sont plus difficiles à résoudre, car dans notre cas les RPU sont connues ainsi que les propriétés du réseau d’interconnexion. La prise en compte de ces contraintes, associée à la forte corrélation des problèmes en font un axe de recherche privilégié.
De nombreuses approches ont été proposées pour résoudre le problème de déploiement d’une application, ou une partie, sur une CGRA. Toutes diffèrent du fait qu’elles ont été conçues pour une architecture particulière, c’est pourquoi nous les présenterons dans la section suivante en même temps que l’architecture, ou le type d’architecture, pour laquelle elles ont été développées.

Sélection de CGRA pour les applications multimédia

Parmi les différentes classifications proposées dans la littérature nous avons choisi celle de T. Cervero [24] concernant les architectures reconfigurables dynamiquement dédiées aux applications multimédia. Cette étude distingue trois grandes familles d’architecture en fonction du degré de couplage (cf 1.2.1) et du type d’unités de calcul : les matrices d’unités fonctionnelles (couplage intermédiaire), les architectures hybrides (coprocesseur) et les matrices de processeur (accélérateur). Le tableau 1.2 donne un récapitulatif des architectures reconfigurables pour les applications multimédia développées depuis 1996 jusqu’à 2009 et la figure 1.9, la classification issue de T. Cervero.

Table des matières

Introduction
1 Architectures reconfigurables à gros grain – État de l’art 
1.1 Architectures reconfigurables
1.1.1 Origines et définitions
1.1.2 Évolutions
1.2 Architectures reconfigurables à gros grain
1.2.1 Couplage Processeur – CGRA
1.2.2 Principales caractéristiques d’une CGRA
1.3 Problématiques de conception d’une CGRA
1.3.1 Prétraitement
1.3.2 Génération d’architecture
1.3.3 Méthodologie de déploiement
1.4 Sélection de CGRA pour les applications multimédia
1.4.1 DART
1.4.2 Montium
1.4.3 ADRES
1.4.4 Silicon Hive
1.5 Synthèse
2 La programmation par contraintes : une nouvelle approche pour la conception et la compilation pour architecture reconfigurable à gros grain 
2.1 Bases de la programmation par contraintes
2.1.1 Problème de satisfaction de contraintes
2.1.2 Contraintes
2.1.3 Algorithme de réduction de domaine
2.1.4 Mécanisme de propagation
2.1.5 Mécanisme de recherche de solutions
2.1.6 Modélisation
2.2 Application à la conception et à la compilation pour architectures embarquées 51
2.3 Application à la conception et à la compilation pour architectures reconfigurables
2.3.1 Modélisation d’une application
2.3.2 Modélisation d’une architecture
2.3.3 Notre méthodologie
2.3.4 UPaK et DURASE deux systèmes pour la conception et l’utilisation d’extensions reconfigurables pour ASIP
2.4 Conclusion
3 Modèle de contraintes pour la fusion d’unités fonctionnelles reconfigurables 
3.1 État de l’art sur la fusion de chemins de données dans le cadre de la synthèse d’architecture matérielle
3.1.1 Algorithme basé sur la recherche d’une clique de poids maximum
3.1.2 Concept de contournement d’opérateur
3.1.3 Positionnement de la contribution au regard de l’état de l’art
3.2 Modèle de contraintes pour la fusion de chemins de données
3.2.1 Aperçu de l’algorithme
3.2.2 Intégration et généralisation du concept de contournement d’opérateur
3.2.3 Conditions de compatibilité entre appariements
3.2.4 Modèle pour la recherche de clique de poids maximum
3.2.5 Modèles pour le problème d’augmentation du chemin critique
3.3 Résultats
3.3.1 Comparaison avec l’approche de Moreano
3.3.2 Résultat sur un ensemble d’applications multimédia
3.4 Conclusion et perspectives
4 Modèles de contraintes pour le déploiement d’applications sur CGRA
4.1 Introduction
4.2 Contexte : Architecture ROMA
4.2.1 Applications ciblées
4.2.2 Architecture ROMA
4.2.3 Adéquation application, architecture et CP
4.2.4 Déploiement pour l’exploration de l’espace de conception
4.3 Modélisation de CGRA
4.3.1 Modèle d’architecture pour l’exploration de l’espace de conception
4.3.2 Modèle d’architecture pour la génération de configurations
4.4 Déploiement d’une application avec optimisation du temps d’exécution
4.4.1 Modèle de contraintes
4.4.2 Résultats
4.5 Déploiement d’une application sur un modèle d’architecture pipelinée
4.5.1 Modèle d’architecture pipelinée
4.5.2 Problématique
4.5.3 Exemple illustratif
4.5.4 Couverture de l’AG avec des motifs de calcul
4.5.5 Modèle de contraintes
4.5.6 Exemple détaillé
4.5.7 Résultats
4.6 Génération de configurations
4.6.1 Fichiers de configurations
4.6.2 Génération d’adresses
4.6.3 Gestion des déclenchements des configurations
4.6.4 Validation du flot complet
Conclusion et perspectives 
Glossaire 
Publications 
Bibliographie

Télécharger le rapport complet