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.

Caractérisation électro-clinique des convulsions fébriles et risque d’épilepsie

Environ 2-3% d’enfants avec convulsions fébriles (CF) développent une épilepsie, mais les outils cliniques existants ne permettent pas d’identifier les enfants susceptibles de développer une épilepsie post-convulsion fébrile. Des études ont mis en évidence des anomalies d’EEG quantifiée, et plus particulièrement en réponse à la stimulation lumineuse intermittente (SLI), chez des patients épileptiques. Aucune étude n’a analysé ces paramètres chez l’enfant avec CF et il importe de déterminer s’ils sont utiles pour évaluer le pronostic des CF. Les objectifs de ce programme de recherche étaient d’identifier, d’une part, des facteurs de risque cliniques qui déterminent le développement de l’épilepsie après des CF et, d’autre part, des marqueurs électrophysiologiques quantitatifs qui différencieraient les enfants avec CF des témoins et pourraient aider à évaluer leur pronostic. Afin de répondre à notre premier objectif, nous avons analysé les dossiers de 482 enfants avec CF, âgés de 3 mois à 6 ans. En utilisant des statistiques de survie, nous avons décrit les facteurs de risque pour développer une épilepsie partielle (antécédents prénataux, retard de développement, CF prolongées et focales) et généralisée (antécédents familiaux d’épilepsie, CF récurrentes et après l’âge de 4 ans). De plus, nous avons identifié trois phénotypes cliniques distincts ayant un pronostic différent : (i) CF simples avec des antécédents familiaux de CF et sans risque d’épilepsie ultérieure; (ii) CF récurrentes avec des antécédents familiaux d’épilepsie et un risque d’épilepsie généralisée; (iii) CF focales avec des antécédents familiaux d’épilepsie et un risque d’épilepsie partielle. Afin de répondre à notre deuxième objectif, nous avons d’abord analysé les potentiels visuels steady-state (PEVSS) évoqués par la SLI (5, 7,5, 10 et 12,5 Hz) en fonction de l’âge. Le tracé EEG de haute densité (128 canaux) a été enregistré chez 61 enfants âgés entre 6 mois et 16 ans et 8 adultes normaux. Nous rapportons un développement topographique différent de l’alignement de phase des composantes des PEVSS de basses (5-15 Hz) et de hautes (30-50 Hz) fréquences. Ainsi, l’alignement de phase des composantes de basses fréquences augmente en fonction de l’âge seulement au niveau des régions occipitale et frontale. Par contre, les composantes de hautes fréquences augmentent au niveau de toutes les régions cérébrales. Puis, en utilisant cette même méthodologie, nous avons investigué si les enfants avec CF présentent des anomalies des composantes gamma (50-100 Hz) des PEVSS auprès de 12 cas de CF, 5 frères et sœurs des enfants avec CF et 15 témoins entre 6 mois et 3 ans. Nous montrons une augmentation de la magnitude et de l’alignement de phase des composantes gamma des PEVSS chez les enfants avec CF comparés au groupe témoin et à la fratrie. Ces travaux ont permis d’identifier des phénotypes électro-cliniques d’intérêt qui différencient les enfants avec CF des enfants témoins et de leur fratrie. L’étape suivante sera de vérifier s’il y a une association entre les anomalies retrouvées, la présentation clinique et le pronostic des CF. Cela pourrait éventuellement aider à identifier les enfants à haut risque de développer une épilepsie et permettre l’institution d’un traitement neuroprotecteur précoce.

Le néo-chamanisme de Michael Harner : étude des transformations du chamanisme classique à la lumière de l’analyse des transformations religieuses selon Danièle Hervieu-Léger

Durant le dernier demi-siècle, la religion, comme tous les autres domaines d’activité humaine, a connu plusieurs transformations importantes. La diminution considérable, durant cette période, de la pratique religieuse institutionnalisée est accompagnée de l’apparition d’une multitude de nouvelles formes de spiritualités qui tentent de répondre aux besoins religieux de l’homme occidental. Parmi les multiples manifestations de ce genre, on découvre une spiritualité distincte, appelée néo-chamanisme ou chamanisme urbain, réunissant de nombreuses pratiques contemporaines qui se définissent comme chamaniques. Dans le cadre de ce mémoire, nous nous sommes concentrés sur l’étude du phénomène néo-chamanique de Michael Harner, ex-professeur et directeur du département d’anthropologie au Graduate Faculty of the New School for Social Research à New York, et fondateur de la Foundation for Shamanic Studies (à l’avenir : FSS). La présente recherche a pour but d’analyser le néo-chamanisme de Harner et de définir sa place parmi les nouvelles formes de religiosités. La théorie de la recomposition du religieux de Danièle Hervieu-Léger sert de cadre d’analyse pour cette nouvelle forme de spiritualité. Dans la première partie, nous traitons le phénomène religieux contemporain sous l’angle socioreligieux. Nous présentons un aperçu global des transformations que celui-ci subit en modernité sous l’impact de la sécularisation. À l’aide de la théorie des nouvelles formes religieuses de Danièle Hervieu-Léger, nous mettons en lumière les principales règles selon lesquelles une nouvelle configuration du religieux se déploie dans le contexte occidental contemporain. Dans la seconde partie, nous examinons le chamanisme traditionnel sous l’angle anthropologique. Nous faisons la lecture d’études classiques sur le chamanisme. Il apparaît que le chamanisme classique est communautaire, réservé à quelques personnes choisies par les esprits et que le processus laborieux d’initiation permettant d’accéder à cette fonction implique certains éléments spécifiques parmi lesquels on compte la maladie initiatique, la mort rituelle et la résurrection de la personne. Dans la troisième partie, nous examinons le néo-chamanisme de Harner. Nous rendons compte de son ouvrage majeur La voie spirituelle du chamane : Le Secret d'un sorcier indien d’Amérique du Nord et nous examinons l’expérience chamanique de la Foundation for Shamanic Studies (FSS). Il se dégage de cette étude que l’approche de Harner se veut l’expression d’un chamanisme fondamental et universel adapté à la société contemporaine. La pratique néo-chamanique de Harner se focalise sur le voyage chamanique et sur le contact avec le monde des esprits comme des éléments qui sont au cœur du chamanisme traditionnel. C’est une pratique axée principalement sur l’individu à des fins d’accomplissement de soi et d’(auto)guérison. Elle attire généralement des personnes dont le niveau de scolarité est élevé, disposées à payer pour les services fournis par la fondation. À la fin de notre étude, nous dégageons les conclusions générales suivantes : le néo-chamanisme de Harner s’éloigne de la tradition chamanique et la transforme en une spiritualité nouvelle adaptée aux besoins des Occidentaux; il reflète les transformations subies par le fait religieux pendant la période moderne; il s’adresse principalement à un public en quête de services spirituels ciblés et ponctuels et il favorise une forme de communalisation temporaire et intense; cependant, l’individuation de la pratique chamanique est porteuse de ses effets politiques et néocoloniaux.

Influence de l'initiation de la traduction sur le changement programmé du cadre de lecture en -1 responsable de la synthèse des enzymes du virus de l’immunodéficience humaine de type 1

Le virus de l’immunodéficience humaine de type 1 (VIH-1) est responsable du syndrome de l’immunodéficience acquise (SIDA). Il faut identifier de nouvelles cibles pour le développement d’agents anti-VIH-1, car ce virus développe une résistance aux agents présentement utilisés. Notre but est d’approfondir la caractérisation de l’étape du changement de cadre de lecture ribosomique en -1 (déphasage -1) nécessaire à la production du précurseur des enzymes du VIH-1. Ce déphasage est programmé et effectué par une minorité de ribosomes lorsqu’ils traduisent la séquence dite glissante à un endroit spécifique de l’ARN messager (ARNm) pleine-longueur du VIH-1. L’efficacité de déphasage est contrôlée par le signal stimulateur de déphasage (SSF), une tige-boucle irrégulière située en aval de la séquence glissante. La structure du SSF est déroulée lors du passage d’un ribosome, mais elle peut se reformer ensuite. Nous avons montré que des variations de l’initiation de la traduction affectent l’efficacité de déphasage. Nous avons utilisé, dans des cellules Jurkat-T et HEK 293T, un rapporteur bicistronique où les gènes codant pour les luciférases de la Renilla (Rluc) et de la luciole (Fluc) sont séparés par la région de déphasage du VIH-1. La Rluc est produite par tous les ribosomes traduisant l’ARNm rapporteur alors que la Fluc est produite uniquement par les ribosomes effectuant un déphasage. L’initiation de ce rapporteur est coiffe-dépendante, comme pour la majorité des ARNm cellulaires. Nous avons examiné l’effet de trois inhibiteurs de l’initiation et montré que leur présence augmente l’efficacité de déphasage. Nous avons ensuite étudié l’effet de la tige-boucle TAR, qui est présente à l’extrémité 5’ de tous les ARNm du VIH-1. TAR empêche la liaison de la petite sous-unité du ribosome (40S) à l’ARNm et module aussi l’activité de la protéine kinase dépendante de l’ARN double-brin (PKR). L’activation de PKR inhibe l’initiation en phosphorylant le facteur d’initiation eucaryote 2 (eIF2) alors que l’inhibition de PKR a l’effet inverse. Nous avons étudié l’effet de TAR sur la traduction et le déphasage via son effet sur PKR en utilisant TAR en trans ou en cis, mais à une certaine distance de l’extrémité 5’ afin d’éviter l’interférence avec la liaison de la 40S. Nous avons observé qu’une faible concentration de TAR, qui active PKR, augmente l’efficacité de déphasage alors qu’une concentration élevée de TAR, qui inhibe PKR, diminue cette efficacité. Nous avons proposé un modèle où des variations de l’initiation affectent l’efficacité de déphasage en modifiant la distance entre les ribosomes parcourant l’ARNm et, donc, la probabilité qu’ils rencontrent un SSF structuré. Par la suite, nous avons déterminé l’effet de la région 5’ non traduite (UTR) de l’ARNm pleine-longueur du VIH-1 sur l’efficacité de déphasage. Cette 5’UTR contient plusieurs régions structurées, dont TAR à l’extrémité 5’, qui peut interférer avec l’initiation. Cet ARNm a une coiffe permettant une initiation coiffe-dépendante ainsi qu’un site d’entrée interne des ribosomes (IRES), permettant une initiation IRES-dépendante. Nous avons introduit cette 5’UTR, complète ou en partie, comme 5’UTR de notre ARNm rapporteur bicistronique. Nos résultats démontrent que cette 5’UTR complète inhibe l’initiation coiffe dépendante et augmente l’efficacité de déphasage et que ces effets sont dus à la présence de TAR suivie de la tige-boucle Poly(A). Nous avons aussi construit un rapporteur tricistronique où les ribosomes exprimant les luciférases utilisent obligatoirement l’IRES. Nous avons observé que cette initiation par l’IRES est faible et que l’efficacité de déphasage correspondante est également faible. Nous avons formulé une hypothèse pour expliquer cette situation. Nous avons également observé que lorsque les deux modes d’initiation sont disponibles, l’initiation coiffe dépendante est prédominante. Finalement, nous avons étudié l’effet de la protéine virale Tat sur l’initiation de la traduction et sur l’efficacité de déphasage. Nous avons montré qu’elle augmente l’initiation de la traduction et que son effet est plus prononcé lorsque TAR est située à l’extrémité 5’ des ARNm. Nous proposons un modèle expliquant les effets de Tat sur l’initiation de la traduction par l’inhibition de PKR ainsi que par des changements de l’expression de protéines cellulaires déroulant TAR. Ces résultats permettent de mieux comprendre les mécanismes régissant le déphasage du VIH-1, ce qui est essentiel pour le développement d’agents anti-déphasage.

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é.