Compilation efficace pour FPGA reconfigurable dynamiquement

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Modélisation et réalisation de la couche physique du système de communication numérique sans fil, WiMax, sur du matériel reconfigurable

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Parallelization of SAT on Reconfigurable Hardware

Quoique très difficile à résoudre, le problème de satisfiabilité Booléenne (SAT) est fréquemment utilisé lors de la modélisation d’applications industrielles. À cet effet, les deux dernières décennies ont vu une progression fulgurante des outils conçus pour trouver des solutions à ce problème NP-complet. Deux grandes avenues générales ont été explorées afin de produire ces outils, notamment l’approche logicielle et matérielle. Afin de raffiner et améliorer ces solveurs, de nombreuses techniques et heuristiques ont été proposées par la communauté de recherche. Le but final de ces outils a été de résoudre des problèmes de taille industrielle, ce qui a été plus ou moins accompli par les solveurs de nature logicielle. Initialement, le but de l’utilisation du matériel reconfigurable a été de produire des solveurs pouvant trouver des solutions plus rapidement que leurs homologues logiciels. Cependant, le niveau de sophistication de ces derniers a augmenté de telle manière qu’ils restent le meilleur choix pour résoudre SAT. Toutefois, les solveurs modernes logiciels n’arrivent toujours pas a trouver des solutions de manière efficace à certaines instances SAT. Le but principal de ce mémoire est d’explorer la résolution du problème SAT dans le contexte du matériel reconfigurable en vue de caractériser les ingrédients nécessaires d’un solveur SAT efficace qui puise sa puissance de calcul dans le parallélisme conféré par une plateforme FPGA. Le prototype parallèle implémenté dans ce travail est capable de se mesurer, en termes de vitesse d’exécution à d’autres solveurs (matériels et logiciels), et ce sans utiliser aucune heuristique. Nous montrons donc que notre approche matérielle présente une option prometteuse vers la résolution d’instances industrielles larges qui sont difficilement abordées par une approche logicielle.

Le poteau d’utilité publique, icône d’un autre siècle?

Le réseau de distribution aérien, ou plus simplement le réseau de poteaux de bois et ses câbles, est encore aujourd’hui omniprésent dans la majorité des villes du Québec. Pour plusieurs, le réseau de poteaux d’utilité publique semble appartenir à une autre époque. Pourtant, les poteaux et câbles ne sont pas près de disparaître, au contraire, ils ne cessent de se transformer. Depuis peu, de plus en plus d’équipements s’ajoutent sur le réseau: boîtiers techniques, nombre de câbles, appareillages au sommet des poteaux, antennes de communication, etc. Bien que les équipements du réseau de distribution aérien soient des éléments produits industriellement, ceux-ci intègrent rarement les services du design industriel au moment de leur conception initiale. Cette recherche étudie le système de distribution aérien sous l’angle de la « pensée design ». L’intention de cette étude est d’analyser les impacts de la présence du réseau aérien en milieux urbains et a pour objectif d’orienter les pratiques de conception de ce type d’équipements. Pour ce faire, dans une optique transdisciplinaire, diverses approches ont été sollicitées dont: l’approche systémique, l’approche paysage et les approches des partenaires des réseaux. Au moyen d’une recherche documentaire et d’observations faites sur le terrain, la recherche vise à dresser un portrait général du réseau de distribution aérien et les défis qui y sont associés. La recherche expose, dans un état des lieux, les résultats issus des questions analytiques de recherche suivantes: de quoi est composé le réseau de distribution aérien, quels sont les intervenants sur le réseau, quelles sont leurs interactions, quels sont les points de vue des différentes catégories d’acteurs en relation avec le réseau, quels sont les impacts reliés à la présence du réseau en milieux urbains et quelle a été son évolution au fil des années. Dans la perspective de l’approche design, chercher à comprendre une problématique de façon plus large permet de s’assurer que l’on répond au bon problème, que l’on considère tous les facteurs en cause visant ainsi à réduire les répercussions négatives sur les contextes de vie actuels et futurs. Les principaux constats de cette recherche démontrent que la composition du réseau de distribution, avant même de considérer les nouveaux usages et l’ajout de nouveaux équipements, présente des lacunes importantes. La gestion entre les divers partenaires du réseau de distribution pose aussi problème. L’ajout de nouveaux équipements sur le réseau, combiné aux multiples équipements apparaissant sur les voies publiques laisse entrevoir l’atteinte d’un niveau de saturation des milieux urbains. Les façons de faire hermétiques et «cristallisées» des partenaires du réseau ne collent pas avec les initiatives et aspirations générales en matière d’aménagement. En étudiant la problématique du réseau de distribution par le biais de la pensée design, l’approche design cherche à déceler, de façon proactive, les opportunités de design qui permettront de mieux gérer l’apparition et l’intégration des nouveaux équipements sur les poteaux. Cette démarche permet d’envisager des solutions qui visent à limiter les répercussions collatérales une fois en contexte et qui, du même coup, adressent des problématiques connexes. Finalement, à la lumière de l’état des lieux, cette recherche propose des critères de conception de futurs réseaux de distribution, élaborés dans l’esprit de l’approche design.

Habitat variability and the individual variability of juvenile Atlantic salmon (Salmo salar)

La variabilité spatiale et temporelle de l’écoulement en rivière contribue à créer une mosaïque d’habitat dynamique qui soutient la diversité écologique. Une des questions fondamentales en écohydraulique est de déterminer quelles sont les échelles spatiales et temporelles de variation de l’habitat les plus importantes pour les organismes à divers stades de vie. L’objectif général de la thèse consiste à examiner les liens entre la variabilité de l’habitat et le comportement du saumon Atlantique juvénile. Plus spécifiquement, trois thèmes sont abordés : la turbulence en tant que variable d’habitat du poisson, les échelles spatiales et temporelles de sélection de l’habitat et la variabilité individuelle du comportement du poisson. À l’aide de données empiriques détaillées et d’analyses statistiques variées, nos objectifs étaient de 1) quantifier les liens causaux entre les variables d’habitat du poisson « usuelles » et les propriétés turbulentes à échelles multiples; 2) tester l’utilisation d’un chenal portatif pour analyser l’effet des propriétés turbulentes sur les probabilités de capture de proie et du comportement alimentaire des saumons juvéniles; 3) analyser les échelles spatiales et temporelles de sélection de l’habitat dans un tronçon l’été et l’automne; 4) examiner la variation individuelle saisonnière et journalière des patrons d’activité, d’utilisation de l’habitat et de leur interaction; 5) investiguer la variation individuelle du comportement spatial en relation aux fluctuations environnementales. La thèse procure une caractérisation détaillée de la turbulence dans les mouilles et les seuils et montre que la capacité des variables d’habitat du poisson usuelles à expliquer les propriétés turbulentes est relativement basse, surtout dans les petites échelles, mais varie de façon importante entre les unités morphologiques. D’un point de vue pratique, ce niveau de complexité suggère que la turbulence devrait être considérée comme une variable écologique distincte. Dans une deuxième expérience, en utilisant un chenal portatif in situ, nous n’avons pas confirmé de façon concluante, ni écarté l’effet de la turbulence sur la probabilité de capture des proies, mais avons observé une sélection préférentielle de localisations où la turbulence était relativement faible. La sélection d’habitats de faible turbulence a aussi été observée en conditions naturelles dans une étude basée sur des observations pour laquelle 66 poissons ont été marqués à l’aide de transpondeurs passifs et suivis pendant trois mois dans un tronçon de rivière à l’aide d’un réseau d’antennes enfouies dans le lit. La sélection de l’habitat était dépendante de l’échelle d’observation. Les poissons étaient associés aux profondeurs modérées à micro-échelle, mais aussi à des profondeurs plus élevées à l’échelle des patchs. De plus, l’étendue d’habitats utilisés a augmenté de façon asymptotique avec l’échelle temporelle. L’échelle d’une heure a été considérée comme optimale pour décrire l’habitat utilisé dans une journée et l’échelle de trois jours pour décrire l’habitat utilisé dans un mois. Le suivi individuel a révélé une forte variabilité inter-individuelle des patrons d’activité, certains individus étant principalement nocturnes alors que d’autres ont fréquemment changé de patrons d’activité. Les changements de patrons d’activité étaient liés aux variables environnementales, mais aussi à l’utilisation de l’habitat des individus, ce qui pourrait signifier que l’utilisation d’habitats suboptimaux engendre la nécessité d’augmenter l’activité diurne, quand l’apport alimentaire et le risque de prédation sont plus élevés. La variabilité inter-individuelle élevée a aussi été observée dans le comportement spatial. La plupart des poissons ont présenté une faible mobilité la plupart des jours, mais ont occasionnellement effectué des mouvements de forte amplitude. En fait, la variabilité inter-individuelle a compté pour seulement 12-17% de la variabilité totale de la mobilité des poissons. Ces résultats questionnent la prémisse que la population soit composée de fractions d’individus sédentaires et mobiles. La variation individuelle journalière suggère que la mobilité est une réponse à des changements des conditions plutôt qu’à un trait de comportement individuel.

Domain/Multi-Domain Protection and Provisioning in Optical Networks

L’évolution récente des commutateurs de sélection de longueurs d’onde (WSS -Wavelength Selective Switch) favorise le développement du multiplexeur optique d’insertionextraction reconfigurable (ROADM - Reconfigurable Optical Add/Drop Multiplexers) à plusieurs degrés sans orientation ni coloration, considéré comme un équipement fort prometteur pour les réseaux maillés du futur relativement au multiplexage en longueur d’onde (WDM -Wavelength Division Multiplexing ). Cependant, leur propriété de commutation asymétrique complique la question de l’acheminement et de l’attribution des longueur d’ondes (RWA - Routing andWavelength Assignment). Or la plupart des algorithmes de RWA existants ne tiennent pas compte de cette propriété d’asymétrie. L’interruption des services causée par des défauts d’équipements sur les chemins optiques (résultat provenant de la résolution du problème RWA) a pour conséquence la perte d’une grande quantité de données. Les recherches deviennent ainsi incontournables afin d’assurer la survie fonctionnelle des réseaux optiques, à savoir, le maintien des services, en particulier en cas de pannes d’équipement. La plupart des publications antérieures portaient particulièrement sur l’utilisation d’un système de protection permettant de garantir le reroutage du trafic en cas d’un défaut d’un lien. Cependant, la conception de la protection contre le défaut d’un lien ne s’avère pas toujours suffisante en termes de survie des réseaux WDM à partir de nombreux cas des autres types de pannes devenant courant de nos jours, tels que les bris d’équipements, les pannes de deux ou trois liens, etc. En outre, il y a des défis considérables pour protéger les grands réseaux optiques multidomaines composés de réseaux associés à un domaine simple, interconnectés par des liens interdomaines, où les détails topologiques internes d’un domaine ne sont généralement pas partagés à l’extérieur. La présente thèse a pour objectif de proposer des modèles d’optimisation de grande taille et des solutions aux problèmes mentionnés ci-dessus. Ces modèles-ci permettent de générer des solutions optimales ou quasi-optimales avec des écarts d’optimalité mathématiquement prouvée. Pour ce faire, nous avons recours à la technique de génération de colonnes afin de résoudre les problèmes inhérents à la programmation linéaire de grande envergure. Concernant la question de l’approvisionnement dans les réseaux optiques, nous proposons un nouveau modèle de programmation linéaire en nombres entiers (ILP - Integer Linear Programming) au problème RWA afin de maximiser le nombre de requêtes acceptées (GoS - Grade of Service). Le modèle résultant constitue celui de l’optimisation d’un ILP de grande taille, ce qui permet d’obtenir la solution exacte des instances RWA assez grandes, en supposant que tous les noeuds soient asymétriques et accompagnés d’une matrice de connectivité de commutation donnée. Ensuite, nous modifions le modèle et proposons une solution au problème RWA afin de trouver la meilleure matrice de commutation pour un nombre donné de ports et de connexions de commutation, tout en satisfaisant/maximisant la qualité d’écoulement du trafic GoS. Relativement à la protection des réseaux d’un domaine simple, nous proposons des solutions favorisant la protection contre les pannes multiples. En effet, nous développons la protection d’un réseau d’un domaine simple contre des pannes multiples, en utilisant les p-cycles de protection avec un chemin indépendant des pannes (FIPP - Failure Independent Path Protecting) et de la protection avec un chemin dépendant des pannes (FDPP - Failure Dependent Path-Protecting). Nous proposons ensuite une nouvelle formulation en termes de modèles de flots pour les p-cycles FDPP soumis à des pannes multiples. Le nouveau modèle soulève un problème de taille, qui a un nombre exponentiel de contraintes en raison de certaines contraintes d’élimination de sous-tour. Par conséquent, afin de résoudre efficacement ce problème, on examine : (i) une décomposition hiérarchique du problème auxiliaire dans le modèle de décomposition, (ii) des heuristiques pour gérer efficacement le grand nombre de contraintes. À propos de la protection dans les réseaux multidomaines, nous proposons des systèmes de protection contre les pannes d’un lien. Tout d’abord, un modèle d’optimisation est proposé pour un système de protection centralisée, en supposant que la gestion du réseau soit au courant de tous les détails des topologies physiques des domaines. Nous proposons ensuite un modèle distribué de l’optimisation de la protection dans les réseaux optiques multidomaines, une formulation beaucoup plus réaliste car elle est basée sur l’hypothèse d’une gestion de réseau distribué. Ensuite, nous ajoutons une bande pasiv sante partagée afin de réduire le coût de la protection. Plus précisément, la bande passante de chaque lien intra-domaine est partagée entre les p-cycles FIPP et les p-cycles dans une première étude, puis entre les chemins pour lien/chemin de protection dans une deuxième étude. Enfin, nous recommandons des stratégies parallèles aux solutions de grands réseaux optiques multidomaines. Les résultats de l’étude permettent d’élaborer une conception efficace d’un système de protection pour un très large réseau multidomaine (45 domaines), le plus large examiné dans la littérature, avec un système à la fois centralisé et distribué.