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.

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

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

Timing verification in transaction modeling

Les systèmes Matériels/Logiciels deviennent indispensables dans tous les aspects de la vie quotidienne. La présence croissante de ces systèmes dans les différents produits et services incite à trouver des méthodes pour les développer efficacement. Mais une conception efficace de ces systèmes est limitée par plusieurs facteurs, certains d'entre eux sont: la complexité croissante des applications, une augmentation de la densité d'intégration, la nature hétérogène des produits et services, la diminution de temps d’accès au marché. Une modélisation transactionnelle (TLM) est considérée comme un paradigme prometteur permettant de gérer la complexité de conception et fournissant des moyens d’exploration et de validation d'alternatives de conception à des niveaux d’abstraction élevés. Cette recherche propose une méthodologie d’expression de temps dans TLM basée sur une analyse de contraintes temporelles. Nous proposons d'utiliser une combinaison de deux paradigmes de développement pour accélérer la conception: le TLM d'une part et une méthodologie d’expression de temps entre différentes transactions d’autre part. Cette synergie nous permet de combiner dans un seul environnement des méthodes de simulation performantes et des méthodes analytiques formelles. Nous avons proposé un nouvel algorithme de vérification temporelle basé sur la procédure de linéarisation des contraintes de type min/max et une technique d'optimisation afin d'améliorer l'efficacité de l'algorithme. Nous avons complété la description mathématique de tous les types de contraintes présentées dans la littérature. Nous avons développé des méthodes d'exploration et raffinement de système de communication qui nous a permis d'utiliser les algorithmes de vérification temporelle à différents niveaux TLM. Comme il existe plusieurs définitions du TLM, dans le cadre de notre recherche, nous avons défini une méthodologie de spécification et simulation pour des systèmes Matériel/Logiciel basée sur le paradigme de TLM. Dans cette méthodologie plusieurs concepts de modélisation peuvent être considérés séparément. Basée sur l'utilisation des technologies modernes de génie logiciel telles que XML, XSLT, XSD, la programmation orientée objet et plusieurs autres fournies par l’environnement .Net, la méthodologie proposée présente une approche qui rend possible une réutilisation des modèles intermédiaires afin de faire face à la contrainte de temps d’accès au marché. Elle fournit une approche générale dans la modélisation du système qui sépare les différents aspects de conception tels que des modèles de calculs utilisés pour décrire le système à des niveaux d’abstraction multiples. En conséquence, dans le modèle du système nous pouvons clairement identifier la fonctionnalité du système sans les détails reliés aux plateformes de développement et ceci mènera à améliorer la "portabilité" du modèle d'application.

Design et implémentation sur FPGA d'un algorithme DES

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

Stabilité instrumentale en neuro imagerie fonctionnelle et structurelle

Dans ce mémoire, nous décrivons le travail effectué pour étendre nos connaissances sur les sources d’instabilité instrumentales en imagerie de résonance magnétique, en particulier dans le domaine anatomique par une étude où cinq adultes ont été scannés quatre fois dans la même plate-forme IRM, deux fois avant et deux fois après une mise à niveau importante d’un scanner 3T de Siemens. Les volumes de l’hippocampe droit et gauche de chaque sujet ont été mesurés avec une segmentation manuelle. Nous avons analysé la fiabilité test-retest avant et après la mise à niveau du système d’IRM. Dans le domaine fonctionnel, cinq adultes ont été scannés quatre fois dans la même plate forme IRM deux fois avant et deux fois après la même mise à niveau du scanneur. Les acquisitions du signal BOLD sont faites dans deux différentes résolutions spatiales (2x2x2mm et 4x4x4mm) pour évaluer la sensibilité du signal BOLD sous conditions de haute et basse SNR. Une dernière étude fonctionnelle sur fantôme avait pour but d’étudier la stabilité de la machine pour les images fonctionnelles et détecter les sources de bruit de type machine. La séquence EPI (Echo Planar Imaging) d’écho de gradient à deux dimensions a été utilisée. Des analyses comme le pourcentage des fluctuations et l’analyse de Fourier des résidus ont également été réalisées. Nous résultats indiquent que les différences dans le matériel provenant d’une importante mise à niveau ne peuvent pas compromettre la validité des études structurelles et fonctionnelles faites à travers la mise à niveau du scanneur. Les acquisitions quotidiennes ont permis de suivre l’évolution de la stabilité et de détecter toute source de bruit qui peut détériorer la détection des activations dans les images fonctionnelles.

Apprentissage machine efficace : théorie et pratique

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique.

Le soin du monde : incursions anthropologiques dans le Pan-African e-Network Project

Cette thèse enquête sur l’émergence d’espaces de soin à l’ère de la mondialisation numérique. Elle s’articule autour d’incursions au sein du Pan-African e Network Project (PAN), un réseau de cybersanté par l’entremise duquel des hôpitaux tertiaires situés en Inde offrent des services de téléconsultations et de formation médicale à des centres de santé africains. Des incursions sur la piste d’un projet en constante mutation, pour en saisir la polyvalence ontologique, la pertinence politique, la valeur thérapeutique. Le PAN, c’est une entreprise colossale, aux ramifications multiples. C’est le travail quotidien d’ingénieurs, médecins, gestionnaires. Ce sont des routines techniques, des équipements. À la fois emblème d’une résurgence de la coopération indo-africaine et expression d’une étonnante histoire cybermédicale indienne, le réseau incarne une Inde néolibérale, portée par l’ambition technique et commerciale de propulser la nation au centre de la marche du monde. Le PAN, c’est une ouverture numérique de la clinique, qui reconfigure la spatialité de la prise en charge de patients. C’est un réseau clé en main, une quête insatiable de maîtrise, une infrastructure largement sous-utilisée. C’est le projet d’une humanité à prendre en charge : une humanité prospère, en santé, connectée. De part en part, l’expérience du PAN problématise le telos cybermédical. Au romantisme d’une circulation fluide et désincarnée de l’information et de l’expertise, elle oppose la concrétude, la plasticité et la pure matérialité de pratiques situées. Qu’on parle de « dispositifs » (Foucault), de « réseaux » (Latour), ou de « sphères » (Sloterdijk), la prise en charge du vivant ne s’effectue pas sur des surfaces neutres et homogènes, mais relève plutôt de forces locales et immanentes. Le PAN pose la nécessité de penser la technique et le soin ensemble, et d’ainsi déprendre la question du devenir de la clinique autant du triomphalisme moderne de l’émancipation que du recueillement phénoménologique devant une expérience authentique du monde. Il s’agit, en somme, de réfléchir sur les pratiques, événements et formes de pouvoir qui composent ces « espaces intérieurs » que sont les réseaux cybermédicaux, dans tout leur vacarme, leur splendeur et leur insuffisance.

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

Le projet feedback : recherche d'un point de rencontre stylistique entre la musique électroacoustique glitch, le free jazz et le drone metal.

L’objectif principal de cette thèse de doctorat en composition consiste en la conceptualisation et création d’une oeuvre pour guitare électrique et dispositif électronique se situant à un point de rencontre stylistique entre le free jazz, la musique électro glitch et le drone métal. Le présent texte vise principalement à expliciter la démarche de création de cette oeuvre, intitulée feedback. À la suite du chapitre d'introduction qui décrit l'origine et les objectifs de ce projet de composition, le premier chapitre est consacré à une réflexion sur l'improvisation musicale. En partant d'une description générale de cette pratique et de ses origines, cinq manifestations de l'improvisation qui ont influencé l’oeuvre y sont décrites. Dans le deuxième chapitre est présentée l'hyperguitare qui a été développée pour la pièce ainsi que la description de ses composantes matérielles et logicielles. Dans le troisième chapitre sont décrits le contexte de création, le rôle de l’improvisation dans le processus de création et la description technique des quatre oeuvres composées en amont de feedback. Le quatrième chapitre est dédié à la pièce feedback inspirée de l'œuvre cinématographique et littéraire Fight Club et imprégnée, sur le plan stylistique, de la culture rock, du free jazz et de la musique électroacoustique glitch. En conclusion sont présentés les nouveaux objectifs que ces recherches ont engendrés.