Aspects géométriques et intégrables des modèles de matrices aléatoires

Travail réalisé en cotutelle avec l'université Paris-Diderot et le Commissariat à l'Energie Atomique sous la direction de John Harnad et Bertrand Eynard.

Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future.

Scheduled service network design for integrated planning of rail freight transportation

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles.

Implantation des futures sur un système distribué par passage de messages

Ce mémoire présente une implantation de la création paresseuse de tâches desti- née à des systèmes multiprocesseurs à mémoire distribuée. Elle offre un sous-ensemble des fonctionnalités du Message-Passing Interface et permet de paralléliser certains problèmes qui se partitionnent difficilement de manière statique grâce à un système de partitionnement dynamique et de balancement de charge. Pour ce faire, il se base sur le langage Multilisp, un dialecte de Scheme orienté vers le traitement parallèle, et implante sur ce dernier une interface semblable à MPI permettant le calcul distribué multipro- cessus. Ce système offre un langage beaucoup plus riche et expressif que le C et réduit considérablement le travail nécessaire au programmeur pour pouvoir développer des programmes équivalents à ceux en MPI. Enfin, le partitionnement dynamique permet de concevoir des programmes qui seraient très complexes à réaliser sur MPI. Des tests ont été effectués sur un système local à 16 processeurs et une grappe à 16 processeurs et il offre de bonnes accélérations en comparaison à des programmes séquentiels équiva- lents ainsi que des performances acceptables par rapport à MPI. Ce mémoire démontre que l’usage des futures comme technique de partitionnement dynamique est faisable sur des multiprocesseurs à mémoire distribuée.

Dépistage prénatal de la trisomie 21 et autres aneuploïdies au premier trimestre

La présente thèse par articles aborde différentes facettes du dépistage prénatal de certaines aneuploïdies au premier trimestre de la grossesse. L’introduction retrace l’historique du dépistage prénatal et énonce les différents marqueurs biochimiques et échographiques associés aux aneuploïdies. La première publication démontre que le tabagisme maternel abaisse significativement les niveaux sanguins maternels de PAPP-A et de la fraction libre de la β-hCG et augmente significativement la clarté nucale, confirmant la nécessité de contrôler cette co-variable dans le calcul de risque final, du moins pour la trisomie 18. Le deuxième article identifie des seuils de clarté nucale au-delà desquels la biochimie génétique n’apporte aucune valeur additionnelle au dépistage prénatal de la trisomie 21 et de la trisomie 18. Pour les fœtus avec clarté nucale supérieure aux seuils établis, un diagnostic prénatal intrusif devrait être offert sans délai. Le troisième et dernier article porte sur la première détermination des niveaux plasmatiques maternels de la protéine FLRG (follistatin-related gene) au premier trimestre de grossesse et sur son rôle potentiel à titre de marqueur biochimique dans le dépistage prénatal de la trisomie 21. Bien que détectables, les niveaux plasmatiques maternels de FLRG ne sont pas significativement altérés en présence de fœtus avec syndrome de Down. Dans la discussion générale, les trois articles sont abordés sous un angle plus spécifique au Québec. Des données complémentaires et originales y sont présentées. Une discussion sur l’évolution future du dépistage prénatal est entamée et des axes de recherche sont proposés.

Variation des biomarqueurs dans le spectre visible non résolu de la Terre

L’évolution rapide des technologies de détection et de caractérisation des exoplanètes depuis le début des années 1990 permet de croire que de nouveaux instruments du type Terrestrial Planet Finder (TPF) pourront prendre les premiers spectres d’exoplanètes semblables à la Terre d’ici une ou deux décennies. Dans ce contexte, l’étude du spectre de la seule planète habitée connue, la Terre, est essentielle pour concevoir ces instruments et analyser leurs résultats. Cette recherche présente les spectres de la Terre dans le visible (390-900 nm), acquis lors de 8 nuits d’observation étalées sur plus d’un an. Ces spectres ont été obtenus en observant la lumière cendrée de la Lune avec le télescope de 1.6 m de l’Observatoire du Mont-Mégantic (OMM). La surface de la Lune réfléchissant de manière diffuse la lumière provenant d’une portion de la Terre, ces spectres sont non résolus spatialement. L’évolution de ces spectres en fonction de la lumière réfléchie à différentes phases de Terre est analogue à celle du spectre d’une exoplanète, dont la phase change selon sa position autour de l’étoile. L'eau, l'oxygène et l'ozone de l’atmosphère, détectés dans tous nos spectres, sont des biomarqueurs dont la présence suggère l’habitabilité de la planète et/ou la présence d’une activité biologique. Le Vegetation Red Edge (VRE), une autre biosignature spectrale, dû aux organismes photosynthétiques à la surface, est caractérisé par l’augmentation de la réflectivité autour de 700 nm. Pour les spectres de 5 nuits, cette augmentation a été évaluée entre -5 et 15% ±~5%, après que les contributions de la diffusion de Rayleigh, des aérosols et d’une large bande moléculaire de l’ozone aient été enlevées. Les valeurs mesurées sont cohérentes avec la présence de végétation dans la phase de la Terre contribuant au spectre, mais s’étendent sur une plage de variations plus large que celles trouvées dans la littérature (0-10%). Cela pourrait s’expliquer par des choix faits lors de la réduction des données et du calcul du VRE, ou encore par la présence d’autres éléments de surface ou de l’atmosphère dont la contribution spectrale autour de 700 nm serait variable.

Étude structurale conformationnelle des toxines de l’anthrax par cryo-microscopie et dynamique moléculaire

Les toxines de l’anthrax font partie de la famille des toxines A-B dans laquelle la moitié B se fixe à la membrane de la cellule permettant par la suite la translocation de la moitié A. Dans le cas de l’anthrax, la moitié B est représentée par le Protective Antigen (PA) et la moitié A par les deux protéines Edema Factor (EF) et Lethal Factor (LF). Après le recrutement par les récepteurs cellulaires (CMG2 et TEM8), PA s’organise en heptamère. Il peut fixer jusqu'à 3 ligands (EF et LF) avant d'être endocyté. Les modèles actuels de PA suggèrent que la baisse de pH à l’intérieur des endosomes permet un changement de conformation de la forme pré-pore vers la forme pore et que les ligands EF et LF passeraient au travers le pore pour entrer dans le cytoplasme. Cependant, le diamètre du pore est environ dix fois inférieur à celui des ligands (10 Å contre 100 Å). Un processus de folding/unfolding a été proposé mais demeure controversé. Afin d'identifier le processus de passage des facteurs EF et LF dans le cytoplasme, nous avons déterminé par cryo-microscopie électronique combinée avec l’analyse d’image les structures tridimensionnelles des complexes formés par PA et LF aux étapes prépore et pore. Par la suite, une étude complémentaire par dynamique moléculaire nous a permis de modéliser à haute résolution les différentes interactions qui ont lieu au sein du complexe. La structure 3D du complexe prépore combiné à 3 LF a été déterminée à une résolution de 14 Å. Nous avons aussi calculé une structure préliminaire du complexe pore également combiné à 3 LF Celles-ci n’ont jamais été résolues auparavant et leur connaissance permet d’envisager l’étude en profondeur du mécanisme infectieux de l’Anthrax in vivo.

Impacts potentiels d’un changement climatique sur le pergélisol dans le nord canadien

Les fichiers video (d'animation) sont dans un format Windows Media (.wmv)

Analyse spectroscopique d'étoiles naines blanches riches en hydrogène(DA) : vers des modèles d'atmosphère améliorés sans paramètres libres

Le but de cette thèse est de raffiner et de mieux comprendre l'utilisation de la méthode spectroscopique, qui compare des spectres visibles de naines blanches à atmosphère riche en hydrogène (DA) à des spectres synthétiques pour en déterminer les paramètres atmosphériques (température effective et gravité de surface). Notre approche repose principalement sur le développement de modèles de spectres améliorés, qui proviennent eux-mêmes de modèles d'atmosphère de naines blanches de type DA. Nous présentons une nouvelle grille de spectres synthétiques de DA avec la première implémentation cohérente de la théorie du gaz non-idéal de Hummer & Mihalas et de la théorie unifiée de l'élargissement Stark de Vidal, Cooper & Smith. Cela permet un traitement adéquat du chevauchement des raies de la série de Balmer, sans la nécessité d'un paramètre libre. Nous montrons que ces spectres améliorés prédisent des gravités de surface qui sont plus stables en fonction de la température effective. Nous étudions ensuite le problème de longue date des gravités élevées pour les DA froides. L'hypothèse de Bergeron et al., selon laquelle les atmosphères sont contaminées par de l'hélium, est confrontée aux observations. À l'aide de spectres haute résolution récoltés au télescope Keck à Hawaii, nous trouvons des limites supérieures sur la quantité d'hélium dans les atmosphères de près de 10 fois moindres que celles requises par le scénario de Bergeron et al. La grille de spectres conçue dans ces travaux est ensuite appliquée à une nouvelle analyse spectroscopique de l'échantillon de DA du SDSS. Notre approche minutieuse permet de définir un échantillon plus propre et d'identifier un nombre important de naines blanches binaires. Nous déterminons qu'une coupure à un rapport signal-sur-bruit S/N > 15 optimise la grandeur et la qualité de l'échantillon pour calculer la masse moyenne, pour laquelle nous trouvons une valeur de 0.613 masse solaire. Finalement, huit nouveaux modèles 3D de naines blanches utilisant un traitement d'hydrodynamique radiative de la convection sont présentés. Nous avons également calculé des modèles avec la même physique, mais avec une traitement standard 1D de la convection avec la théorie de la longueur de mélange. Un analyse différentielle entre ces deux séries de modèles montre que les modèles 3D prédisent des gravités considérablement plus basses. Nous concluons que le problème des gravités élevées dans les naines blanches DA froides est fort probablement causé par une faiblesse dans la théorie de la longueur de mélange.

Modélisation de l'irradiance solaire spectrale dans le proche et moyen ultraviolet

Nous présentons un modèle pour l’irradiance solaire spectrale entre 200 et 400 nm. Celui-ci est une extension d’un modèle d’irradiance solaire totale basé sur la simulation de la fragmentation et l’érosion des taches qui utilise, en entrée, les positions et aires des taches observées pour chaque pas de temps d’une journée. L’émergence des taches sur la face du Soleil opposée à la Terre est simulée par une injection stochastique. Le modèle simule ensuite leur désintégration, qui produit des taches plus petites et des facules. Par la suite, l’irradiance est calculée en sommant la contribution des taches, des facules et du Soleil inactif. Les paramètres libres du modèle sont ajustés en comparant les séquences temporelles produites avec les données provenant de divers satellites s’étalant sur trois cycles d’activité. Le modèle d’irradiance spectrale, quant à lui, a été obtenu en modifiant le calcul de la contribution des taches et des facules, ainsi que celle du Soleil inactif, afin de tenir compte de leur dépendance spectrale. Le flux de la photosphère inactive est interpolé sur un spectre synthétique non magnétisé, alors que le contraste des taches est obtenu en calculant le rapport du flux provenant d’un spectre synthétique représentatif des taches et de celui provenant du spectre représentatif du Soleil inactif. Le contraste des facules est quand à lui calculé avec une procédure simple d’inversion de corps noir. Cette dernière nécessite l’utilisation d’un profil de température des facules obtenu à l’aide de modèles d’atmosphère. Les données produites avec le modèle d’irradiance spectrale sont comparées aux observations de SOLSTICE sur UARS. L’accord étant peu satisfaisant, particulièrement concernant le niveau d’irradiance minimal ainsi que l’amplitude des variations, des corrections sont appliquées sur le flux du Soleil inactif, sur le profil de température des facules, ainsi qu’à la dépendance centre-bord du contraste des facules. Enfin, un profil de température des facules est reconstruit empiriquement en maximisant l’accord avec les observations grâce à un algorithme génétique. Il est utilisé afin de reconstruire les séquences temporelles d’irradiance jusqu’en 1874 à des longueurs d’ondes d’intérêt pour la chimie et la dynamique stratosphérique.

Étude des collisions proton-proton dans l’expérience ATLAS avec les détecteurs ATLAS-MPX

Les seize détecteurs MPX constituant le réseau ATLAS-MPX ont été placés à différentes positions dans le détecteur ATLAS et sa averne au CERN dans le but de mesurer en emps réel les champs de radiation produits ar des particules primaires (protons des faisceaux) et des particules secondaires (kaons, pions, g, protons) issues des collisions proton-proton. Des films de polyéthylène (PE) et de fluorure de lithium (6LiF) recouvrent les détecteurs afin d’augmenter leur sensibilité aux neutrons produits par les particules primaires et secondaires interagissant avec les matériaux présents dans l’environnement d’ATLAS. La reconnaissance des traces laissées par les particules dans un détecteur ATLAS-MPX se fait à partir des algorithmes du logiciel MAFalda (“Medipix Analysis Framework”) basé sur les librairies et le logiciel d’analyse de données ROOT. Une étude sur le taux d’identifications erronées et le chevauchement d’amas a été faite en reconstruisant les activités des sources 106Ru et 137Cs. L’efficacité de détection des neutrons rapides a été mesurée à l’aide des sources 252Cf et 241AmBe (neutrons d’énergie moyenne de 2.13 et 4.08 MeV respectivement). La moyenne des efficacités de détection mesurées pour les neutrons produits par les sources 252C f et 241AmBe a été calculée pour les convertisseurs 6LiF et PE et donnent (0.8580 ± 0.1490)% et (0.0254 ± 0.0031)% pour LiF et (0.0510 ± 0.0061)% et (0.0591 ± 0.0063)% pour PE à bas et à haut seuil d’énergie respectivement. Une simulation du calcul de l’efficacité de détection des neutrons dans le détecteur MPX a été réalisée avec le logiciel GEANT4. Des données MPX correspondant aux collisions proton-proton à 2.4 TeV et à 7 TeV dans le centre de masse ont été analysées. Les flux détectés d’électrons et de photons sont particulièrement élevés dans les détecteurs MPX01 et MPX14 car ils sont plus près du point de collision. Des flux de neutrons ont été estimés en utilisant les efficacités de détection mesurées. Une corrélation avec la luminosité du LHC a été établie et on prédit que pour les collisions à 14 TeV dans le centre de masse et avec une luminosité de 10^34 cm-1*s-1 il y aura environ 5.1x10^8 ± 1.5x10^7 et 1.6x10^9 ± 6.3x10^7 particules détectées par les détecteurs MPX01 et MPX14 respectivement.

Le rendu en demi-ton avec sensibilité à la structure

Dans ce mémoire nous allons présenter une méthode de diffusion d’erreur originale qui peut reconstruire des images en demi-ton qui plaisent à l’œil. Cette méthode préserve des détails fins et des structures visuellement identifiables présentes dans l’image originale. Nous allons tout d’abord présenter et analyser quelques travaux précédents afin de montrer certains problèmes principaux du rendu en demi-ton, et nous allons expliquer pourquoi nous avons décidé d’utiliser un algorithme de diffusion d’erreur pour résoudre ces problèmes. Puis nous allons présenter la méthode proposée qui est conceptuellement simple et efficace. L’image originale est analysée, et son contenu fréquentiel est détecté. Les composantes principales du contenu fréquentiel (la fréquence, l’orientation et le contraste) sont utilisées comme des indices dans un tableau de recherche afin de modifier la méthode de diffusion d’erreur standard. Le tableau de recherche est établi dans un étape de pré-calcul et la modification est composée par la modulation de seuil et la variation des coefficients de diffusion. Ensuite le système en entier est calibré de façon à ce que ces images reconstruites soient visuellement proches d’images originales (des aplats d’intensité constante, des aplats contenant des ondes sinusoïdales avec des fréquences, des orientations et des constrastes différents). Finalement nous allons comparer et analyser des résultats obtenus par la méthode proposée et des travaux précédents, et démontrer que la méthode proposée est capable de reconstruire des images en demi-ton de haute qualité (qui préservent des structures) avec un traitement de temps très faible.

Représentation et détection des images et des surfaces déformables

La représentation d'une surface, son lissage et son utilisation pour l'identification, la comparaison, la classification, et l'étude des variations de volume, de courbure ou de topologie sont omniprésentes dans l'aire de la numérisation. Parmi les méthodes mathématiques, nous avons retenu les transformations difféomorphiques d'un pattern de référence. Il y a un grand intérêt théorique et numérique à approcher un difféomorphisme arbitraire par des difféomorphismes engendrés par des champs de vitesses. Sur le plan théorique la question est : "est-ce que le sous-groupe de difféomorphismes engendrés par des champs de vitesses est dense dans le groupe plus large de Micheletti pour la métrique de Courant ?" Malgré quelques progrès réalisés ici, cette question demeure ouverte. Les pistes empruntées ont alors convergé vers le sous-groupe de Azencott et de Trouvé et sa métrique dans le cadre de l'imagerie. Elle correspond à une notion de géodésique entre deux difféomorphismes dans leur sous-groupe. L'optimisation est utilisée pour obtenir un système d'équations état adjoint caractérisant la solution optimale du problème d'identification à partir des observations. Cette approche est adaptée à l'identification de surfaces obtenues par un numériseur tel que, par exemple, le scan d'un visage. Ce problème est beaucoup plus difficile que celui d'imagerie. On doit alors introduire un système de référence courbe et une surface à facettes pour les calculs. On donne la formulation du problème d'identification et du calcul du changement de volume par rapport à un scan de référence.

Étude de la coalescence de nanogouttelettes par dynamique moléculaire

Ce travail est consacré à l’étude de la coalescence de gouttelettes liquides à l’échelle du nanomètre. Nous nous sommes intéressés principalement à l’évolution du changement topologique des gouttelettes à partir de la rupture des surfaces au moment du contact initial jusqu’à la coalescence complète. Nous utilisons la dynamique moléculaire afin de simuler plusieurs types de gouttelettes soit en utilisant le potentiel empirique de type Stillinger-Weber pour des gouttelettes de silicium (l-Si) en 3 dimensions et le modèle Embedded Atom Method pour des gouttelettes de cuivre liquide (l-Cu) en 2d, quasi-2d (disques) et 3 dimensions. Qualitativement, toutes les simulations démontrent une coalescence similaire indépendamment de la dimension de calcul (2d à 3d), de la taille et de la température initiale des gouttelettes. La coalescence évolue par une déformation rapide des surfaces sans mixage important entre les atomes des deux gouttelettes initiales. De plus, nous étudions l’évolution du col de coalescence formé lors du contact initial entre les gouttelettes et, pour les systèmes en 3d, nous observons une transition claire d’un régime visqueux vers un régime inertiel du rayon de ce col, tel que suggéré par des modèles théoriques. Pour les gouttelettes de cuivre nous observons exactement le comportement des prédictions analytiques et confirmons que le premier régime suit un comportement visqueux sans aplatissement local des gouttelettes. La situation est différente pour les gouttelettes de l-Si où nous observons un effet plus grand, par rapport aux prédictions analytiques, du rayon et de la température initiale des gouttelettes sur l’évolution du col de coalescence. Nous suggérons que les paramètres décrivant l’évolution de la coalescence dépendent des propriétés des matériaux utilisés contrairement à la théorie universelle couramment utilisée.

Approche efficace pour la conception des architectures multiprocesseurs sur puce électronique

Les systèmes multiprocesseurs sur puce électronique (On-Chip Multiprocessor [OCM]) sont considérés comme les meilleures structures pour occuper l'espace disponible sur les circuits intégrés actuels. Dans nos travaux, nous nous intéressons à un modèle architectural, appelé architecture isométrique de systèmes multiprocesseurs sur puce, qui permet d'évaluer, de prédire et d'optimiser les systèmes OCM en misant sur une organisation efficace des nœuds (processeurs et mémoires), et à des méthodologies qui permettent d'utiliser efficacement ces architectures. Dans la première partie de la thèse, nous nous intéressons à la topologie du modèle et nous proposons une architecture qui permet d'utiliser efficacement et massivement les mémoires sur la puce. Les processeurs et les mémoires sont organisés selon une approche isométrique qui consiste à rapprocher les données des processus plutôt que d'optimiser les transferts entre les processeurs et les mémoires disposés de manière conventionnelle. L'architecture est un modèle maillé en trois dimensions. La disposition des unités sur ce modèle est inspirée de la structure cristalline du chlorure de sodium (NaCl), où chaque processeur peut accéder à six mémoires à la fois et où chaque mémoire peut communiquer avec autant de processeurs à la fois. Dans la deuxième partie de notre travail, nous nous intéressons à une méthodologie de décomposition où le nombre de nœuds du modèle est idéal et peut être déterminé à partir d'une spécification matricielle de l'application qui est traitée par le modèle proposé. Sachant que la performance d'un modèle dépend de la quantité de flot de données échangées entre ses unités, en l'occurrence leur nombre, et notre but étant de garantir une bonne performance de calcul en fonction de l'application traitée, nous proposons de trouver le nombre idéal de processeurs et de mémoires du système à construire. Aussi, considérons-nous la décomposition de la spécification du modèle à construire ou de l'application à traiter en fonction de l'équilibre de charge des unités. Nous proposons ainsi une approche de décomposition sur trois points : la transformation de la spécification ou de l'application en une matrice d'incidence dont les éléments sont les flots de données entre les processus et les données, une nouvelle méthodologie basée sur le problème de la formation des cellules (Cell Formation Problem [CFP]), et un équilibre de charge de processus dans les processeurs et de données dans les mémoires. Dans la troisième partie, toujours dans le souci de concevoir un système efficace et performant, nous nous intéressons à l'affectation des processeurs et des mémoires par une méthodologie en deux étapes. Dans un premier temps, nous affectons des unités aux nœuds du système, considéré ici comme un graphe non orienté, et dans un deuxième temps, nous affectons des valeurs aux arcs de ce graphe. Pour l'affectation, nous proposons une modélisation des applications décomposées en utilisant une approche matricielle et l'utilisation du problème d'affectation quadratique (Quadratic Assignment Problem [QAP]). Pour l'affectation de valeurs aux arcs, nous proposons une approche de perturbation graduelle, afin de chercher la meilleure combinaison du coût de l'affectation, ceci en respectant certains paramètres comme la température, la dissipation de chaleur, la consommation d'énergie et la surface occupée par la puce. Le but ultime de ce travail est de proposer aux architectes de systèmes multiprocesseurs sur puce une méthodologie non traditionnelle et un outil systématique et efficace d'aide à la conception dès la phase de la spécification fonctionnelle du système.