Architectures reconfigurables
Cette section présente les architectures reconfigurables de manière chronologique. En commençant par les prémisses de ce type de composants, leurs différentes fonctionnalités et spécificités sont introduites au fur et à mesure pour finalement présenter les architectures hétérogènes reconfigurables dynamiquement qui correspondent aux circuits considérés dans nos travaux.
Architectures configurables : Les architectures configurables sont des architectures pouvant être adaptées à un algorithme précis, de manière flexible mais définitive. La première architecture de ce type est le PAL (Programmable Array Logic) présentée par Monolithic Memories en 1978. Ce type d’architecture offre un compromis entre un circuit dédié et un processeur. En effet, elle apporte une certaine flexibilité par rapport aux circuits dédiés et des performances accrues par rapport aux processeurs généralistes. Cependant, les architectures PAL présentent l’inconvénient de n’être configurables qu’une seule fois.
Architectures reconfigurables : Afin de pallier à cette contrainte de configuration définitive des architectures PAL, les fabricants ont développé de nouvelles technologies. Ainsi, LATTICE présente, en 1985, la technologie GAL (Generic Array Logic) permettant d’effectuer une configuration de l’architecture à chaque initialisation du circuit. La même année, la société Xilinx présente également un nouveau type d’architectures reconfigurables , les FPGA. Ce type d’architecture domine désormais le marché des architectures reconfigurables. Les FPGA sont réalisés par un assemblage de trois fonctions logiques : des LUT, des bascules, et des multiplexeurs. Une LUT est une table à n variables où sont stockées les 2n solutions possibles d’une équation logique à n entrées.
Préemption de programmes/tâches
Initialement, les processeurs généralistes étaient utilisés dans des mainframes (ordinateurs centraux), réservés à des grandes firmes. L’opérateur avait alors la possibilité de soumettre un job (programme ou ensemble de programmes) à ces machines. Le processeur était alors monopolisé par ce job durant tout le temps requis à son exécution. Ce mode opératoire a immédiatement montré des limites notamment en terme de performances. Lorsqu’un programme en cours d’exécution utilisait des données provenant d’un périphérique lent (un disque dur par exemple), des cycles processeurs étaient perdus à attendre les données provenant de ce périphérique. Afin d’exploiter pleinement la puissance de calcul d’un processeur, la multiprogrammation a été introduite. Cette technique permet de partager le temps processeur entre plusieurs programmes. Ainsi, lorsqu’un programme est en attente de données, le système peut exécuter un autre programme en attendant que les données soient prêtes.
La multiprogrammation requiert un mécanisme permettant de suspendre des programmes en cours d’exécution puis d’en reprendre l’exécution ultérieurement. Le mécanisme généralement utilisé est la préemption. La préemption consiste à sauvegarder le contexte d’exécution d’un programme, capturant ainsi l’état du programme au moment où il est préempté. Lorsque le programme est exécuté sur un processeur généraliste, ce contexte est principalement décrit par la valeur des registres ainsi que la valeur du compteur ordinal. Lorsqu’un programme est préempté, le système d’exploitation stoppe son exécution puis sauvegarde ces valeurs. Pour poursuivre l’exécution de ce programme, le contexte est alors restauré et l’exécution reprend là où elle avait été stoppée.
Ordonnancement de tâches
L’ordonnancement de tâches consiste à définir un ordre d’exécution sur l’ensemble des tâches soumises à un système. Dans nos travaux, nous considérons une application composée d’un ensemble de tâches. Le flot d’exécution de l’application correspond alors à l’ordre d’exécution des tâches constituant l’application considérée. L’action d’ordonnancement est réalisé par un composant nommé ordonnanceur.
L’ordonnanceur est l’un des composants principaux d’un système d’exploitation . Dans ce contexte, l’ordonnanceur choisit quel processus doit être exécuté à un instant donné. Afin de rester le plus généraliste possible, nous n’utilisons pas le vocabulaire spécifique aux systèmes d’exploitation. Ainsi, dans la suite de ce document, nous parlerons d’applications et de tâches. En fonction des applications à ordonnancer et des architectures sous-jacentes, de nombreux types d’ordonnancements ont été proposés. En fonction de la nature de l’application à exécuter, l’ordonnancement peut être effectué avant son exécution (hors-ligne) ou pendant (en-ligne). Le matériel sur lequel est exécuté l’application peut également avoir une incidence sur les mécanismes utilisés par l’ordonnanceur. Ainsi, certaines architecture permettent de réaliser efficacement la préemption ou non.
Placement de tâches sur architectures reconfigurables
Présentation de l’ordonnancement spatial : L’ordonnancement spatial, ou placement, consiste à placer une tâche sur la zone reconfigurable. L’opération de placement d’une tâche est constituée de deux étapes. La première consiste à trouver un emplacement, la seconde consiste à placer physiquement la tâche à cet emplacement. Dans la suite, nous nous focalisons donc sur la première étape qui concerne directement les algorithmes de placement. La zone reconfigurable est une surface rectangulaire. Dans nos travaux, nous considérons que les tâches sont également rectangulaires. nous avions présenté un ensemble de variables (DFPT, DDPT, etc.) caractérisant une tâche temps réel. Afin de décrire la dimension spatiale d’une tâche, il est nécessaire d’ajouter à cet ensemble un couple de coordonnées, noté (x, y), une largeur, notée li , et une hauteur, notée hi.
Le placement d’une tâche consiste à déterminer les coordonnées (x, y) d’une zone libre de largeur li et de hauteur hi . Le placement consiste donc à agencer des rectangles dans un conteneur rectangulaire. Lorsque le but est de maximiser le nombre de tâches à placer, ce problème est connu sous le nom de bin-packing 2D et est NP-complet .
Il paraît donc ambitieux de tenter une résolution optimale de ce problème, d’autant plus que la résolution a lieu pendant l’exécution des tâches. Le surcoût d’exécution de l’ordonnanceur devant être négligeable face aux charges induites par l’exécution des tâches, des heuristiques sont utilisées afin de minimiser le surcoût de l’algorithme de placement. Un objectif généralement visé est de maximiser le nombre de tâches placées, mais d’autres objectifs peuvent être envisagés tels que minimiser la distance entre des tâches communicantes.
Des travaux visent à supporter des tâches ayant une forme de polygone n’ayant que des angles droits. Cependant, afin de simplifier les algorithmes de placement ainsi que le placement physique d’une tâche, la majorité des travaux relatifs à l’ordonnancement spatial considère des tâches ayant une forme rectangulaire. Ainsi, nous ne considérons que des tâches rectangulaires.
Notons enfin que dans nos travaux, nous ne considérons que des tâches matérielles. Il existe cependant des recherches portant sur l’ordonnancement (et donc le placement) de tâches logicielles et matérielles.
Table des matières
Introduction
1 Ordonnancement spatio-temporel pour architectures reconfigurables
1.1 Architectures reconfigurables
1.1.1 Architectures configurables
1.1.2 Architectures reconfigurables
1.1.3 Architectures reconfigurables dynamiquement
1.1.3.1 Reconfiguration par colonne
1.1.3.2 Reconfiguration par région
1.1.4 Architectures reconfigurables hétérogènes
1.2 Hypothèses matérielles et logicielles de nos travaux
1.2.1 Préemption de programmes/tâches
1.2.1.1 Définition
1.2.1.2 La préemption sur une architecture reconfigurable
1.2.2 Relocation
1.3 Ordonnancement de tâches
1.3.1 Définition générale
1.3.1.1 Hors-ligne versus en-ligne
1.3.1.2 Préemptif versus non-préemptif
1.3.2 Ordonnancement temps réel
1.3.2.1 Tâche temps réel
1.3.2.2 Implémentation des systèmes temps réel
1.3.2.3 Ordonnancement temps réel multiprocesseur
1.3.3 Ordonnancement pour architectures reconfigurables
1.4 Placement de tâches sur architectures reconfigurables
1.4.1 Présentation de l’ordonnancement spatial
1.4.2 Travaux relatifs à l’ordonnancement spatial
1.4.2.1 Placement par colonne
1.4.2.2 Approches utilisant la notion de rectangle vide maximum
1.4.2.3 Réduction de la fragmentation
1.4.2.4 Placement hétérogène
1.5 Synthèse
2 Réseau de neurones de Hopfield
2.1 Réseau de neurones artificiels
2.1.1 Neurone biologique
2.1.2 Neurone formel
2.1.3 Perceptron, réseau multicouche et autres
2.2 Réseau de Hopfield : généralités
2.2.1 Présentation
2.2.2 Fonctionnement
2.3 Convergence des réseaux de Hopfield
2.3.1 Modes d’évaluation d’un réseau de Hopfield
2.3.1.1 Mode séquentiel
2.3.1.2 Mode synchrone
2.3.1.3 Mode parallèle
2.3.2 Fonction d’énergie
2.4 Réseau de Hopfield pour l’optimisation
2.4.1 Définition d’un codage du problème
2.4.2 Construction d’un réseau de Hopfield associé à un problème d’optimisation
2.4.3 Utilisation d’un réseau associé à un problème d’optimisation
2.5 Règles génériques de construction d’un réseau
2.5.1 Règle k-de-n
2.5.2 Règle au-plus-k-de-n
2.5.3 Règle 0-ou-1-de-n
2.5.4 Règle de k-consécutivité
2.6 Propriété d’additivité des réseaux de Hopfield
2.7 Conclusion
3 Ordonnancement temporel par réseaux de neurones de Hopfield
3.1 Modélisation neuronale d’un problème d’ordonnancement
3.1.1 Architecture homogène
3.1.2 Architecture hétérogène
3.2 Simplification du réseau : neurones inhibiteurs
3.2.1 Définition d’un neurone inhibiteur
3.2.2 Application à l’ordonnancement
3.2.3 Convergence d’un réseau pourvu de neurones inhibiteurs
3.2.4 Réduction du nombre de neurones cachés
3.2.4.1 Réduction par les neurones inhibiteurs
3.2.4.2 Suppression des tâches fictives
3.3 Résultats
3.3.1 Comparaison avec des approches neuronales classiques
3.3.2 Comparaison avec l’algorithme Pfair
3.3.2.1 Résultats préliminaires
3.3.2.2 Comparaison avec des jeux de tâches aléatoirement générés
3.3.3 Résultats sur une architecture hétérogène
3.3.4 Résultats dans le contexte des reconfigurables
3.3.5 Complexité
3.4 Conclusion
4 Placement de tâches pour architectures reconfigurables hétérogènes
4.1 Placement d’un ensemble de tâches par un réseau de Hopfield
4.1.1 Modélisation d’une architecture reconfigurable hétérogène
4.1.2 Modélisation d’une application
4.1.3 Modélisation du problème
4.1.3.1 Contrôle du nombre d’instances activées
4.1.3.2 Eviter le chevauchement d’instances de tâches
4.1.3.3 Augmenter le nombre d’instances placées
4.1.3.4 Fusion des différentes fonctions
4.1.4 Modification de la dynamique du réseau
4.1.4.1 Choix d’une fonctions
4.1.4.2 Seuillage dynamique et nombre d’instances activées
4.1.4.3 Implémentation du seuillage dynamique
4.1.5 Résultats
4.1.5.1 Simulations du placement d’un ensemble de tâches
4.1.5.2 Simulations sur plusieurs jeux de tâches ayant des caractéristiques identiques
4.1.5.3 Comparaisons avec l’algorithme SUP Fit
4.1.5.4 Comparaison en temps d’exécution
4.1.6 Utilisation du réseau de neurones dans un contexte réel
4.1.6.1 Placement d’un sous ensemble de tâches
4.1.6.2 Gestion de l’état de la zone reconfigurable
4.1.7 Conclusion
4.2 Placement en colonne
4.2.1 Organisation des ressources d’une architecture reconfigurable hétérogène
4.2.2 Modélisation d’une tâche
4.2.3 Algorithme de placement
4.2.3.1 Placement d’une tâche
4.2.3.2 Suppression d’une tâche
4.2.4 Expérimentations
4.2.4.1 Scénario d’exécution
4.2.4.2 Comparaison du nombre de tâches rejetées
4.2.4.3 Comparaison du nombre d’instances réelles
4.2.5 Conclusion
5 Optimisation et tolérance aux fautes des réseaux de neurones de Hopfield
5.1 Evaluation parallèle d’un réseau de neurones de Hopfield
5.1.1 Mode d’évaluation parallèle
5.1.1.1 Sur un exemple simple
5.1.1.2 Généralisation
5.1.2 Convergence dans le cas parallèle
5.1.2.1 Signe du produit A1 × A2 de l’équation (5.17)
5.1.2.2 Signe du produit BT
1 × W11 × B1 de l’équation (5.17)
5.1.3 Construction des paquets
5.1.3.1 Application à un problème d’ordonnancement
5.1.3.2 Construction des paquets : généralisation
5.1.4 Expérimentation
5.1.5 Conclusion
5.1.6 Perspectives
5.2 Tolérance aux fautes
5.2.1 Modèle de fautes au sein d’un réseau de neurones de Hopfield
5.2.2 Maintien de la convergence d’un réseau de Hopfield malgré les défaillances
5.2.3 Résultats
5.2.3.1 Nombre de fautes tolérées
5.2.3.2 Impact du nombre de fautes sur le temps de convergence 1
5.2.4 Conclusion
Conclusion
