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