Cette thèse a été menée en collaboration avec la der-edf. Il s'agit d'étudier ici la parallélisation d'un probleme de répartition de charges dans les réseaux électriques. Ce probleme correspond mathématiquement a la resolution successive de systèmes linéaires dont les matrices sont proches les unes des autres. Une methode originale de resolution est tout d'abord présentée dans un cadre séquentiel, puis une parallélisation sur plusieurs types d'architectures (mimd vectoriel, simd massivement parallèle et mimd a topologie reconfigurable) est proposée. Les machines cibles ont ete étudiées en profondeur et modélisées théoriquement. Plusieurs idées de parallélisation ont été envisagées. Il est intéressant de constater que les meilleures méthodes de resolution de ce probleme concret modèle (c'est-a-dire les plus rapides) sont différentes suivant le type de machine parallèle considéré

.

La tendance des constructeurs pour le calcul scientifique est à l'imbrication de technologies permettant un degré de parallélisme toujours plus fort au sein d'une même machine : architecture NUMA, puces multicœurs, SMT. L'efficacité de l'exécution d'une application parallèle irrégulière sur de telles machines hiérarchiques repose alors sur la qualité de l'ordonnancement des tâches et du placement des données, pour éviter le plus possible les pénalités NUMA et les défauts de cache. Les systèmes d'exploitation actuels, pris au dépourvu car trop généralistes, laissent les concepteurs d'application contraints à « câbler » leurs programmes pour une machine donnée.<br /><br />Dans cette thèse, pour garantir une certaine portabilité des performances, nous définissons la notion de /bulle/ permettant d'exprimer la nature structurée du parallélisme du calcul, et nous modélisons l'architecture de la machine cible par une hiérarchie de listes de tâches. Une interface de programmation et des outils de débogage de haut niveau permettent alors de développer simplement des ordonnanceurs dédiés, efficaces et portables. Différents ordonnanceurs mettant en œuvre des approches variées ont été développés, en partie notamment par des stagiaires encadrés au sein de l'équipe, ce qui montre à la fois la puissance et la simplicité de l'interface. C'est ainsi une véritable plate-forme de développement et d'expérimentation d'ordonnanceurs à bulles qui a été intégrée au sein de la bibliothèque de threads utilisateur marcel. Le support OpenMP du compilateur GCC, GOMP, a été étendu pour utiliser cette bibliothèque et exprimer la nature structurée des sections parallèles imbriquées à l'aide de bulles. Avec la couche de compatibilité POSIX de marcel, ces supports ont permis de tester les différents ordonnanceurs à bulles développés, sur différentes applications. Les gains obtenus, de l'ordre de 20 à 40%, montrent l'intérêt de notre approche.

Après un état de l'art sur l'ordonnancement en général et l'ordonnancement temps réel en particulier permetttant de préciser les notions utilisées par la suite et après avoir motivé l'intérêt d'une nouvelle contrainte temps réel de latence, nous proposons un modèle qui formalise les systèmes temps réel avec contraintes de précédences, de périodicités et de latences. Dans ce modèle, les précédences sont définies par un graphe orienté acyclique infiniment répété. Pour le cas monoprocesseur, on étudie trois problèmes d'ordonnancement : celui des systèmes avec contraintes de précédences et de périodicités, celui des systèmes avec contraintes de précédences et de latences et enfin celui des systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème on étudie la cohérence entre les différentes contraintes, on donne des conditions d'ordonnançabilité et on propose un algorithme prouvé optimal dans le sens où s'il y a un ordonnancement, l'algorithme le trouvera. On passe ensuite au cas multiprocesseur où l'architecture est définie par un graphe non-orienté. On étudie trois problèmes d'implantation (distribution et ordonnancement) dans les mêmes cas qu'en monoprocesseur en tenant compte des temps de communications. On prouve que ces trois problèmes sont NP-difficiles et on propose, donc, des heuristiques. Les performances de chaque heuristique sont comparées à celles d'algorithme exacte de type "branch and bound", en utilisant des simulations numériques.

Les besoins continus en puissance de calcul restent un moteur important dans l'évolution des technologies des ordinateurs. Dans le domaine scientifique, par exemple, on trouve facilement des applications capables d'épuiser la puissance de calcul même sur des machines parmi les plus récentes. Dans le cas specifique des machines parallèles, nous nous intéressons au problème de performances des machines multiprocesseurs à mémoire partagée. Le rapport entre les capacités de la hiérarchie mémoire et la vitesse des processeurs est à l'origine d'un des problèmes de performances fondamentaux. On parle de contention ou de goulot d'étranglement mémoire afin de signifier que la saturation de l'accès à la partie haute de la hiérarchie mémoire est responsable d'une baisse de performances. La technologie de la fabrication des processeurs évolue en effet généralement plus rapidement que celle de la mémoire centrale. L'interconnexion entre la mémoire centrale et les processeurs est un des points cruciaux dans l'architecture des multiprocesseurs, en effet ce point est fréquent. Dans ce contexte, nous proposons l'utilisation des compteurs matériels en tant qu'élément d'un système de contrôle permettant de modifier l'ordonnancement de l'exécution des processus en présence d'une contention. La politique de contrôle retenue consiste à maximiser le rendement de la machine. Le contrôle d'exécution des processus est basé sur l'estimation des performances via l'observation de l'utilisation mémoire. Ce mécanisme d'estimation est l'issue d'une étude sur l'impact des capacités des hiérarchies mémoires sur les performances des multiprocesseurs.

Les systèmes temps réel à contraintes temporelles strictes sont caractérisés par des ensembles de tâches pour lesquelles sont connus l'échéance, le modèle d'arrivée (fréquence) et la durée d'exécution pire cas (WCET). Nous nous intéressons à l'ordonnancement de ces systèmes sur plate-forme multiprocesseur. Garantir le respect des échéances pour un algorithme d'ordonnancement est l'une des problématiques majeures de cette thématique. Nous allons plus loin en nous intéressant à la sûreté temporelle, que nous caractérisons par les propriétés (i) de robustesse et (ii) de viabilité. La robustesse consiste à proposer un intervalle sur les augmentations(i-a) de WCET et (i-b) de fréquence tel que les échéances soient respectées. La viabilité consiste cette fois à garantir le respect des échéances lors du relâchement des contraintes (ii-a) de WCET (réduction), (ii-b) de fréquence (réduction) et (ii-c) d'échéance(augmentation). La robustesse revient alors à tolérer l'imprévu, tandis que la viabilité est la garantie que l'algorithme d'ordonnancement n'est pas sujet à des anomalies suite à un relâchement de contraintes. Nous considérons l'ordonnancement en priorités fixes, où chaque occurrence d'une tâche est ordonnancée avec la même priorité. Dans un premier temps, nous étudions la propriété de robustesse dans les approches d'ordonnancement hors-ligne et sans migration (partitionnement). Nous traitons le cas des tâches avec ou sans partage de ressources. Dans un second temps, nous étudions la propriété de viabilité d'une approche d'ordonnancement en ligne avec migrations restreintes et sans partage de ressources

Aujourd'hui les systèmes embarqués sont partout et requièrent de plus en plus de puissance de calcul. Mais, l'évolution des technologies a un impact négatif sur la fiabilité. En particulier, il est prévu une hausse du nombre de fautesf intermittentes dans les technologies à venir. Cependant, nous ne bénéficions pas d'étude expérimentale détaillée pour ce type de faute. Or, pour tenter de se prémunir de ces fautes, il est important de comprendre leur comportement, ainsi que leur impact sur le système et les applications. Pour cela, nous avons défini une plateforme expérimentale capable d'observer des erreurs intermittentes. Nous avons ainsi, pu confirmer que les erreurs intermittentes peuvent être observées très tôt avant la période d'usure du circuit. De plus, ces erreurs apparaissent en rafale et seul l'arrêt des processeurs semble les stopper. Nous confirmons ainsi, qu'il est nécessaire de mettre en place des méthodes de détection en ligne des erreurs intermittentes dans les circuits intégrés très submicroniques. Cependant, aucune solution proposée dans la littérature ne convient à la fois aux erreurs intermittentes et aux architectures multiprocesseur. Ainsi, nous avons développé une méthode de test périodique répondant à ces contraintes. En particulier, nous avons montré que le test ne doit pas nécessairement être prioritaire devant les applications. Cela nous a permis de conclure qu'une politique d'ordonnancement des tests pseudo-périodiques, prenant en compte les processeurs au repos et la priorité des tâches, offrent le meilleur compromis entre performance et probabilité de détection.

Les applications dans le domaine des communications numériques deviennent de plus en plus complexes et diversifiées. En témoigne l'apparition des turbo-communications qui représentent la généralisation du principe de processus itératif introduit par les turbocodes. La mise en œuvre de systèmes de turbo-communications, communément appelés turbo- récepteurs, est devenue primordiale pour atteindre les performances aujourd'hui exigées en terme de qualité de transmission. Des architectures matérielles dédiées implantant ces systèmes ont déjà vu le jour dans plusieurs équipes de recherches académiques et industrielles. Cependant, pour des exigences de flexibilité de l'implantation (pour supporter les évolutions d'une norme ou des applications multi-standards), de qualité de transmission et de haut débit de communication, des architectures multiprocesseurs adéquates deviennent incontournables. Le sujet de cette thèse porte sur la mise en œuvre d'une plate-forme architecturale multiprocesseur générique adaptée aux turbo-récepteurs et plus particulièrement aux turbo-décodeurs convolutifs. Ainsi, le sujet gravite autour de deux axes de recherche : un axe algorithmique autour des systèmes de turbo-décodage et un autre autour de la conception numérique ces derniers. Sur l'axe algorithmique, ces travaux présentent une étude approfondie des algorithmes de turbo-décodage autour des techniques de parallélisme. Les fondations de cette étude reposent sur une classification des parallélismes existants qui distingue les parallélismes selon leurs granularités et leurs pouvoirs d'accélération. L'analyse de cette classification a révélé la nécessité d'investiguer les parallélismes de sous-bloc et de décodeur composant pour améliorer l'efficacité de leur mise en œuvre. Les recherches menées mettent en évidence que le parallélisme de sous-bloc s'avère plus efficace avec la technique d'initialisation par passage de message. Nous avons également montré que le parallélisme de décodeur composant, grâce à la technique du décodage combiné ou « shuffled decoding » , améliore l'efficacité des architectures de turbo-décodeur fortement parallèles et que cette dernière peut être optimisée en contraignant la conception de l'entrelaceur du turbocode. Sur l'axe architectural, ces avancées algorithmiques ont été mises à profit dans une plate-forme multiprocesseur qui exploite au mieux les compromis matériel/logiciel (i .e. performance/flexibilité) tant au niveau du calcul qu'au niveau des communications. Au niveau du calcul, un processeur ASIP (Application-Specific Instruction-set Processor) dédié au décodage des codes convolutifs a été proposé et conçu de manière à ne fournir que la flexibilité désirée, tout en conservant des performances élevées grâce à un chemin de données fortement parallélisé. Au niveau des communications, la plate-forme a été dotée de réseaux sur puce dédiés pour assurer la bande passante nécessaire aux échanges itératifs d'information. Cette plate-forme multi-ASIP flexible a été prototypée sur une carte d'émulation intégrant des circuits FPGA. La flexibilité de la plate-forme proposée autorise le support de tous les standards de turbocodes convolutifs actuels et émergeants et peut trouver un intérêt industriel dans les domaines des télécommunications mobiles et satellitaires, de la diffusion de contenu ou de l'Internet haut-débit.

Reproduction de : Thèse de doctorat : Informatique : Université de Nice-Sophia Antipolis : 1996. / Résumés en français et en anglais. En annexe articles en anglais. L'Impr. INRIA a attribué un n° de coll, TU 386 associé à un code-barres en 4e de couv. Bibliogr. p. 79-82.

Les applications de vision par ordinateur embarquées demandent une forte capacité decalcul et poussent le développement des systèmes multi- et many-cores spécifiques à l’application. Les choix au départ de la conception du système peuvent impacter sa performance parallèle finale – parmi lesquelles la granularité de la parallélisation, le nombre de processeurs et l’équilibre entre calculs et l’acheminement des données. L’impact de ces choix est difficile à estimer dans les phases initiales de conception et il y a peu d’outils et méthodes pour aider les concepteurs dans cette tâche. Les contributions de cette thèse consistent en deux méthodes et les outils associés qui visent à faciliter la sélection des paramètres architecturaux d’un multiprocesseur embarqué et les stratégies de parallélisation des applications de vision embarquée. La première est une méthode d’exploration de l’espace de conception qui repose sur Parana, un outil fournissant une estimation rapide et précise de la performance parallèle. Parana permet l’évaluation de différents scénarios de parallélisation et peut déterminer la limite maximale de performance atteignable. La seconde contribution est une méthode pour l’optimisation du dimensionnement des tuiles d’images 2D utilisant la programmation par contraintes dans l’outil Tilana. La méthode proposée intègre pour plus de précision des facteurs non-linéaires comme les temps des transferts DMA et les surcoûts de l’ordonnancement parallèle. / Embedded computer vision applications demand high system computational power and constitute one of the key drivers for application-specific multi- and many-core systems. A number of early system design choices can impact the system’s parallel performance – among which the parallel granularity, the number of processors and the balance between computation and communication. Their impact in the final system performance is difficult to assess in early design stages and there is a lack for tools that support designers in this task. The contributions of this thesis consist in two methods and associated tools that facilitate the selection of embedded multiprocessor’s architectural parameters and computer vision application parallelization strategies. The first consists of a Design Space Exploration (DSE) methodology that relies on Parana, a fast and accurate parallel performance estimation tool. Parana enables the evaluation of what-if parallelization scenarios and can determine their maximum achievable performance limits. The second contribution consists of a method for optimal 2D image tile sizing using constraint programming within the Tilana tool. The proposed method integrates non-linear DMA data transfer times and parallel scheduling overheads for increased accuracy.