Auswahl der wissenschaftlichen Literatur zum Thema „Calcul parallèle sur cartes graphique“

De nombreux logiciels du commerce proposent de créer des modélisations en 3D d'objets ou de scènes à partir uniquement de photographies. Cependant les professionnels, notamment les archéologues et les architectes, ont un certain nombre de contraintes qui restreignent fortement le choix du logiciel, telles que des ressources financières limitées, des connaissances peu approfondies en photogrammétrie et en informatique, des impératifs qui limitent le temps d'acquisition et de traitement, et enfin des attentes précises en terme de qualité, de précision et de complétude de la modélisation. Le laboratoire MATIS a développé un ensemble d'outils libres, open source, qui permettent d'effectuer l'ensemble des étapes du traitement d'un chantier photogrammétrique et qui fournissent des modèles 3D très denses et précis grâce à la rigueur de l'approche photogrammétrique ; ils représentent donc une solution intéressante pour ces professionnels du point de vue algorithmique.Cependant ils ont été développés pour des applications de recherche et sont donc peu ergonomiques pour le public non photogrammètre et non informaticien. C'est pourquoi une interface graphique est en cours de développement afin de fournir un accès simplifié et unifié à ces outils, notamment aux architectes et aux archéologues. Grâce à l'interface, l'utilisateur peut manipuler les images d'un même chantier et contrôler chaque étape du traitement qui comprend : le calcul automatique de points homologues entre les images, l'estimation des poses de la caméra et le calcul des modèles 3D. Les résultats peuvent être convertis en cartes de profondeur ombrées ou en nuages denses de points 3D (au format standard ply), et peuvent être affichés directement par l'interface. Pour offrir la possibilité de traiter des chantiers suffisamment variés, tout en masquant la complexité du paramétrage, la démarche retenue est de présenter à l'utilisateur un accès par grande famille de prises de vue, par exemple : chantier convergent, relevé de façades, chantier aérien sub-vertical, modélisation d'intérieur. . . Une attention particulière est apportée à la qualité de la documentation et à la portabilité du produit sur les principaux types d'ordinateur grand public (Linux, Mac et Windows). Cette interface, bien que non finalisée, permet déjà d'effectuer l'intégralité du traitement de chantiers de type convergent et est disponible en ligne. Des utilisateurs issus des différentes communautés de professionnels ciblées (archéologie, architecture, géologie, photogrammétrie architecturale) l'ont déjà testée et l'interface est régulièrement mise à jour afin de l'adapter aux remarques et demandes de ces testeurs.

L'arrivée des supercalculateurs post-petascales and exascales offre la perspective d'accélérer la résolution des problèmes d'ingénierie et aux modélisations hautement complexes. Cependant, ces futurs systèmes posent des problèmes aux informaticiens pour construire de telles machines. De nombreux problèmes doivent être résolus comme la tolérance aux pannes, la consommation énergétique et la programmation de ces systèmes complexes composés de milliard de coeurs.Dans cette thèse, nous nous sommes concentrés sur l'aspect programmation et proposons un paradigme de programmation multi-niveaux composé de trois niveaux. Pour le bas niveau, un paradigme data parallèle est proposé pour programmer les processeurs à nombreux coeurs pour sa focalisation sur la distribution et le mouvement des données. Nous avons implémenté et évalué le produit matrice vecteur creux suivant différents formats de matrice creuse sur un GPU pour illustrer ce point. Pour le niveau intermédiaire, nous proposons un paradigme à passage de messages de manière à optimiser les communications inter-processeurs et inter-noeuds. Pour le haut niveau, un paradigme de description de graphe est proposé pour programmer et gérer le parallélisme entre les noeuds.Avec une méthode d'inversion matricielle dense développée en YML, nous soulignons l'intérêt des graphes pour la réduction du temps à la solution et pour le support des communications asynchrones de facon transparente. L'intérêt des graphes est également démontré pour les optimisations d'entrées/sorties et leur support dans un modèle de programmation. Nous concluons finalement en analysant une telle proposition de paradigme de programmation pour les machines exascale et présentons la direction des travaux futurs
The coming of post-petscale and exascale supercomputers offers the perspective to accelerate the solving of engineering problems and to highly complex modeling. However, these future systems challenge computer scientists to built such machines. Many issues must be faced such as fault-tolerance, energy consumption and the programming of these complex systems composed of billion cores.In this thesis, we have focused on the programming aspect and propose a multi-level programming paradigm composed of three levels. For the low level, a data parallel paradigm is proposed to program many-cores processors for its focus on data mapping and movements. We have implemented and evaluated the SpMV with various sparse matrix formats on GPU to illustrate this point. For the intermediate level, we propose a message passing paradigm in order to optimize inter-sockets and inter-nodes communications. For the high level, a graph description paradigm is proposed to program and manage the parallelism between nodes.With a dense matrix inversion method developed in YML, we underline the interest of graph for the Time-To-Solution reduction and for the support of asynchronous communications in a transparent way. The interest of graph is also demonstrated for I/O optimizations and for their direct support into the programming model. We finally conclude by analyzing a such proposition of programming paradigm for exascale machines and outlines the future work direction

La bioinformatique nécessite l'analyse de grandes quantités de données. Avec l'apparition de nouvelles technologies permettant un séquençage à haut débit à bas coût, la puissance de calcul requise pour traiter les données a énormément augmenté.. Cette thèse examine la possibilité d'utiliser les processeurs graphiques (GPU) pour des applications de bioinformatique. Dans un premier temps, ce travail s'intéresse au calcul des structures secondaires d'ARN. Ce problème est en général calculé par programmation dynamique, avec un algorithme qui pose de sérieux problèmes pour un code GPU. Nous introduisons une nouvelle implémentation tuilée qui fait apparaitre une bonne localité mémoire, permettant ainsi un programme GPU très efficace. Cette modification permet également de vectoriser le code CPU et donc de faire une comparaison honnête des performances entre GPU et CPU. Dans un deuxième temps, ce travail aborde le problème d'alignements de séquences. Nous présentons une parallélisation GPU d'une méthode utilisant une indexation par graines. L' implémentation sur GPU n'étant pas efficace, nous nous tournons vers le développement d'une version CPU. Notre contribution principale est le développement d'un nouvel algorithme éliminant rapidement les nombreux alignements potentiels, basé sur le précalcul de portions de la matrice de programmation dynamique. Ce nouvel algorithme a conduit au développement d'un nouveau programme d'alignement très efficace. Notre travail fournit l'exemple de deux problèmes différents dont seulement un a pu être efficacement parallélisé sur GPU. Ces deux expériences nous permettent d'évaluer l'efficacité des GPU et leur place en bioinformatique.

Rechercher les similarités entre séquences est une opération fondamentale en bioinformatique, que cela soit pour étudier des questions biologiques ou bien pour traiter les données issues de séquenceurs haut-débit. Il y a un vrai besoin d'algorithmes capables de traiter des millions de séquences rapidement. Pour trouver des similarités approchées, on peut tout d'abord considérer de petits mots exacts présents dans les deux séquences, les graines, puis essayer d'étendre les similarités aux voisinages de ces graines. Cette thèse se focalise sur la deuxième étape des heuristiques à base de graines : comment récupérer et comparer efficacement ces voisinages des graines, pour ne garder que les bons candidats ? La thèse explore différentes solutions adaptées aux processeurs massivement multicoeurs: aujourd'hui, les GPUs sont en train de démocratiser le calcul parallèle et préparent les processeurs de demain. La thèse propose des approches directes (extension de l'algorithme bit-parallèle de Wu-Manber, publiée à PBC 2011, et recherche dichotomique) ou bien avec un index supplémentaire (utilisation de fonctions de hash parfaites). Chaque solution a été pensée pour tirer le meilleur profit des architectures avec un fort parallélisme à grain fin, en utilisant des calculs intensifs mais homogènes. Toutes les méthodes proposées ont été implémentés en OpenCL, et comparées sur leur temps d'exécution. La thèse se termine par un prototype de read mapper parallèle, MAROSE, utilisant ces concepts. Dans certaines situations, MAROSE est plus rapide que les solutions existantes avec une sensibilité similaire.

La théorie de la viabilité propose des outils permettant de contrôler un système dynamique afin de le maintenir dans un domaine de contraintes. Le concept central de cette théorie est le noyau de viabilité, qui est l’ensemble des états initiaux à partir desquels il existe au moins une trajectoire contrôlée restant dans le domaine de contraintes. Cependant, le temps et l’espace nécessaires au calcul du noyau de viabilité augmentent exponentiellement avec le nombre de dimensions du problème considéré. C’est la malédiction de la dimension. Elle est d’autant plus présente dans le cas de systèmes incorporant des incertitudes. Dans ce cas-là, le noyau de viabilité devient l’ensemble des états pour lesquels il existe une stratégie de contrôle permettant de rester dans le domaine de contraintes avec au moins une certaine probabilité jusqu’à l’horizon de temps donné. L’objectif de cette thèse est d’étudier et de développer des approches afin de combattre cette malédiction de la dimension. Pour ce faire, nous avons proposé deux axes de recherche : la parallélisation des calculs et l’utilisation de la théorie de la fiabilité. Les résultats sont illustrés par plusieurs applications. Le premier axe explore l’utilisation de calcul parallèle sur carte graphique. La version du programme utilisant la carte graphique est jusqu’à 20 fois plus rapide que la version séquentielle, traitant des problèmes jusqu’en dimension 7. Outre ces gains en temps de calcul, nos travaux montrent que la majeure partie des ressources est utilisée pour le calcul des probabilités de transition du système. Cette observation fait le lien avec le deuxième axe de recherche qui propose un algorithme calculant une approximation de noyaux de viabilité stochastiques utilisant des méthodes fiabilistes calculant les probabilités de transition. L’espace-mémoire requis par cet algorithme est une fonction linéaire du nombre d’états de la grille utilisée, contrairement à l’espace-mémoire requis par l’algorithme de programmation dynamique classique qui dépend quadratiquement du nombre d’états. Ces approches permettent d’envisager l’application de la théorie de la viabilité à des systèmes de plus grande dimension. Ainsi nous l’avons appliquée à un modèle de dynamique du phosphore dans le cadre de la gestion de l’eutrophisation des lacs, préalablement calibré sur les données du lac du Bourget. De plus, les liens entre fiabilité et viabilité sont mis en valeur avec une application du calcul de noyau de viabilité stochastique, autrement appelé noyau de fiabilité, en conception fiable dans le cas d’une poutre corrodée
Viability theory provides tools to maintain a dynamical system in a constraint domain. The main concept of this theory is the viability kernel, which is the set of initial states from which there is at least one controlled trajectory remaining in the constraint domain. However, the time and space needed to calculate the viability kernel increases exponentially with the number of dimensions of the problem. This issue is known as “the curse of dimensionality”. This curse is even more present when applying the viability theory to uncertain systems. In this case, the viability kernel is the set of states for which there is at least a control strategy to stay in the constraint domain with some probability until the time horizon. The objective of this thesis is to study and develop approaches to beat back the curse of dimensionality. We propose two lines of research: the parallel computing and the use of reliability theory tools. The results are illustrated by several applications. The first line explores the use of parallel computing on graphics card. The version of the program using the graphics card is up to 20 times faster than the sequential version, dealing with problems until dimension 7. In addition to the gains in calculation time, our work shows that the majority of the resources is used to the calculation of transition probabilities. This observation makes the link with the second line of research which proposes an algorithm calculating a stochastic approximation of viability kernels by using reliability methods in order to compute the transition probabilities. The memory space required by this algorithm is a linear function of the number of states of the grid, unlike the memory space required by conventional dynamic programming algorithm which quadratically depends on the number of states. These approaches may enable the use of the viability theory in the case of high-dimension systems. So we applied it to a phosphorus dynamics for the management of Lake Bourget eutrophication, previously calibrated from experimental data. In addition the relationship between reliability and viability is highlighted with an application of stochastic viability kernel computation, otherwise known as reliability kernel, in reliable design in the case of a corroded beam

La reconstruction tomographique à partir de données de projections est un problème inverse largement utilisé en imagerie médicale et de façon plus modeste pour le contrôle nondestructif. Avec un nombre suffisant de projections, les algorithmes analytiques permettentdes reconstructions rapides et précises. Toutefois, dans le cas d’un faible nombre de vues(imagerie faible dose) et/ou d’angle limité (contraintes spécifiques liées à l’installation), lesdonnées disponibles pour l’inversion ne sont pas complètes, le mauvais conditionnementdu problème s’accentue, et les résultats montrent des artefacts importants. Pour aborderces situations, une approche alternative consiste à discrétiser le problème de reconstruction,et à utiliser des algorithmes itératifs ou une formulation statistique du problème afinde calculer une estimation de l’objet inconnu. Ces méthodes sont classiquement basées surune discrétisation du volume en un ensemble de voxels, et fournissent des cartes 3D de ladensité de l’objet étudié. Les temps de calcul et la ressource mémoire de ces méthodesitératives sont leurs principaux points faibles. Par ailleurs, quelle que soit l’application, lesvolumes sont ensuite segmentés pour une analyse quantitative. Devant le large éventaild’outils de segmentation existant, basés sur différentes interprétations des contours et defonctionnelles à minimiser, les choix sont multiples et les résultats en dépendent.Ce travail de thèse présente une nouvelle approche de reconstruction simultanée àla segmentation des différents matériaux qui composent le volume. Le processus dereconstruction n’est plus basé sur une grille régulière de pixels (resp. voxels), mais sur unmaillage composé de triangles (resp. tétraèdres) non réguliers qui s’adaptent à la formede l’objet. Après une phase d’initialisation, la méthode se décompose en trois étapesprincipales que sont la reconstruction, la segmentation et l’adaptation du maillage, quialternent de façon itérative jusqu’à convergence. Des algorithmes itératifs de reconstructioncommunément utilisés avec une représentation conventionnelle de l’image ont étéadaptés et optimisés pour être exécutés sur des grilles irrégulières composées d’élémentstriangulaires ou tétraédriques. Pour l’étape de segmentation, deux méthodes basées surune approche paramétrique (snake) et l’autre sur une approche géométrique (level set)ont été mises en oeuvre afin de considérer des objets de différentes natures (mono- etmulti- matériaux). L’adaptation du maillage au contenu de l’image estimée est basée surles contours segmentés précédemment, pour affiner la maille au niveau des détails del’objet et la rendre plus grossière dans les zones contenant peu d’information. En finde processus, le résultat est une image classique de reconstruction tomographique enniveaux de gris, mais dont la représentation par un maillage adapté au contenu proposeidirectement une segmentation associée. Les résultats montrent que la partie adaptative dela méthode permet de représenter efficacement les objets et conduit à diminuer drastiquementla mémoire nécessaire au stockage. Dans ce contexte, une version 2D du calcul desopérateurs de reconstruction sur une architecture parallèle type GPU montre la faisabilitédu processus dans son ensemble. Une version optimisée des opérateurs 3D permet descalculs encore plus efficaces
Tomography reconstruction from projections data is an inverse problem widely used inthe medical imaging field. With sufficiently large number of projections over the requiredangle, the FBP (filtered backprojection) algorithms allow fast and accurate reconstructions.However in the cases of limited views (lose dose imaging) and/or limited angle (specificconstrains of the setup), the data available for inversion are not complete, the problembecomes more ill-conditioned, and the results show significant artifacts. In these situations,an alternative approach of reconstruction, based on a discrete model of the problem,consists in using an iterative algorithm or a statistical modelisation of the problem to computean estimate of the unknown object. These methods are classicaly based on a volumediscretization into a set of voxels and provide 3D maps of densities. Computation time andmemory storage are their main disadvantages. Moreover, whatever the application, thevolumes are segmented for a quantitative analysis. Numerous methods of segmentationwith different interpretations of the contours and various minimized energy functionalare offered, and the results can depend on their use.This thesis presents a novel approach of tomographic reconstruction simultaneouslyto segmentation of the different materials of the object. The process of reconstruction isno more based on a regular grid of pixels (resp. voxel) but on a mesh composed of nonregular triangles (resp. tetraedra) adapted to the shape of the studied object. After aninitialization step, the method runs into three main steps: reconstruction, segmentationand adaptation of the mesh, that iteratively alternate until convergence. Iterative algorithmsof reconstruction used in a conventionnal way have been adapted and optimizedto be performed on irregular grids of triangular or tetraedric elements. For segmentation,two methods, one based on a parametric approach (snake) and the other on a geometricapproach (level set) have been implemented to consider mono and multi materials objects.The adaptation of the mesh to the content of the estimated image is based on the previoussegmented contours that makes the mesh progressively coarse from the edges to thelimits of the domain of reconstruction. At the end of the process, the result is a classicaltomographic image in gray levels, but whose representation by an adaptive mesh toits content provide a correspoonding segmentation. The results show that the methodprovides reliable reconstruction and leads to drastically decrease the memory storage. Inthis context, the operators of projection have been implemented on parallel archituecturecalled GPU. A first 2D version shows the feasability of the full process, and an optimizedversion of the 3D operators provides more efficent compoutations