Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

No description available.

La vision par ordinateur est primordiale pour la compréhension et l’analyse d’une scène routière afin de construire des systèmes d’aide à la conduite (ADAS) plus intelligents. Cependant, l’implémentation de ces systèmes dans un réel environnement automobile et loin d’être simple. En effet, ces applications nécessitent une haute performance de calcul en plus d’une précision algorithmique. Pour répondre à ces exigences, de nouvelles architectures hétérogènes sont apparues. Elles sont composées de plusieurs unités de traitement avec différentes technologies de calcul parallèle: GPU, accélérateurs dédiés, etc. Pour mieux exploiter les performances de ces architectures, différents langages sont nécessaires en fonction du modèle d’exécution parallèle. Dans cette thèse, nous étudions diverses méthodologies de programmation parallèle. Nous utilisons une étude de cas complexe basée sur la stéréo-vision. Nous présentons les caractéristiques et les limites de chaque approche. Nous évaluons ensuite les outils employés principalement en terme de performances de calcul et de difficulté de programmation. Le retour de ce travail de recherche est crucial pour le développement de futurs algorithmes de traitement d’images en adéquation avec les architectures parallèles avec un meilleur compromis entre les performances de calcul, la précision algorithmique et la difficulté de programmation. / Computer Vision (CV) is crucial for understanding and analyzing the driving scene to build more intelligent Advanced Driver Assistance Systems (ADAS). However, implementing CV-based ADAS in a real automotive environment is not straightforward. Indeed, CV algorithms combine the challenges of high computing performance and algorithm accuracy. To respond to these requirements, new heterogeneous circuits are developed. They consist of several processing units with different parallel computing technologies as GPU, dedicated accelerators, etc. To better exploit the performances of such architectures, different languages are required depending on the underlying parallel execution model. In this work, we investigate various parallel programming methodologies based on a complex case study of stereo vision. We introduce the relevant features and limitations of each approach. We evaluate the employed programming tools mainly in terms of computation performances and programming productivity. The feedback of this research is crucial for the development of future CV algorithms in adequacy with parallel architectures with a best compromise between computing performance, algorithm accuracy and programming efforts.

Les travaux de cette thèse s'inscrivent dans le cadre du projet Petasky. Notre objectif est de proposer des outils permettant de gérer des dizaines de Peta-octets de données issues d'observations astronomiques. Nos travaux se focalisent essentiellement sur la conception des nouveaux systèmes permettant de garantir le passage à l'échelle. Dans cette thèse, nos contributions concernent trois aspects : Benchmarking des systèmes existants, conception d'un nouveau système et optimisation du système. Nous avons commencé par analyser la capacité des systèmes fondés sur le modèle MapReduce et supportant SQL à gérer les données LSST et leurs capacités d'optimisation de certains types de requêtes. Nous avons pu constater qu'il n'y a pas de technique « magique » pour partitionner, stocker et indexer les données mais l'efficacité des techniques dédiées dépend essentiellement du type de requête et de la typologie des données considérées. Suite à notre travail de Benchmarking, nous avons retenu quelques techniques qui doivent être intégrées dans un système de gestion de données à large échelle. Nous avons conçu un nouveau système de façon à garantir la capacité dudit système à supporter plusieurs mécanismes de partitionnement et plusieurs opérateurs d'évaluation. Nous avons utilisé BSP (Bulk Synchronous Parallel) comme modèle de calcul. Les données sont représentées logiquement par des graphes. L'évaluation des requêtes est donc faite en explorant le graphe de données en utilisant les arcs entrants et les arcs sortants. Les premières expérimentations ont montré que notre approche permet une amélioration significative des performances par rapport aux systèmes Map/Reduce / This work is carried out in framework of the PetaSky project. The objective of this project is to provide a set of tools allowing to manage Peta-bytes of data from astronomical observations. Our work is concerned with the design of a scalable approach. We first started by analyzing the ability of MapReduce based systems and supporting SQL to manage the LSST data and ensure optimization capabilities for certain types of queries. We analyzed the impact of data partitioning, indexing and compression on query performance. From our experiments, it follows that there is no “magic” technique to partition, store and index data but the efficiency of dedicated techniques depends mainly on the type of queries and the typology of data that are considered. Based on our work on benchmarking, we identified some techniques to be integrated to large-scale data management systems. We designed a new system allowing to support multiple partitioning mechanisms and several evaluation operators. We used the BSP (Bulk Synchronous Parallel) model as a parallel computation paradigm. Unlike MapeReduce model, we send intermediate results to workers that can continue their processing. Data is logically represented as a graph. The evaluation of queries is performed by exploring the data graph using forward and backward edges. We also offer a semi-automatic partitioning approach, i.e., we provide the system administrator with a set of tools allowing her/him to choose the manner of partitioning data using the schema of the database and domain knowledge. The first experiments show that our approach provides a significant performance improvement with respect to Map/Reduce systems

Ce travail présente une approche modulaire bien adaptée à l'analyse de situations complexes d'assemblages de structures élastiques. L'approche CONTRAST (CONtact TRidimensionnel dans les Assemblages en STatique) prend facilement en compte les non-linéarités locales dues au contact ou à des éléments technologiques particuliers (joints élastomères, boulons fortement précontraints,...). Elle est basée sur une décomposition de l'assemblage en sous-structures et interfaces, qui sont des entités mécaniques à part entière avec leurs propres équations et leurs propres inconnues. Les interfaces jouent un rôle majeur en modélisant simplement les non-linéarités locales. Le schéma itératif de résolution est issu de la méthode à grand incrément de temps (LATIN method). L'approche CONTRAST est ainsi basée sur une formulation et une stratégie parallèles. Ce parallélisme est avant tout utilisé pour introduire flexibilité et modularité dans la définition du problème et autorise l'utilisation de maillages incompatibles sur les interfaces. Il permet aussi une réduction des coûts de calcul par rapport aux techniques éléments finis classiques. Des comparaisons avec un code de calcul industriel valident le traitement des problèmes de contact et de frottement. Des exemples d'assemblages industriels présentent les possibilités de l'approche ainsi que son comportement sur calculateur parallèle

Ce mémoire présente une implantation de la création paresseuse de tâches desti- née à des systèmes multiprocesseurs à mémoire distribuée. Elle offre un sous-ensemble des fonctionnalités du Message-Passing Interface et permet de paralléliser certains problèmes qui se partitionnent difficilement de manière statique grâce à un système de partitionnement dynamique et de balancement de charge. Pour ce faire, il se base sur le langage Multilisp, un dialecte de Scheme orienté vers le traitement parallèle, et implante sur ce dernier une interface semblable à MPI permettant le calcul distribué multipro- cessus. Ce système offre un langage beaucoup plus riche et expressif que le C et réduit considérablement le travail nécessaire au programmeur pour pouvoir développer des programmes équivalents à ceux en MPI. Enfin, le partitionnement dynamique permet de concevoir des programmes qui seraient très complexes à réaliser sur MPI. Des tests ont été effectués sur un système local à 16 processeurs et une grappe à 16 processeurs et il offre de bonnes accélérations en comparaison à des programmes séquentiels équiva- lents ainsi que des performances acceptables par rapport à MPI. Ce mémoire démontre que l’usage des futures comme technique de partitionnement dynamique est faisable sur des multiprocesseurs à mémoire distribuée. / This master’s thesis presents an implementation of lazy task creation for distributed memory multiprocessors. It offers a subset of Message-Passing Interface’s functionality and allows parallelization of some problems that are hard to statically partition thanks to its dynamic partitionning and load balancing system. It is based on Multilisp, a Scheme dialect for parallel computing, and implements an MPI like interface on top of it. It offers a richer and more expressive language than C and simplify the work needed to developp programs similar to those in MPI. Finally, dynamic partitioning allows some programs that would be very hard to develop in MPI. Tests were made on a 16 cpus computer and on a 16 cpus cluster. The system gets good accelerations when compared to equivalent sequential programs and acceptable performances when compared to MPI. It shows that it is possible to use futures as a dynamic partitioning method on distributed memory multiprocessors.

La simulation numérique est aujourd'hui un outils majeur dans la conception des objets aérodynamiques, que ce soit dans l'aéronautique, l'automobile, l'industrie navale, etc... Un des défis majeurs pour repousser les limites des codes de simulation est d'améliorer leur précision, tout en utilisant une quantité fixe de ressources (puissance et/ou temps de calcul). Cet objectif peut être atteint par deux approches différentes, soit en construisant une discrétisation fournissant sur un maillage donné une solution d'ordre très élevé, soit en construisant un schéma compact et massivement parallélisable, de manière à minimiser le temps de calcul en distribuant le problème sur un grand nombre de processeurs. Dans cette thèse, nous tentons de rassembler ces deux approches par le développement et l'implémentation de Schéma Distribuant le Résidu (RDS) d'ordre très élevé et de compacité maximale. Ce manuscrit commence par un rappel des principaux résultats mathématiques concernant les Lois de Conservation hyperboliques (CLs). Le but de cette première partie est de mettre en évidence les propriétés des solutions analytiques que nous cherchons à approcher, de manière à injecter ces propriétés dans celles de la solution discrète recherchée. Nous décrivons ensuite les trois étapes principales de la construction d'un schéma RD d'ordre très élevé : \begin{itemize} \item la représentation polynomiale d'ordre très élevé de la solution sur des polygones et des polyèdres; \item la description de méthodes distribuant le résidu de faible ordre, compactes et conservatives, consistantes avec une représentation polynomiale des données de très haut degré. Parmi elles, une attention particulière est donnée à la plus simple, issue d'une généralisation du schéma de Lax-Friedrichs (LxF); \item la mise en place d'une procédure préservant la positivité qui transforme tout schéma stable et linéaire, en un schéma non linéaire d'ordre très élevé, capturant les chocs de manière non oscillante. \end{itemize} Dans le manuscrit, nous montrons que les schémas obtenus par cette procédure sont consistants avec la CL considérée, qu'ils sont stables en norme $\L^{\infty}$ et qu'ils ont la bonne erreur de troncature. Même si tous ces développements théoriques ne sont démontrés que dans le cas de CL scalaires, des remarques au sujet des problèmes vectoriels sont faites dès que cela est possible. Malheureusement, lorsqu'on considère le schéma LxF, le problème algébrique non linéaire associé à la recherche de la solution stationnaire est en général mal posé. En particulier, on observe l'apparition de modes parasites de haute fréquence dans les régions de faible gradient. Ceux-ci sont éliminés grâce à un terme supplémentaire de stabilisation dont les effets et l'évaluation numérique sont précisément détaillés. Enfin, nous nous intéressons à une discrétisation correcte des conditions limites pour le schéma d'ordre élevé proposé. Cette théorie est ensuite illustrée sur des cas test scalaires bidimensionnels simples. Afin de montrer la généralité de notre approche, des maillages composés uniquement de triangles et des maillages hybrides, composés de triangles et de quadrangles, sont utilisés. Les résultats obtenus par ces tests confirment ce qui est attendu par la théorie et mettent en avant certains avantages des maillages hybrides. Nous considérons ensuite des solutions bidimensionnelles des équations d'Euler de la dynamique des gaz. Les résultats sont assez bons, mais on perd les pentes de convergence attendues dès que des conditions limite de paroi sont utilisées. Ce problème nécessite encore d'être étudié. Nous présentons alors l'implémentation parallèle du schéma. Celle-ci est analysée et illustrée à travers des cas test tridimensionnel de grande taille. Du fait de la relative nouveauté et de la complexité des problèmes tridimensionels, seuls des remarques qualitatives sont faites pour ces cas test : le comportement global semble être bon, mais plus de travail est encore nécessaire pour définir les propriétés du schémas en trois dimensions. Enfin, nous présentons une extension possible du schéma aux équations de Navier-Stokes dans laquelle les termes visqueux sont traités par une formulation de type Galerkin. La consistance de cette formulation avec les équations de Navier-Stokes est démontrée et quelques remarques au sujet de la précision du schéma sont soulevées. La méthode est validé sur une couche limite de Blasius pour laquelle nous obtenons des résultats satisfaisants. Ce travail offre une meilleure compréhension des propriétés générales des schémas RD d'ordre très élevé et soulève de nouvelles questions pour des améliorations futures. Ces améliorations devrait faire des schémas RD une alternative attractive aux discrétisations classiques FV ou ENO/WENO, aussi bien qu'aux schémas Galerkin Discontinu d'ordre très élevé, de plus en plus populaires.

Ce mémoire présente une implantation de la création paresseuse de tâches desti- née à des systèmes multiprocesseurs à mémoire distribuée. Elle offre un sous-ensemble des fonctionnalités du Message-Passing Interface et permet de paralléliser certains problèmes qui se partitionnent difficilement de manière statique grâce à un système de partitionnement dynamique et de balancement de charge. Pour ce faire, il se base sur le langage Multilisp, un dialecte de Scheme orienté vers le traitement parallèle, et implante sur ce dernier une interface semblable à MPI permettant le calcul distribué multipro- cessus. Ce système offre un langage beaucoup plus riche et expressif que le C et réduit considérablement le travail nécessaire au programmeur pour pouvoir développer des programmes équivalents à ceux en MPI. Enfin, le partitionnement dynamique permet de concevoir des programmes qui seraient très complexes à réaliser sur MPI. Des tests ont été effectués sur un système local à 16 processeurs et une grappe à 16 processeurs et il offre de bonnes accélérations en comparaison à des programmes séquentiels équiva- lents ainsi que des performances acceptables par rapport à MPI. Ce mémoire démontre que l’usage des futures comme technique de partitionnement dynamique est faisable sur des multiprocesseurs à mémoire distribuée. / This master’s thesis presents an implementation of lazy task creation for distributed memory multiprocessors. It offers a subset of Message-Passing Interface’s functionality and allows parallelization of some problems that are hard to statically partition thanks to its dynamic partitionning and load balancing system. It is based on Multilisp, a Scheme dialect for parallel computing, and implements an MPI like interface on top of it. It offers a richer and more expressive language than C and simplify the work needed to developp programs similar to those in MPI. Finally, dynamic partitioning allows some programs that would be very hard to develop in MPI. Tests were made on a 16 cpus computer and on a 16 cpus cluster. The system gets good accelerations when compared to equivalent sequential programs and acceptable performances when compared to MPI. It shows that it is possible to use futures as a dynamic partitioning method on distributed memory multiprocessors.

Nous étudions dans cette thèse une matrice de processeurs élémentaires optoélectronique (parfois appelé rétine artificielle optoélectronique ou encore spa - pour smart pixel array) capable de réaliser plusieurs fonctions de traitement d'images bas niveau a cadence vidéo. Plus précisément, il s'agit d'une machine simd optoélectronique fonctionnant par recuit simule : chaque processeur élémentaire (pe ou sp - pour smart pixel) est l'équivalent d'un neurone dont l'état évolue en fonction de celui de ses voisins, et cela de façon probabiliste grâce a un générateur de nombres aléatoires optique base sur le phénomène de speckle laser. Dans une première version du processeur (circuit en silicium cmos 0,8 m), chaque pe est interconnecté de façon électronique a ces quatre plus proches voisins. Un montage base sur deux modulateurs spatiaux de lumière ferroélectriques et un hologramme de dammann permet d'étendre le voisinage d'interconnexion et de simuler des interconnexions intra-processeur optiques reconfigurables. Le montage servira a demontrer la détection du mouvement sur des séquences d'images a niveaux de gris ; toutefois, les performances restent médiocres (2 a 5 secondes par image). En fin de thèse est étudié un nouveau prototype base sur une matrice a entrées et sorties optiques (diodes p-i-n a puits quantiques multiples) réalisé en technologie hybride si/gaas par flip-chip bonding . Les performances du système sont considérablement améliorées (l'architecture comporte alors de véritables interconnexions optiques intra-processeur). L'étude théorique permet de conclure que l'utilisation d'une puce a entrées et sorties optiques rendrait le système a la fois compact (taille comparable avec celle d'un processeur pentium avec ses éléments de réfrigération) et extrêmement rapide (dizaines de milliers d'images a la seconde), ce qui en ferait un dispositif de choix pour les applications embarques de traitement d'images bas-niveau et temps réel.

Cette thèse propose un nouveau paradigme de représentation d'applications pour les machines virtuelles, capable d'abstraire l'architecture des systèmes informatiques. Les machines virtuelles actuelles reposent sur un modèle unique de représentation d'application qui abstrait les instructions des machines et sur un modèle d'exécution qui traduit le fonctionnement de ces instructions vers les machines cibles. S'ils sont capables de rendre les applications portables sur une vaste gamme de systèmes, ces deux modèles ne permettent pas en revanche d'exprimer la concurrence sur les instructions. Or, celle-ci est indispensable pour optimiser le traitement des applications selon les ressources disponibles de la plate-forme cible. Nous avons tout d'abord développé une représentation " universelle " d'applications pour machine virtuelle fondée sur la modélisation par graphe flux de données. Une application est ainsi modélisée par un graphe orienté dont les sommets sont des unités de calcul (les acteurs) et dont les arcs représentent le flux de données passant au travers de ces sommets. Chaque unité de calcul peut être traitée indépendamment des autres sur des ressources distinctes. La concurrence sur les instructions dans l'application est alors explicite. Exploiter ce nouveau formalisme de description d'applications nécessite de modifier les règles de programmation. A cette fin, nous avons introduit et défini le concept de " Représentation Canonique et Minimale " d'acteur. Il se fonde à la fois sur le langage de programmation orienté acteur CAL et sur les modèles d'abstraction d'instructions des machines virtuelles existantes. Notre contribution majeure qui intègre les deux nouvelles représentations proposées, est le développement d'une " Machine Virtuelle Universelle " (MVU) dont la spécificité est de gérer les mécanismes d'adaptation, d'optimisation et d'ordonnancement à partir de l'infrastructure de compilation Low-Level Virtual Machine. La pertinence de cette MVU est démontrée dans le contexte normatif du codage vidéo reconfigurable (RVC). En effet, MPEG RVC fournit des applications de référence de décodeurs conformes à la norme MPEG-4 partie 2 Simple Profile sous la forme de graphe flux de données. L'une des applications de cette thèse est la modélisation par graphe flux de données d'un décodeur conforme à la norme MPEG-4 partie 10 Constrained Baseline Profile qui est deux fois plus complexe que les applications de référence MPEG RVC. Les résultats expérimentaux montrent un gain en performance en exécution de deux pour des plates-formes dotées de deux cœurs par rapport à une exécution mono-cœur. Les optimisations développées aboutissent à un gain de 25% sur ces performances pour des temps de compilation diminués de moitié. Les travaux effectués démontrent le caractère opérationnel et universel de cette norme dont le cadre d'utilisation dépasse le domaine vidéo pour s'appliquer à d'autres domaine de traitement du signal (3D, son, photo...)