Dans une machine sans mémoire commune, les processeurs communiquent par échanges de messages via des liaisons point à point. Les machines à connectique fixe utilisent des liaisons permanentes organisées selon un graphe d'interconnexion régulier tel qu'une grille ou un hypercube. Les messages qui ne beneficient pas d'une liaison directe doivent être routés de voisin en voisin jusqu'à leur destination. Les performances de ces machines sont tributaires de l'adéquation entre le graphe des communications entre tâches et le graphe d'interconnexion<br />physique des processeurs.<br />Cette thèse examine les possibilités offertes par les machines<br />à réseau d'interconnexion programmable, dites reconfigurables, et<br />deux modes de fonctionnement seront étudiés. La reconfiguration synchrone programme le réseau d'interconnexion en une seule fois avant l'exécution de l'application. Le routage des messages n'est pas totalement éliminé et l'utilisation possible de topologies irrégulières en complique la mise en oeuvre. Le réseau peut au contraire être reprogrammé systématiquement pour chaque message de telle sorte qu'il bénéficie d'une liaison directe le temps de son transfert. Ce mode de reconfiguration, dit asynchrone, impose<br />de fortes contraintes sur la vitesse de commande du réseau.<br />Cette thèse a été entreprise dans le cadre du projet de recherche<br />européen ESPRIT "supernode" ; le but de celui-ci étant la construction de multiprocesseurs reconfigurables à base de transputers.

Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits

Les circuits FPGAs (Field Programmable Gate Arrays) sont devenus des acteurs importants dans le domaine du traitement numérique qui a été dominé auparavant par les microprocesseurs et les circuits intégrés spéci ques. Le plus grand dé pour les FPGAs aujourd'hui est de présenter un bon compromis entre une grande souplesse et de bonnes performances (vitesse, surface et consommation). La combinaison de trois facteurs dé nit les caractéristiques d'un circuit FPGA: la qualité de l'architecture, la qualité des outils CAO de con guration et la conception électrique du FPGA. L'objet de cette thèse est l'exploration de nouvelles architectures et de structures d'interconnexion qui pourront améliorer les performances de ces circuits. En effet, les ressources d'interconnexion occupent 90% de la surface totale et occasionnent 60% de la consommation électrique. Les architectures étudiées présentent des structures matricielles et arborescentes. Les principaux résultats sont les suivants: Au départ nous explorons différentes topologies arborescentes et nous comparons leurs surfaces à celles des architectures matricielles. Pour cela, nous développons une plateforme d'outils logiciels permettant d'implanter différents circuits logiques sur l'architecture cible. En se basant sur cette étude expérimentale, nous dé nissons une nouvelle architecture arborescente. Nous montrons, en nous appuyant sur un modèle d'estimation de surface, que cette architecture permet de réduire la surface totale de 56% par rapport à une architecture matricielle. Ceci est dû essentiellement à une meilleure utilisation des ressources d'interconnexion. Nous explorons les effets des différents paramètres de l'architecture proposée: le coef cient de Rent, la taille des groupes logiques et le nombre d'entrées par bloc logique. Ceci permet de régler l'architecture pour l'adapter à des domaines d'applications qui ont des contraintes spéci ques en terme de surface, vitesse et consommation. En n, nous proposons une architecture qui rassemble les avantages des structures arborescentes et matricielles. Nous uni ons les deux structures en construisant des groupes de blocs logiques qui ont localement un réseau d'interconnexion arborescent et qui sont connectés entre eux via un réseau matriciel. Nous montrons que l'architecture obtenue présente un bon compromis entre l'évolutivité de la vue physique et la densité de la surface.

Les résultats obtenus dans cette thèse portent principalement sur l' étude des communications dans les architectures parallèles, distribuées ou réseaux d'interconnexion.<br>Dans le chapitre 1 nous présentons brièvement une rapide classification des machines parallèles. Puis nous décrivons en détails les principaux mécanismes de routage des messages existant à l'heure actuelle dans de telles machines. Nous détaillons en particulier, les nouveaux mécanismes de routage du type "wormhole". Ce chapitre contient également un bref rappel des principales notions de théorie des graphes utilisées pour la modélisation des machines parallèles à mémoire distribuée.<br>Les chapitres 2, 3 et 4 dressent une synthèse des travaux qui nous paraissent les plus significatifs sur quelques principaux problèmes de communications globales (diffusion, échange total et multidistribution) par commutation de circuits, tout au moins lorsque l'on cherche essentiellement à minimiser le nombre d'étapes des protocoles.<br>Dans le chapitre 5 nous résumons en premier lieu nos travaux sur la décomposition hamiltonienne du réseau Butterfly généralisé, puis en second lieu nous donnons notre approche au problème des larges graphes à degré et diamètre fixés.

.

Le modèle d'acteurs est un modèle de calcul concurrent qui semble bien adapté au modèle d'exécution des architectures massivement parallèles. Nous étudions son adéquation à une machine massivement parallèle à grain fin étudiée dans notre groupe ; nous dégageons les mécanismes de base à intégrer au niveau de l'unité de routage de cette machine. Pour des modèles de programmation dynamiques de ce type, il est nécessaire d'établir une stratégie d'allocation dynamique de processus. Nous proposons et évaluons une idée originale pour l'allocation dynamique de processus dans une architecture massivement parallèle. Dans le cas d'une machine à grain fin comme la nôtre, il est primordial qu'une telle fonction n'induise qu'un minimum de charge supplémentaire en termes de communications. Nous présentons une fonction intégrée de recherche de processeurs libres pour l'exécution des processus dynamiques. L'évaluation des principaux choix architecturaux a pu être menée grâce à un simulateur développé dans le cadre de ce travail. Les résultats obtenus, qui démontrent l'intérêt de l'approche, sont présentés dans cette thèse.