Dissertations / Theses: 'Algorithmes GPU'

1

Ballage, Marion. "Algorithmes de résolution rapide de problèmes mécaniques sur GPU." Thesis, Toulouse 3, 2017. http://www.theses.fr/2017TOU30122/document.

Full text

Abstract:

Dans le contexte de l'analyse numérique en calcul de structures, la génération de maillages conformes sur des modèles à géométrie complexe conduit à des tailles de modèles importantes, et amène à imaginer de nouvelles approches éléments finis. Le temps de génération d'un maillage est directement lié à la complexité de la géométrie, augmentant ainsi considérablement le temps de calcul global. Les processeurs graphiques (GPU) offrent de nouvelles opportunités pour le calcul en temps réel. L'architecture grille des GPU a été utilisée afin d'implémenter une méthode éléments finis sur maillage cartésien. Ce maillage est particulièrement adapté à la parallélisation souhaitée par les processeurs graphiques et permet un gain de temps important par rapport à un maillage conforme à la géométrie. Les formulations de la méthode des éléments finis ainsi que de la méthode des éléments finis étendue ont été reprises afin d'être adaptées à notre méthode. La méthode des éléments finis étendus permet de prendre en compte la géométrie et les interfaces à travers un choix adéquat de fonctions d'enrichissement. Cette méthode discrétise par exemple sans mailler explicitement les fissures, et évite surtout de remailler au cours de leur propagation. Des adaptations de cette méthode sont faites afin de ne pas avoir besoin d'un maillage conforme à la géométrie. La géométrie est définie implicitement par une fonction surfaces de niveau, ce qui permet une bonne approximation de la géométrie et des conditions aux limites sans pour autant s'appuyer sur un maillage conforme. La géométrie est représentée par une fonction surfaces de niveau que nous appelons la densité. La densité est supérieure à 0.5 à l'intérieur du domaine de calcul et inférieure à 0.5 à l'extérieur. Cette fonction densité, définie par ses valeurs aux points noeuds du maillage, est interpolée à l'intérieur de chaque élément. Une méthode d'intégration adaptée à cette représentation géométrique est proposée. En effet, certains éléments sont coupés par la fonction surfaces de niveau et l'intégration de la matrice de raideur ne doit se faire que sur la partie pleine de l'élément. La méthode de quadrature de Gauss qui permet d'intégrer des polynômes de manière exacte n'est plus adaptée. Nous proposons d'utiliser une méthode de quadrature avec des points d'intégration répartis sur une grille régulière et dense. L'intégration peut s'avérer coûteuse en temps de calcul, c'est pour cette raison que nous proposons une technique d'apprentissage donnant la matrice élémentaire de rigidité en fonction des valeurs de la fonction surfaces de niveau aux sommets de l'élément considéré. Cette méthode d'apprentissage permet de grandes améliorations du temps de calcul des matrices élémentaires. Les résultats obtenus après analyse par la méthode des éléments finis standard ou par la méthode des éléments finis sur maillage cartésien ont une taille qui peut croître énormément selon la complexité des modèles, ainsi que la précision des schémas de résolution. Dans un contexte de programmation sur processeurs graphiques, où la mémoire est limitée, il est intéressant d'arriver à compresser ces données. Nous nous sommes intéressés à la compression des modèles et des résultats éléments finis par la transformée en ondelettes. La compression mise en place aidera aussi pour les problèmes de stockage en réduisant la taille des fichiers générés, et pour la visualisation des données
Generating a conformal mesh on complex geometries leads to important model size of structural finite element simulations. The meshing time is directly linked to the geometry complexity and can contribute significantly to the total turnaround time. Graphics processing units (GPUs) are highly parallel programmable processors, delivering real performance gains on computationally complex, large problems. GPUs are used to implement a new finite element method on a Cartesian mesh. A Cartesian mesh is well adapted to the parallelism needed by GPUs and reduces the meshing time to almost zero. The novel method relies on the finite element method and the extended finite element formulation. The extended finite element method was introduced in the field of fracture mechanics. It consists in enriching the basis functions to take care of the geometry and the interface. This method doesn't need a conformal mesh to represent cracks and avoids refining during their propagation. Our method is based on the extended finite element method, with a geometry implicitly defined, wich allows for a good approximation of the geometry and boundary conditions without a conformal mesh.To represent the model on a Cartesian grid, we use a level set representing a density. This density is greater than 0.5 inside the domain and less than 0.5 outside. It takes 0.5 on the boundary. A new integration technique is proposed, adapted to the geometrical representation. For the element cut by the levet set, only the part full of material has to be integrated. The Gauss quadrature is no longer adapted. We introduce a quadrature method with integration points on a cartesian dense grid.In order to reduce the computational effort, a learning approach is then considered to form the elementary stiffness matrices as function of density values on the vertices of the elements. This learning method reduces the stiffness matrices time computation. Results obtained after analysis by finite element method or the novel finite element method can have important storage size, dependant of the model complexity and the resolution scheme exactitude. Due to the limited direct memory of graphics processing units, the data results are compressed. We compress the model and the element finite results with a wavelet transform. The compression will help for storage issue and also for data visualization

APA, Harvard, Vancouver, ISO, and other styles

2

Luong, Thé Van. "Métaheuristiques parallèles sur GPU." Thesis, Lille 1, 2011. http://www.theses.fr/2011LIL10058/document.

Full text

Abstract:

Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leurdéploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers
Real-world optimization problems are often complex and NP-hard. Their modeling is continuously evolving in terms of constraints and objectives, and their resolution is CPU time-consuming. Although near-optimal algorithms such as metaheuristics (generic heuristics) make it possible to reduce the temporal complexity of their resolution, they fail to tackle large problems satisfactorily. Over the last decades, parallel computing has been revealed as an unavoidable way to deal with large problem instances of difficult optimization problems. The design and implementation of parallel metaheuristics are strongly influenced by the computing platform. Nowadays, GPU computing has recently been revealed effective to deal with time-intensive problems. This new emerging technology is believed to be extremely useful to speed up many complex algorithms. One of the major issues for metaheuristics is to rethink existing parallel models and programming paradigms to allow their deployment on GPU accelerators. Generally speaking, the major issues we have to deal with are: the distribution of data processing between CPU and GPU, the thread synchronization, the optimization of data transfer between the different memories, the memory capacity constraints, etc. The contribution of this thesis is to deal with such issues for the redesign of parallel models of metaheuristics to allow solving of large scale optimization problems on GPU architectures. Our objective is to rethink the existing parallel models and to enable their deployment on GPUs. Thereby, we propose in this document a new generic guideline for building efficient parallel metaheuristics on GPU. Our challenge is to come out with the GPU-based design of the whole hierarchy of parallel models.In this purpose, very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of solutions to GPU threadsor memory management. These approaches have been exhaustively experimented using five optimization problems and four GPU configurations. Compared to a CPU-based execution, experiments report up to 80-fold acceleration for large combinatorial problems and up to 2000-fold speed-up for a continuous problem. The different works related to this thesis have been accepted in a dozen of publications, including the IEEE Transactions on Computers journal

APA, Harvard, Vancouver, ISO, and other styles

3

Viard, Thomas. "Algorithmes de visualisation des incertitudes en géomodélisation sur GPU." Thesis, Vandoeuvre-les-Nancy, INPL, 2010. http://www.theses.fr/2010INPL042N/document.

Full text

Abstract:

En géosciences, la majeure partie du sous-sol est inaccessible à toute observation directe. Seules des informations parcellaires ou imprécises sont donc disponibles lors de la construction ou de la mise à jour de modèles géologiques ; de ce fait, les incertitudes jouent un rôle fondamental en géomodélisation. La théorie des problèmes inverses et les méthodes de simulations stochastiques fournissent un cadre théorique permettant de générer un ensemble de représentations plausibles du sous-sol, également nommées réalisations. En pratique, la forte cardinalité de l'ensemble des réalisations limite significativement tout traitement ou interprétation sur le modèle géologique.L'objectif de cette thèse est de fournir au géologue des algorithmes de visualisation permettant d'explorer, d'analyser et de communiquer les incertitudes spatiales associées à de larges ensembles de réalisations. Nos contributions sont les suivantes : (1) Nous proposons un ensemble de techniques dédiées à la visualisation des incertitudes pétrophysiques. Ces techniques reposent sur une programmation sur carte graphique (GPU) et utilisent une architecture garantissant leur interopérabilité ; (2) Nous proposons deux techniques dédiées à la visualisation des incertitudes structurales, traitant aussi bien les incertitudes géométriques que les incertitudes topologiques (existence de la surface ou interactions avec d'autres surfaces) ; (3) Nous évaluons la qualité des algorithmes de visualisation des incertitudes par le biais de deux études sur utilisateurs, portant respectivement sur la perception des méthodes statiques et par animation. Ces études apportent un éclairage nouveau sur la manière selon laquelle l'incertitude doit être représentée
Most of the subsurface is inaccessible to direct observation in geosciences. Consequently, only local or imprecise data are available when building or updating a geological model; uncertainties are therefore central to geomodeling. The inverse problem theory and the stochastic simulation methods provide a framework for the generation of large sets of likely representations of the subsurface, also termed realizations. In practice, however, the size of the set of realizations severely impacts further interpretation or processing of the geological model.This thesis aims at providing visualization algorithms to expert geologists that allow them to explore, analyze and communicate on spatial uncertainties associated to large sets of realizations. Our contributions are: (1) We propose a set of techniques dedicated to petrophysical uncertainty visualization, based on a GPU programming approach that maintains their interoperability; (2) We propose two techniques dedicated to structural uncertainty visualization that can handle both geometrical and topological uncertainties (e.g., the existence of the surface or its relationships with other surfaces); (3) We assess the quality of our uncertainty visualization algorithms through two user studies, which respectively focus on the perception of static and animated methods. These studies bring new elements on how uncertainty should be represented

APA, Harvard, Vancouver, ISO, and other styles

4

Lefèbvre, Matthieu. "Algorithmes sur GPU pour la simulation numérique en mécanique des fluides." Paris 13, 2012. http://scbd-sto.univ-paris13.fr/intranet/edgalilee_th_2012_lefebvre.pdf.

Full text

Abstract:

La simulation numérique en mécanique des fluides nécessite souvent une importante puissance de calcul. Pour accélérer ces simulations l’utilisation de GPU est envisagée. Cette thèse s’intéresse tout d’abord à l’étude d’algorithmes de mécanique des fluides numérique en maillage structuré. La structuration du maillage amène un rangement mémoire naturellement convenable pour effectuer des simulations sur GPU. Ceci permet de dégager des principes d’utilisation sans avoir à considérer le bruit occasionné par la définition d’une structure de données spécifique. Par la suite nous nous concentrons sur les algorithmes de mécanique des fluides numériques sur maillage non structuré et trois stratégies algorithmiques sont présentées. La première de ces techniques est une réorganisation visant à rendre les données consécutives en mémoire, au prix d’une copie des données coûteuse à la fois en temps et en mémoire. Une deuxième technique résultant en un partitionnement fin du domaine de calcul est développée, elle permet d’utiliser les mémoires cache des GPU modernes de manière plus efficace. La troisième de ces techniques est le raffinement générique. Le maillage initial est composé d’éléments grossiers raffinés de façon identique. Cette algorithme permet d’accéder aux données de façon consécutive et apporte des performances accrues
Numerical simulations in fluid mechanics require tremendous computational power ; GPU computing is one of the newest approaches to accelerate such simulations. On one hand, this thesis studies the case of fluid mechanics algorithms on structured meshes. The mesh structuration naturally brings well suited memory arrangements and allows to reach guidelines when using GPUs for numerical simulations. On the other hand, we examine the case of fluid mechanics on unstructured meshes with the help of three different algorithmic strategies. The first of these technique is a reorganisation to produce consecutive data accesses, but at the cost of expensive data copies, both in time and in memory. The second technique, a cell partitioning approach, is developed and allows to extensively use modern GPUs’ cache memories. The third technique consists on a generic refinement. The initial mesh is made of coarse elements refined in the exact same way in order to produce consecutive memory accesses. This approach brings significant performance improvements for fluid mechanics simulations on unstructured meshes

APA, Harvard, Vancouver, ISO, and other styles

5

Marin, Manuel. "GPU-enhanced power flow analysis." Thesis, Perpignan, 2015. http://www.theses.fr/2015PERP0041.

Full text

Abstract:

Cette thèse propose un large éventail d'approches afin d'améliorer différents aspects de l'analyse des flux de puissance avec comme fils conducteur l'utilisation du processeurs graphiques (GPU). Si les GPU ont rapidement prouvés leurs efficacités sur des applications régulières pour lesquelles le parallélisme de données était facilement exploitable, il en est tout autrement pour les applications dites irrégulières. Ceci est précisément le cas de la plupart des algorithmes d'analyse de flux de puissance. Pour ce travail, nous nous inscrivons dans cette problématique d'optimisation de l'analyse de flux de puissance à l'aide de coprocesseur de type GPU. L'intérêt est double. Il étend le domaine d'application des GPU à une nouvelle classe de problème et/ou d'algorithme en proposant des solutions originales. Il permet aussi à l'analyse des flux de puissance de rester pertinent dans un contexte de changements continus dans les systèmes énergétiques, et ainsi d'en faciliter leur évolution. Nos principales contributions liées à la programmation sur GPU sont: (i) l'analyse des différentes méthodes de parcours d'arbre pour apporter une réponse au problème de la régularité par rapport à l'équilibrage de charge ; (ii) l'analyse de l'impact du format de représentation sur la performance des implémentations d'arithmétique floue. Nos contributions à l'analyse des flux de puissance sont les suivantes: (ii) une nouvelle méthode pour l'évaluation de l'incertitude dans l'analyse des flux de puissance ; (ii) une nouvelle méthode de point fixe pour l'analyse des flux de puissance, problème que l'on qualifie d'intrinsèquement parallèle
This thesis addresses the utilization of Graphics Processing Units (GPUs) for improving the Power Flow (PF) analysis of modern power systems. Currently, GPUs are challenged by applications exhibiting an irregular computational pattern, as is the case of most known methods for PF analysis. At the same time, the PF analysis needs to be improved in order to cope with new requirements of efficiency and accuracy coming from the Smart Grid concept. The relevance of GPU-enhanced PF analysis is twofold. On one hand, it expands the application domain of GPU to a new class of problems. On the other hand, it consistently increases the computational capacity available for power system operation and design. The present work attempts to achieve that in two complementary ways: (i) by developing novel GPU programming strategies for available PF algorithms, and (ii) by proposing novel PF analysis methods that can exploit the numerous features present in GPU architectures. Specific contributions on GPU computing include: (i) a comparison of two programming paradigms, namely regularity and load-balancing, for implementing the so-called treefix operations; (ii) a study of the impact of the representation format over performance and accuracy, for fuzzy interval algebraic operations; and (iii) the utilization of architecture-specific design, as a novel strategy to improve performance scalability of applications. Contributions on PF analysis include: (i) the design and evaluation of a novel method for the uncertainty assessment, based on the fuzzy interval approach; and (ii) the development of an intrinsically parallel method for PF analysis, which is not affected by the Amdahl's law

APA, Harvard, Vancouver, ISO, and other styles

6

Van, Luong Thé. "Métaheuristiques parallèles sur GPU." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2011. http://tel.archives-ouvertes.fr/tel-00638820.

Full text

Abstract:

Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leur déploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers.

APA, Harvard, Vancouver, ISO, and other styles

7

Buatois, Luc. "Algorithmes sur GPU de visualisation et de calcul pour des maillages non-structurés." Phd thesis, Institut National Polytechnique de Lorraine - INPL, 2008. http://tel.archives-ouvertes.fr/tel-00331935.

Full text

Abstract:

Les algorithmes les plus récents de traitement numérique de la géométrie ou bien encore de simulation numérique de type CFD (Computational Fluid Dynamics) utilisent à présent de nouveaux types de grilles composées de polyèdres arbitraires, autrement dit des grilles fortement non-structurées. Dans le cas de simulations de type CFD, ces grilles peuvent servir de support à des champs scalaires ou vectoriels qui représentent des grandeurs physiques (par exemple : densité, porosité, perméabilité). La problématique de cette thèse concerne la définition de nouveaux outils de visualisation et de calcul sur de telles grilles. Pour la visualisation, cela pose `a la fois le problème du stockage et de l'adaptativité des algorithmes `a une géométrie et une topologie variables. Pour le calcul, cela pose le problème de la résolution de grands systèmes linéaires creux non-structurés. Pour aborder ces problèmes, l'augmentation incessante ces dernières années de la puissance de calcul parallèle des processeurs graphiques nous fournit de nouveaux outils. Toutefois, l'utilisation de ces GPU nécessite de définir de nouveaux algorithmes adaptés aux modèles de programmation parallèle qui leur sont spécifiques. Nos contributions sont les suivantes : (1) Une méthode générique de visualisation tirant partie de la puissance de calcul des GPU pour extraire des isosurfaces à partir de grandes grilles fortement nonstructurées. (2) Une méthode de classification de cellules qui permet d'accélérer l'extraction d'isosurfaces grâce à une pré-sélection des seules cellules intersectées. (3) Un algorithme d'interpolation temporelle d'isosurfaces. Celui-ci permet de visualiser de manière continue dans le temps l'évolution d'isosurfaces. (4) Un algorithme massivement parallèle de résolution de grands systèmes linéaires non-structurés creux sur le GPU. L'originalité de celui-ci concerne son adaptation à des matrices de motif arbitraire, ce qui le rend applicable `a n'importe quel système creux, dont ceux issus de maillages fortement non-structurés.

APA, Harvard, Vancouver, ISO, and other styles

8

Chakroun, Imen. "Algorithmes Branch and Bound parallèles hétérogènes pour environnements multi-coeurs et multi-GPU." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2013. http://tel.archives-ouvertes.fr/tel-00841965.

Full text

Abstract:

Les algorithmes Branch and Bound (B&B) sont attractifs pour la résolution exacte de problèmes d'optimisation combinatoire (POC) par exploration d'un espace de recherche arborescent. Néanmoins, ces algorithmes sont très gourmands en temps de calcul pour des instances de problèmes de grande taille (exemple : benchmarks de Taillard pour FSP) même en utilisant le calcul sur grilles informatiques [Mezmaz et al., IEEE IPDPS'2007]. Le calcul massivement parallèle fourni à travers les plates-formes de calcul hétérogènes d'aujourd'hui [TOP500 ] est requis pour traiter effi cacement de telles instances. Le dé fi est alors d'exploiter tous les niveaux de parallélisme sous-jacents et donc de repenser en conséquence les modèles parallèles des algorithmes B&B. Dans cette thèse, nous nous attachons à revisiter la conception et l'implémentation des ces algorithmes pour la résolution de POC de grande taille sur (larges) plates-formes de calcul multi-coeurs et multi-GPUs. Le problème d'ordonnancement Flow-Shop (FSP) est considéré comme étude de cas. Une étude expérimentale préliminaire sur quelques grandes instances du FSP a révélé que l'arbre de recherche est hautement irrégulier (en forme et en taille) et très large (milliards de milliards de noeuds), et que l'opérateur d'évaluation des bornes est exorbitant en temps de calcul (environ 97% du temps de B&B). Par conséquent, notre première contribution est de proposer une approche GPU avec un seul coeur CPU (GB&B) dans laquelle seul l'opérateur d'évaluation est exécuté sur GPU. L'approche traite deux dé fis: la divergence de threads et l'optimisation de la gestion de la mémoire hiérarchique du GPU. Comparée à une version séquentielle, des accélérations allant jusqu'à ( 100) sont obtenues sur Nvidia Tesla C2050. L'analyse des performances de GB&B a montré que le surcoût induit par le transfert des données entre le CPU et le GPU est élevé. Par conséquent, l'objectif de la deuxième contribution est d'étendre l'approche (LL-GB&B) a fin de minimiser la latence de communication CPU-GPU. Cet objectif est réalisé grâce à une parallélisation à grain fin sur GPU des opérateurs de séparation et d'élagage. Le défi majeur relevé ici est la divergence de threads qui est due à la nature fortement irrégulière citée ci-dessus de l'arbre exploré. Comparée à une exécution séquentielle, LL-GB&B permet d'atteindre des accélérations allant jusqu'à ( 160) pour les plus grandes instances. La troisième contribution consiste à étudier l'utilisation combinée des GPUs avec les processeurs multi-coeurs. Deux scénarios ont été explorés conduisant à deux approches: une concurrente (RLL-GB&B) et une coopérative (PLL-GB&B). Dans le premier cas, le processus d'exploration est eff ectué simultanément par le GPU et les coeurs du CPU. Dans l'approche coopérative, les coeurs du CPU préparent et transfèrent les sous-problèmes en utilisant le streaming CUDA tandis que le GPU eff ectue l'exploration. L'utilisation combinée du multi-coeur et du GPU a montré que l'utilisation de RLL-GB&B n'est pas bénéfi que et que PLL-GB&B permet une amélioration allant jusqu'à (36%) par rapport à LL-GB&B. Sachant que récemment des grilles de calcul comme Grid5000 (certains sites) ont été équipées avec des GPU, la quatrième contribution de cette thèse traite de la combinaison du calcul sur GPU et multi-coeur avec le calcul distribué à grande échelle. Pour ce faire, les diff érentes approches proposées ont été réunies dans un méta-algorithme hétérofigène qui sélectionne automatiquement l'algorithme à déployer en fonction de la con figuration matérielle cible. Ce méta-algorithme est couplé avec l'approche B&B@Grid proposée dans [Mezmaz et al., IEEE IPDPS'2007]. B&B@Grid répartit les unités de travail (sous-espaces de recherche codés par des intervalles) entre les noeuds de la grille tandis que le méta-algorithme choisit et déploie localement un algorithme de B&B parallèle sur les intervalles reçus. L'approche combinée nous a permis de résoudre à l'optimalité et e fficacement les instances (20 20) de Taillard.

APA, Harvard, Vancouver, ISO, and other styles

9

Mansouri, Abdelkhalek. "Generic heuristics on GPU to superpixel segmentation and application to optical flow estimation." Thesis, Bourgogne Franche-Comté, 2020. http://www.theses.fr/2020UBFCA012.

Full text

Abstract:

Déterminer des clusters dans des nuages de points et apparier des graphes sont des tâches primordiales en informatique, analyse de donnée, traitement d’image, généralement modélisées par des problèmes d’optimisation de classe NP-difficile. Avec l’avènement des multiprocesseurs à bas coût, l’accélération des procédures heuristiques pour ces tâches devient possible et nécessaire. Nous proposons des implantations parallèles sur système GPU (graphics processing unit) pour des algorithmes génériques appliqués ici à la segmentation d’image en superpixels et au problème du flot optique. Le but est de fournir des algorithmes génériques basés sur des structures de données décentralisées et aisément adaptables à différents problèmes d’optimisation sur des graphes et plateformes parallèles.Les algorithmes parallèles proposés sur GPU incluent le classique k-means et le calcul de forêt couvrante minimum pour la segmentation en superpixels. Ils incluent également un algorithme de recherche locale parallèle et un algorithme mémétique à base de population de solutions appliqués à l’estimation du flot optique via des appariements de superpixels. Tandis que les opérations sur les données exploitent le GPU, l’algorithme mémétique opère en tant que coalition de processus exécutés en parallèle sur le CPU multi-cœur et requérant des ressources GPU. Les images sont des nuages de points de l’espace euclidien 3D (domaine espace-intensité), et aussi des graphes auxquels sont associés des grilles de processeurs. Les kernels GPU exécutent des transformations en parallèle sous contrôle du CPU qui a un rôle réduit de détection des conditions d’arrêt et de séquencement des transformations.La contribution présentée est composée de deux grandes parties. Dans une première partie, nous présentons des outils pour la segmentation en superpixels. Une implémentation parallèle de l’algorithme des k-means est présentée et appliquée aux données 3D. Elle est basée sur une subdivision cellulaire de l’espace 3D qui permet des recherches de plus proche voisin en parallèle en temps optimal constant pour des distributions bornées. Nous présentons également une application de l’algorithme parallèle de calcul de forêt couvrante de Boruvka à la segmentation superpixel de type ligne de partage-des-eaux (watershed). Dans une deuxième partie, en se basant sur les superpixels générés, des procédures parallèles de mise en correspondance sont dérivées pour l’estimation du flot optique avec prise en compte des discontinuités. Ces méthodes incluent des heuristiques de construction et d’amélioration, telles que le winner-take-all et la recherche locale parallèle, et leur intégration dans une métaheuristique à base de population. Diverses combinaisons d’exécution sont présentées et évaluées en comparaison avec des algorithmes de l’état de l’art performants
Finding clusters in point clouds and matching graphs to graphs are recurrent tasks in computer science domain, data analysis, image processing, that are most often modeled as NP-hard optimization problems. With the development and accessibility of cheap multiprocessors, acceleration of the heuristic procedures for these tasks becomes possible and necessary. We propose parallel implantation on GPU (graphics processing unit) system for some generic algorithms applied here to image superpixel segmentation and image optical flow problem. The aim is to provide generic algorithms based on standard decentralized data structures to be easy to improve and customized on many optimization problems and parallel platforms.The proposed parallel algorithm implementations include classical k-means algorithm and application of minimum spanning forest computation for super-pixel segmentation. They include also a parallel local search procedure, and a population-based memetic algorithm applied to optical flow estimation based on superpixel matching. While data operations fully exploit GPU, the memetic algorithm operates like a coalition of processes executed in parallel on the multi-core CPU and requesting GPU resources. Images are point clouds in 3D Euclidean space (space-gray value domain), and are also graphs to which are assigned processor grids. GPU kernels execute parallel transformations under CPU control whose limited role only consists in stopping criteria evaluation or sequencing transformations.The presented contribution contains two main parts. Firstly, we present tools for superpixel segmentation. A parallel implementation of the k-means algorithm is presented with application to 3D data. It is based on a cellular grid subdivision of 3D space that allows closest point findings in constant optimal time for bounded distributions. We present an application of the parallel Boruvka minimum spanning tree algorithm to compute watershed minimum spanning forest. Secondly, based on the generated superpixels and segmentation, we derive parallel optimization procedures for optical flow estimation with edge aware filtering. The method includes construction and improvement heuristics, as winner-take-all and parallel local search, and their embedding into a population-based metaheuristic framework. The algorithms are presented and evaluated in comparison to state-of-the-art algorithms

APA, Harvard, Vancouver, ISO, and other styles

10

Legrand, Hélène. "Algorithmes parallèles pour le traitement rapide de géométries 3D." Electronic Thesis or Diss., Paris, ENST, 2017. http://www.theses.fr/2017ENST0053.

Full text

Abstract:

Au cours des vingt dernières années, les principaux concepts du traitement du signal ont trouvé leur homologue pour le cas de la géométrie numérique, et en particulier des modèles polygonaux de surfaces 3D. Ces traitements requièrent néanmoins un temps de calcul non négligeable lorsqu’on les applique sur des modèles de taille conséquente. Cette charge de calcul devient un frein important dans le contexte actuel, où les quantités massives de données 3D générées à chaque seconde peuvent potentiellement nécessiter l’application d’un sous-ensemble de ces opérateurs. La capacité à exécuter des opérateurs de traitement géométrique en un temps très court représente alors un verrou important pour les systèmes de conception, capture et restitution 3D dynamiques. Dans ce contexte, on cherche à accélérer de plusieurs ordres de grandeur certains algorithmes de traitement géométrique actuels, et à reformuler ou approcher ces algorithmes afin de diminuer leur complexité ou de les adapter à un environnement parallèle. Dans cette thèse, nous nous appuyons sur un objet compact et efficace permettant d’analyser les surfaces 3D à plusieurs échelles : les quadriques d’erreurs. En particulier, nous proposons de nouveaux algorithmes haute performance, maintenant à la surface des quadriques d’erreur représentatives de la géométrie. Un des principaux défis tient ici à la génération des structures adaptées en parallèle, afin d’exploiter les processeurs parallèles à grain fin que sont les GPU, la principale source de puissance disponible dans un ordinateur moderne
Over the last twenty years, the main signal processing concepts have been adapted for digital geometry, in particular for 3D polygonal meshes. However, the processing time required for large models is significant. This computational load becomes an obstacle in the current context, where the massive amounts of data that are generated every second may need to be processed with several operators. The ability to run geometry processing operators with strong time constraints is a critical challenge in dynamic 3D systems. In this context, we seek to speed up some of the current algorithms by several orders of magnitude, and to reformulate or approximate them in order to reduce their complexity or make them parallel. In this thesis, we are building on a compact and effective object to analyze 3D surfaces at different scales : error quadrics. In particular, we propose new high performance algorithms that maintain error quadrics on the surface to represent the geometry. One of the main challenges lies in the effective generation of the right structures for parallel processing, in order to take advantage of the GPU

APA, Harvard, Vancouver, ISO, and other styles

11

Recur, Benoît. "Précision et qualité en reconstruction tomographique : algorithmes et applications." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14113/document.

Full text

Abstract:

Il existe un grand nombre de modalités permettant l'acquisition d'un objet de manière non destructrice (Scanner à Rayons X, micro-scanner, Ondes Térahertz, Microscopie Électronique de Transmission, etc). Ces outils acquièrent un ensemble de projections autour de l'objet et une étape de reconstruction aboutit à une représentation de l'espace acquis. La principale limitation de ces méthodes est qu'elles s'appuient sur une modélisation continue de l'espace alors qu'elles sont exploitées dans un domaine fini. L'étape de discrétisation qui en résulte est une source d'erreurs sur les images produites. De plus, la phase d'acquisition ne s'effectue pas de manière idéale et peut donc être entachée d'artéfacts et de bruits. Un grand nombre de méthodes, directes ou itératives, ont été développées pour tenter de réduire les erreurs et reproduire une image la plus représentative possible de la réalité. Un panorama de ces reconstructions est proposé ici et est coloré par une étude de la qualité, de la précision et de la résistances aux bruits d'acquisition.Puisque la discrétisation constitue l'une des principales limitations, nous cherchons ensuite à adapter des méthodes discrètes pour la reconstruction de données réelles. Ces méthodes sont exactes dans un domaine fini mais ne sont pas adaptées à une acquisition réelle, notamment à cause de leur sensibilité aux erreurs. Nous proposons donc un lien entre les deux mondes et développons de nouvelles méthodes discrètes plus robustes aux bruits. Enfin, nous nous intéressons au problème des données manquantes, i.e. lorsque l'acquisition n'est pas uniforme autour de l'objet, à l'origine de déformations dans les images reconstruites. Comme les méthodes discrètes sont insensibles à cet effet nous proposons une amorce de solution utilisant les outils développés dans nos travaux
A large kind of methods are available now to acquire an object in a non-destructive way (X-Ray scanner, micro-scanner, Tera-hertz waves, Transmission Electron Microscopy, etc). These tools acquire a projection set around the object and a reconstruction step leads to a representation of the acquired domain. The main limitation of these methods is that they rely on a continuous domain modeling wheareas they compute in a finite domain. The resulting discretization step sparks off errors in obtained images. Moreover, the acquisition step is not performed ideally and may be corrupted by artifacts and noises. Many direct or iterative methods have been developped to try to reduce errors and to give a better representative image of reality. An overview of these reconstructions is proposed and it is enriched with a study on quality, precision and noise robustness.\\Since the discretization is one of the major limitations, we try to adjust discrete methods for the reconstruction of real data. These methods are accurate in a finite domain but are not suitable for real acquisition, especially because of their error sensitivity. Therefore, we propose a link between the two worlds and we develop new discrete and noise robust methods. Finally, we are interesting in the missing data problem, i.e. when the acquisition is not uniform around the object, giving deformations into reconstructed images. Since discrete reconstructions are insensitive to this effect, we propose a primer solution using the tools developed previously

APA, Harvard, Vancouver, ISO, and other styles

12

Romera, Thomas. "Adéquation algorithme architecture pour flot optique sur GPU embarqué." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS450.

Full text

Abstract:

Cette thèse porte sur l'optimisation et l'implémentation efficace d'algorithmes d'estimation du mouvement des pixels (flot optique) sur des processeurs graphiques (GPU) embarqués. Deux algorithmes itératifs ont été étudiés : la méthode de Variation Totale - L1 (TV-L1) et la méthode de Horn-Schunck. L’objectif est d’obtenir un traitement temps réel (moins de 40 ms par images) sur des plateformes embarquées à faible consommation énergétique, tout en gardant une résolution image et une qualité d’estimation du flot acceptable pour les applications visées. Différents niveaux de stratégies d'optimisation ont été explorés. Des transformations algorithmiques de haut niveau, telles que la fusion d'opérateurs et le pipeline d'opérateurs, ont été mises en œuvre pour maximiser la réutilisation des données et améliorer la localité spatiale/temporelle. De plus, des optimisations bas niveau spécifiques aux GPU, notamment l'utilisation d'instructions et de nombres vectoriels, ainsi qu'une gestion efficace de l'accès à la mémoire, ont été intégrées. L'impact de la représentation des nombres en virgule flottante (simple précision par rapport à demi-précision) a également été étudié. Les implémentations ont été évaluées sur les plateformes embarquées Nvidia Jetson Xavier, TX2 et Nano en termes de temps d'exécution, de consommation énergétique et de précision du flot optique. Notamment, la méthode TV-L1 présente une complexité et une intensité de calcul plus élevées par rapport à Horn-Schunck. Les versions les plus rapides de ces algorithmes atteignent ainsi un temps de traitement de 0,21 nanosecondes par pixel par itération en demi-précision sur la plate-forme Xavier. Cela représente une réduction du temps d'exécution de 22x par rapport aux versions CPU efficaces et parallèles. De plus, la consommation d'énergie est réduite d'un facteur x5,3. Parmi les cartes testées, la plate-forme embarquée Xavier, à la fois la plus puissante et la plus récente, offre systématiquement les meilleurs résultats en termes de vitesse et d'efficacité énergétique. La fusion d'opérateurs et le pipelining se sont avérés essentiels pour améliorer les performances sur GPU en favorisant la réutilisation des données. Cette réutilisation des données est rendue possible grâce à la mémoire Shared des GPU, une petite mémoire d'accès rapide permettant le partage de données entre les threads du même bloc de threads GPU. Bien que la fusion de plusieurs itérations apporte des gains de performance, elle est limitée par la taille de la mémoire Shared, nécessitant des compromis entre l'utilisation des ressources et la vitesse. L'utilisation de nombres en demi-précision accélère les algorithmes itératifs et permet d'obtenir une meilleure précision du flot optique dans le même laps de temps par rapport aux versions en simple-précision. Les implémentations en demi-précision convergent plus rapidement en raison de l'augmentation du nombre d'itérations réalisables dans un délai donné. Plus précisément, l'utilisation de nombres en demi-précision sur la meilleure architecture GPU accélère l'exécution jusqu'à 2,2x pour TV-L1 et 3,7x pour Horn-Schunck. Ces travaux soulignent l'importance des optimisations spécifiques aux GPU pour les algorithmes de vision par ordinateur, ainsi que l'utilisation et l'étude des nombres à virgule flottante de précision réduite. Ils ouvrent la voie à des améliorations futures grâce à des différentes transformations algorithmiques, à des formats numériques différents et à des architectures matérielles nouvelles. Cette approche peut également être étendue à d'autres familles d'algorithmes itératifs
This thesis focus on the optimization and efficient implementation of pixel motion (optical flow) estimation algorithms on embedded graphics processing units (GPUs). Two iterative algorithms have been studied: the Total Variation - L1 (TV-L1) method and the Horn-Schunck method. The primary objective of this work is to achieve real-time processing, with a target frame processing time of less than 40 milliseconds, on low-power platforms, while maintaining acceptable image resolution and flow estimation quality for the intended applications. Various levels of optimization strategies have been explored. High-level algorithmic transformations, such as operator fusion and operator pipelining, have been implemented to maximize data reuse and enhance spatial/temporal locality. Additionally, GPU-specific low-level optimizations, including the utilization of vector instructions and numbers, as well as efficient memory access management, have been incorporated. The impact of floating-point number representation (single-precision versus half-precision) has also been investigated. The implementations have been assessed on Nvidia's Jetson Xavier, TX2, and Nano embedded platforms in terms of execution time, power consumption, and optical flow accuracy. Notably, the TV-L1 method exhibits higher complexity and computational intensity compared to Horn-Schunck. The fastest versions of these algorithms achieve a processing rate of 0.21 nanoseconds per pixel per iteration in half-precision on the Xavier platform, representing a 22x time reduction over efficient and parallel CPU versions. Furthermore, energy consumption is reduced by a factor of x5.3. Among the tested boards, the Xavier embedded platform, being both the most powerful and the most recent, consistently delivers the best results in terms of speed and energy efficiency. Operator merging and pipelining have proven to be instrumental in improving GPU performance by enhancing data reuse. This data reuse is made possible through GPU Shared memory, which is a small, high-speed memory that enables data sharing among threads within the same GPU thread block. While merging multiple iterations yields performance gains, it is constrained by the size of the Shared memory, necessitating trade-offs between resource utilization and speed. The adoption of half-precision numbers accelerates iterative algorithms and achieves superior optical flow accuracy within the same time frame compared to single-precision counterparts. Half-precision implementations converge more rapidly due to the increased number of iterations possible within a given time window. Specifically, the use of half-precision numbers on the best GPU architecture accelerates execution by up to x2.2 for TV-L1 and x3.7 for Horn-Schunck. This work underscores the significance of both GPU-specific optimizations for computer vision algorithms, along with the use and study of reduced floating point numbers. They pave the way for future enhancements through new algorithmic transformations, alternative numerical formats, and hardware architectures. This approach can potentially be extended to other families of iterative algorithms

APA, Harvard, Vancouver, ISO, and other styles

13

Soua, Mahmoud. "Extraction hybride et description structurelle de caractères pour une reconnaissance efficace de texte dans les documents hétérogènes scannés : Méthodes et Algorithmes parallèles." Thesis, Paris Est, 2016. http://www.theses.fr/2016PESC1069/document.

Full text

Abstract:

La Reconnaissance Optique de Caractères (OCR) est un processus qui convertit les images textuelles en documents textes éditables. De nos jours, ces systèmes sont largement utilisés dans les applications de dématérialisation tels que le tri de courriers, la gestion de factures, etc. Dans ce cadre, l'objectif de cette thèse est de proposer un système OCR qui assure un meilleur compromis entre le taux de reconnaissance et la vitesse de traitement ce qui permet de faire une dématérialisation de documents fiable et temps réel. Pour assurer sa reconnaissance, le texte est d'abord extrait à partir de l'arrière-plan. Ensuite, il est segmenté en caractères disjoints qui seront décrits ultérieurement en se basant sur leurs caractéristiques structurelles. Finalement, les caractères sont reconnus suite à la mise en correspondance de leurs descripteurs avec ceux d'une base prédéfinie. L'extraction du texte, reste difficile dans les documents hétérogènes scannés avec un arrière-plan complexe et bruité où le texte risque d'être confondu avec un fond texturé/varié en couleurs ou distordu à cause du bruit de la numérisation. D'autre part, la description des caractères, extraits et segmentés, se montre souvent complexe (calcul de transformations géométriques, utilisation d'un grand nombre de caractéristiques) ou peu discriminante si les caractéristiques des caractères choisies sont sensibles à la variation de l'échelle, de la fonte, de style, etc. Pour ceci, nous adaptons la binarisation au type de documents hétérogènes scannés. Nous assurons également une description hautement discriminante entre les caractères se basant sur l'étude de la structure des caractères selon leurs projections horizontale et verticale dans l'espace. Pour assurer un traitement temps réel, nous parallélisons les algorithmes développés sur la plateforme du processeur graphique (GPU). Nos principales contributions dans notre système OCR proposé sont comme suit :Une nouvelle méthode d'extraction de texte à partir des documents hétérogènes scannés incluant des régions de texte avec un fond complexe ou homogène. Dans cette méthode, un processus d'analyse d’image est employé suivi d’une classification des régions du document en régions d’images (texte avec un fond complexe) et de textes (texte avec un fond homogène). Pour les régions de texte on extrait l'information textuelle en utilisant une méthode de classification hybride basée sur l'algorithme Kmeans (CHK) que nous avons développé. Les régions d'images sont améliorées avec une Correction Gamma (CG) avant d'appliquer CHK. Les résultats obtenus d'expérimentations, montrent que notre méthode d'extraction de texte permet d'attendre un taux de reconnaissance de caractères de 98,5% sur des documents hétérogènes scannés.Un Descripteur de Caractère Unifié basé sur l'étude de la structure des caractères. Il emploie un nombre suffisant de caractéristiques issues de l'unification des descripteurs de la projection horizontale et verticale des caractères réalisantune discrimination plus efficace. L'avantage de ce descripteur est à la fois sa haute performance et sa simplicité en termes de calcul. Il supporte la reconnaissance des reconnaissance de caractère de 100% pour une fonte et une taille données.Une parallélisation du système de reconnaissance de caractères. Le processeur graphique GPU a été employé comme une plateforme de parallélisation. Flexible et puissante, cette architecture offre une solution efficace pour l'accélération des algorithmesde traitement intensif d'images. Notre mise en oeuvre, combine les stratégies de parallélisation à fins et gros grains pour accélérer les étapes de la chaine OCR. En outre, les coûts de communication CPU-GPU sont évités et une bonne gestion mémoire est assurée. L'efficacité de notre mise en oeuvre est validée par une expérimentation approfondie
The Optical Character Recognition (OCR) is a process that converts text images into editable text documents. Today, these systems are widely used in the dematerialization applications such as mail sorting, bill management, etc. In this context, the aim of this thesis is to propose an OCR system that provides a better compromise between recognition rate and processing speed which allows to give a reliable and a real time documents dematerialization. To ensure its recognition, the text is firstly extracted from the background. Then, it is segmented into disjoint characters that are described based on their structural characteristics. Finally, the characters are recognized when comparing their descriptors with a predefined ones.The text extraction, based on binarization methods remains difficult in heterogeneous and scanned documents with a complex and noisy background where the text may be confused with a textured background or because of the noise. On the other hand, the description of characters, and the extraction of segments, are often complex using calculation of geometricaltransformations, polygon, including a large number of characteristics or gives low discrimination if the characteristics of the selected type are sensitive to variation of scale, style, etc. For this, we adapt our algorithms to the type of heterogeneous and scanned documents. We also provide a high discriminatiobn between characters that descriptionis based on the study of the structure of the characters according to their horizontal and vertical projections. To ensure real-time processing, we parallelise algorithms developed on the graphics processor (GPU). Our main contributions in our proposed OCR system are as follows:A new binarisation method for heterogeneous and scanned documents including text regions with complex or homogeneous background. In this method, an image analysis process is used followed by a classification of the document areas into images (text with a complex background) and text (text with a homogeneous background). For text regions is performed text extraction using a hybrid method based on classification algorithm Kmeans (CHK) that we have developed for this aim. This method combines local and global approaches. It improves the quality of separation text/background, while minimizing the amount of distortion for text extraction from the scanned document and noisy because of the process of digitization. The image areas are improved with Gamma Correction (CG) before applying HBK. According to our experiment, our text extraction method gives 98% of character recognition rate on heterogeneous scanned documents.A Unified Character Descriptor based on the study of the character structure. It employs a sufficient number of characteristics resulting from the unification of the descriptors of the horizontal and vertical projection of the characters for efficient discrimination. The advantage of this descriptor is both on its high performance and its simple computation. It supports the recognition of alphanumeric and multiscale characters. The proposed descriptor provides a character recognition 100% for a given Face-type and Font-size.Parallelization of the proposed character recognition system. The GPU graphics processor has been used as a platform of parallelization. Flexible and powerful, this architecture provides an effective solution for accelerating intensive image processing algorithms. Our implementation, combines coarse/fine-grained parallelization strategies to speed up the steps of the OCR chain. In addition, the CPU-GPU communication overheads are avoided and a good memory management is assured. The effectiveness of our implementation is validated through extensive experiments

APA, Harvard, Vancouver, ISO, and other styles

14

He, Guanlin. "Parallel algorithms for clustering large datasets on CPU-GPU heterogeneous architectures." Electronic Thesis or Diss., université Paris-Saclay, 2022. http://www.theses.fr/2022UPASG062.

Full text

Abstract:

Clustering, qui consiste à réaliser des groupements naturels de données, est une tâche fondamentale et difficile dans l'apprentissage automatique et l'exploration de données. De nombreuses méthodes de clustering ont été proposées dans le passé, parmi lesquelles le clustering en k-moyennes qui est une méthode couramment utilisée en raison de sa simplicité et de sa rapidité.Le clustering spectral est une approche plus récente qui permet généralement d'obtenir une meilleure qualité de clustering que les k-moyennes. Cependant, les algorithmes classiques de clustering spectral souffrent d'un manque de passage à l'échelle en raison de leurs grandes complexités en nombre d'opérations et en espace mémoire nécessaires. Ce problème de passage à l'échelle peut être traité en appliquant des méthodes d'approximation ou en utilisant le calcul parallèle et distribué.L'objectif de cette thèse est d'accélérer le clustering spectral et de le rendre applicable à de grands ensembles de données en combinant l'approximation basée sur des données représentatives avec le calcul parallèle sur processeurs CPU et GPU. En considérant différents scénarios, nous proposons plusieurs chaînes de traitement parallèle pour le clustering spectral à grande échelle. Nous concevons des algorithmes et des implémentations parallèles optimisés pour les modules de chaque chaîne proposée : un algorithme parallèle des k-moyennes sur CPU et GPU, un clustering spectral parallèle sur GPU avec un format de stockage creux, un filtrage parallèle sur GPU du bruit dans les données, etc. Nos expériences variées atteignent de grandes performances et valident le passage à l'échelle de chaque module et de nos chaînes complètes
Clustering, which aims at achieving natural groupings of data, is a fundamental and challenging task in machine learning and data mining. Numerous clustering methods have been proposed in the past, among which k-means is one of the most famous and commonly used methods due to its simplicity and efficiency.Spectral clustering is a more recent approach that usually achieves higher clustering quality than k-means. However, classical algorithms of spectral clustering suffer from a lack of scalability due to their high complexities in terms of number of operations and memory space requirements. This scalability challenge can be addressed by applying approximation methods or by employing parallel and distributed computing.The objective of this thesis is to accelerate spectral clustering and make it scalable to large datasets by combining representatives-based approximation with parallel computing on CPU-GPU platforms. Considering different scenarios, we propose several parallel processing chains for large-scale spectral clustering. We design optimized parallel algorithms and implementations for each module of the proposed chains: parallel k-means on CPU and GPU, parallel spectral clustering on GPU using sparse storage format, parallel filtering of data noise on GPU, etc. Our various experiments reach high performance and validate the scalability of each module and the complete chains

APA, Harvard, Vancouver, ISO, and other styles

15

Mabrouk, Lhoussein. "Contribution à l'implémentation des algorithmes de vision avec parallélisme massif de données sur les architectures hétérogènes CPU/GPU." Thesis, Université Grenoble Alpes, 2020. http://www.theses.fr/2020GRALT009.

Full text

Abstract:

Le mélange de gaussiennes (MoG) et l'acquisition comprimée (CS) sont deux algorithmes utilisés dans de nombreuses applications de traitement d'image et du son. Leur combinaison, CS-MoG, a été récemment utilisée pour la soustraction de fond dans des applications de détection des objets mobiles. Néanmoins, les implémentations de CS-MoG présentées dans la littérature ne profitent pas pleinement de l'évolution des architectures hétérogènes. Ces travaux de thèse proposent deux contributions pour l'implémentation efficace de CS-MoG sur architectures parallèles hétérogènes CPU/GPU. Ces dernières offrent de nos jours une grande flexibilité de programmation permettant d’optimiser les performances ainsi que l’efficacité énergétique.Notre première contribution consiste à offrir le meilleur compromis accélération-précision sur CPU et GPU. La seconde est la proposition d'une nouvelle approche adaptative de partitionnement de données permettant d'exploiter pleinement l'ensemble des CPUs-GPUs. Quelles que soient leurs performances relatives, cette approche, appelée Curseur de Distribution Optimale de Données (ODDC), vise à assurer un équilibrage automatique de la charge de calcul en estimant la proportion optimale des données qui doit être affectée à chaque processeur, en prenant en compte sa capacité de calcul.Cette approche met à jour ce partitionnement en ligne ce qui permet de prendre en compte toute influence de l'irrégularité du contenu des images traitées. En termes d’objets mobiles, nous ciblons principalement les véhicules dont la détection représente un ensemble de défis, mais afin de généraliser notre approche, nous testons également des scènes contenant d’autres types de cibles.Les résultats expérimentaux, sur différentes plateformes et jeux de données, montrent que la combinaison de nos deux contributions permet d'atteindre 98% des performances maximales possibles sur ces plateformes. Ces résultats peuvent être aussi bénéfiques pour d'autres algorithmes où les calculs s'effectuent d'une manière indépendante sur des petits grains de données
Mixture of Gaussians (MoG) and Compressive Sensing (CS) are two common algorithms in many image and audio processing systems. Their combination, CS-MoG, was recently used for mobile objects detecting through background subtraction. However, the implementations of CS-MoG presented in previous works do not take full advantage of the heterogeneous architectures evolution. This thesis proposes two contributions for the efficient implementation of CS-MoG on heterogeneous parallel CPU/GPU architectures. These technologies nowadays offer great programming flexibility, which allows optimizing performance as well as energy efficiency.Our first contribution consists in offering the best acceleration-precision compromise on CPU and GPU. The second is the proposition of a new adaptive approach for data partitioning, allowing to fully exploiting the CPUs-GPUs. Whatever their relative performance, this approach, called the Optimal Data Distribution Cursor (ODDC), aims to ensure automatic balancing of the computational load by estimating the optimal proportion of data that has to be affected to each processor, taking into account its computing capacity.This approach updates the partitioning online, which allows taking into account any influence of the irregularity of the processed images content. In terms of mobile objects, we mainly target vehicles whose detection represents some challenges, but in order to generalize our approach, we test also scenes containing other types of targets.Experimental results, on different platforms and datasets, show that the combination of our two contributions makes it possible to reach 98% of the maximal possible performance on these platforms. These results can also be beneficial for other algorithms where calculations are performed independently on small grains of data

APA, Harvard, Vancouver, ISO, and other styles

16

Perrotte, Lancelot. "Algorithmes robustes de lancer de rayons pour calcul de dose interactif." Toulouse, ISAE, 2011. http://www.theses.fr/2011ESAE0005.

Full text

Abstract:

Dans le contexte actuel, il est plus que jamais nécessaire de disposer d'outils de simulation permettant d'évaluer rapidement la dose reçue par des opérateurs travaillant sur des sites irradiés. Afin d'étuider facilement de nombreux scénarios d'intervention, il nous faut diminuer les temps de calcul des simulateurs actuels, ce qui passe principalement par une accélération des calculs géométriques associés au calcul de dose. Ces calculs consistent à identifier et trier l'ensemble des intersections entre plusieurs groupes de rayons "radiatifs", convergeant tous au point de mesure de la dose, et une scène 3D volumineuse. Afin d'effectuer l'ensemble de ces calculs en une fraction de seconde, nous proposons d'abord un algorithme GPU complet permettant le traitement efficace d'un paquet de rayons cohérents. Ensuite, nous présentons une modification de cet algorithme garantissant la robustesse des tests d'intersection rayon-triangle et l'absence de précision dus aux calculs en arithmétique flottante, sans utilisation de coefficients dépendants de la scène et sans perte de performance notable (moins de 10% de dégradation). Enfin, nous proposons une stratégie efficace de traitement de multiples paquets (nécessaire lors de l'étude de multiples sources de radiations) exploitant ces premiers résultats. Ces méthodes nous permettent d'obtenir un calcul de dose interactif et robuste sur des scènes de taille importante (une scène de plus de 700 000 triangles, et 12 paquets de 100 000 rayons chacun, générant plus de treize millions d'intersections, stockées, triées le long de chaque rayon et transférées vers le CPU en 470 millisecondes).

APA, Harvard, Vancouver, ISO, and other styles

17

Luo, Jia. "Algorithmes génétiques parallèles pour résoudre des problèmes d'ordonnancement de tâches dynamiques de manière efficace en prenant en compte l'énergie." Thesis, Toulouse 3, 2019. http://www.theses.fr/2019TOU30001.

Full text

Abstract:

Du fait de nouvelles législations gouvernementales et de la prise de conscience environnementale des consommateurs ainsi que de la hausse du coût de l'énergie, l'efficacité énergétique est devenue un paramètre essentiel des processus industriels ces dernières années. La plupart des avancées en ce qui concerne les économies d'énergie dans les problèmes d'ordonnancement se sont focalisées sur l'ordonnancement statique. Mais en fait, ces problèmes sont dynamiques dans le monde réel. Dans cette thèse, deux problèmes d'ordonnancement dynamique efficace énergiquement sont étudiés. Le Modèle I analyse le retard total et la durée de production avec une limite de puissance tout en tenant compte d'un flux dynamique de nouvelles tâches. Un rééchelonnement complet périodique est adopté. Le Modèle II vise à réduire au minimum le retard total et la consommation d'énergie totale dans le traitement des tâches en tenant compte de nouvelles tâches prioritaires. Une approche basée sur la réparation de la planification des événements est utilisée pour traiter la mise à jour de l'ordonnancement. Comme un nouveau plan d'ordonnancement adéquat doit être obtenu dans un temps de réponse court dans un environnement dynamique, deux Algorithmes Génétiques parallèles (AG) sont proposés pour résoudre ces deux modèles. L'algorithme parallèle AG I est une méthode hybride basée sur CUDA consistant en un modèle AG insulaire au niveau supérieur et un modèle AG fin, au niveau inférieur. Il combine les métriques de deux couches hiérarchiques et tire pleinement parti des capacités de calcul de la plateforme CUDA. L'algorithme AG II est conçu avec une double hétérogénéité qui résulte de l'utilisation d'un AG cellulaire parallèle et d'un pseudo AG parallèle. Avec ces deux structures différentes, les ilots augmentent la diversité de la population et peuvent être simultanément parallélisés sur des GPU et un processeur multi-cœur. Enfin, des solutions numériques sont présentées et analysées ; elles montrent que nos approches peuvent non seulement résoudre les problèmes de manière flexible, mais également obtenir des solutions avantageuses et réduire les temps de calcul
Due to new government legislation, customers' environmental concerns and continuously rising cost of energy, energy efficiency is becoming an essential parameter of industrial manufacturing processes in recent years. Most efforts considering energy issues in scheduling problems have focused on static scheduling. But in fact, scheduling problems are dynamic in the real world with uncertain new arrival jobs after the execution time. In this thesis, two energy efficient dynamic scheduling problems are studied. Model I analyzes the total tardiness and the makespan with a peak power limitation while considering the flexible flow shop with new arrival jobs. A periodic complete rescheduling approach is adopted to represent the optimization problem. Model II concerns an investigation into minimizing total tardiness and total energy consumption in the job shop with new urgent arrival jobs. An event driven schedule repair approach is utilized to deal with the updated schedule. As an adequate renewed scheduling plan needs to be obtained in a short response time in dynamic environment, two parallel Genetic Algorithms (GAs) are proposed to solve these two models respectively. The parallel GA I is a CUDA-based hybrid model consisting of an island GA at the upper level and a fine-grained GA at the lower level. It combines metrics of two hierarchical layers and takes full advantage of CUDA's compute capability. The parallel GA II is a dual heterogeneous design composed of a cellular GA and a pseudo GA. The islands with these two different structures increase the population diversity and can be well parallelized on GPUs simultaneously with multi-core CPU. Finally, numerical experiments are conducted and show that our approaches can not only solve the problems flexibly, but also gain competitive results and reduce time requirements

APA, Harvard, Vancouver, ISO, and other styles

18

Delevacq, Audrey. "Métaheuristiques pour l'optimisation combinatoire sur processeurs graphiques (GPU)." Thesis, Reims, 2013. http://www.theses.fr/2013REIMS011/document.

Full text

Abstract:

Plusieurs problèmes d'optimisation combinatoire sont dits NP-difficiles et ne peuvent être résolus de façon optimale par des algorithmes exacts. Les métaheuristiques ont prouvé qu'elles pouvaient être efficaces pour résoudre un grand nombre de ces problèmes en leur trouvant des solutions approchées en un temps raisonnable. Cependant, face à des instances de grande taille, elles ont besoin d'un temps de calcul et d'une quantité d'espace mémoire considérables pour être performantes dans l'exploration de l'espace de recherche. Par conséquent, l'intérêt voué à leur déploiement sur des architectures de calcul haute performance a augmenté durant ces dernières années. Les approches de parallélisation existantes suivent généralement les paradigmes de passage de messages ou de mémoire partagée qui conviennent aux architectures traditionnelles à base de microprocesseurs, aussi appelés CPU (Central Processing Unit).Cependant, la recherche évolue très rapidement dans le domaine du parallélisme et de nouvelles architectures émergent, notamment les accélérateurs matériels qui permettent de décharger le CPU de certaines de ses tâches. Parmi ceux-ci, les processeurs graphiques ou GPU (Graphics Processing Units) présentent une architecture massivement parallèle possédant un grand potentiel mais aussi de nouvelles difficultés d'algorithmique et de programmation. En effet, les modèles de parallélisation de métaheuristiques existants sont généralement inadaptés aux environnements de calcul de type GPU. Certains travaux ont d'ailleurs abordé ce sujet sans toutefois y apporter une vision globale et fondamentale.L'objectif général de cette thèse est de proposer un cadre de référence permettant l'implémentation efficace des métaheuristiques sur des architectures parallèles basées sur les GPU. Elle débute par un état de l'art décrivant les travaux existants sur la parallélisation GPU des métaheuristiques et les classifications générales des métaheuristiques parallèles. Une taxonomie originale est ensuite proposée afin de classifier les implémentations recensées et de formaliser les stratégies de parallélisation sur GPU dans un cadre méthodologique cohérent. Cette thèse vise également à valider cette taxonomie en exploitant ses principales composantes pour proposer des stratégies de parallélisation originales spécifiquement adaptées aux architectures GPU. Plusieurs implémentations performantes basées sur les métaheuristiques d'Optimisation par Colonie de Fourmis et de Recherche Locale Itérée sont ainsi proposées pour la résolution du problème du Voyageur de Commerce. Une étude expérimentale structurée et minutieuse est réalisée afin d'évaluer et de comparer la performance des approches autant au niveau de la qualité des solutions trouvées que de la réduction du temps de calcul
Several combinatorial optimization problems are NP-hard and can only be solved optimally by exact algorithms for small instances. Metaheuristics have proved to be effective in solving many of these problems by finding approximate solutions in a reasonable time. However, dealing with large instances, they may require considerable computation time and amount of memory space to be efficient in the exploration of the search space. Therefore, the interest devoted to their deployment on high performance computing architectures has increased over the past years. Existing parallelization approaches generally follow the message-passing and shared-memory computing paradigms which are suitable for traditional architectures based on microprocessors, also called CPU (Central Processing Unit). However, research in the field of parallel computing is rapidly evolving and new architectures emerge, including hardware accelerators which offloads the CPU of some of its tasks. Among them, graphics processors or GPUs (Graphics Processing Units) have a massively parallel architecture with great potential but also imply new algorithmic and programming challenges. In fact, existing parallelization models of metaheuristics are generally unsuited to computing environments like GPUs. Few works have tackled this subject without providing a comprehensive and fundamental view of it.The general purpose of this thesis is to propose a framework for the effective implementation of metaheuristics on parallel architectures based on GPUs. It begins with a state of the art describing existing works on GPU parallelization of metaheuristics and general classifications of parallel metaheuristics. An original taxonomy is then designed to classify identified implementations and to formalize GPU parallelization strategies in a coherent methodological framework. This thesis also aims to validate this taxonomy by exploiting its main components to propose original parallelization strategies specifically tailored to GPU architectures. Several effective implementations based on Ant Colony Optimization and Iterated Local Search metaheuristics are thus proposed for solving the Travelling Salesman Problem. A structured and thorough experimental study is conducted to evaluate and compare the performance of approaches on criteria related to solution quality and computing time reduction

APA, Harvard, Vancouver, ISO, and other styles

19

Roccia, Jean-Patrick. "Accélération de l'algorithme du lancer de rayons en environnement parallèle hétérogène." Toulouse 3, 2013. http://thesesups.ups-tlse.fr/2008/.

Full text

Abstract:

Le lancer de rayons permet d'obtenir une grande précision pour simuler des phénomènes de rayonnements physiques, et ce dans des domaines très variés. Malgré sa relative simplicité, celui-ci pose de multiples problèmes lorsqu'il s'agit de le rendre performant. Les architectures matérielles modernes proposent un parallélisme croissant, symbolisé par une augmentation du nombre de cœurs de calculs disponibles, que ce soit sur CPU ou sur GPU. L'algorithme du lancer de rayons se doit de tirer parti de cette puissance de calcul disponible. En effet, au lieu de traiter les rayons de manière séquentielle, les traiter parallèlement permet d'augmenter significativement les performances. Nos contributions s'étalent sur l'ensemble des éléments clefs pour l'accélération de l'algorithme du lancer de rayons. La première permet d'accélérer la construction d'une structure d'accélération : un KD-Tree. Cette méthode permet d'accélérer la construction en utilisant conjointement le CPU et le GPU, et se compare avantageusement aux méthodes précédemment publiées. Notre seconde contribution permet la répartition des tâches de traversées du KD-Tree entre les CPU et GPU de manière transparente pour l'utilisateur. Notre troisième contribution concerne le test d'intersection rayon-triangle appliqué au KD-Tree et permet de maximiser l'utilisation des instructions SIMD des CPU lors de l'intersection tout en maitrisant la consommation mémoire et préservant les performances sur GPU. Enfin, notre dernière contribution est plus générale, et permet de répartir automatiquement de manière parallèle et transparente des calculs entre les unités de calculs hétérogènes
Ray tracing allows to obtain high accuracy to simulate physical phenomena of radiation, and in diverse areas. However, despite its relative simplicity, many problems occur when it comes to the performance. Modern hardware architectures offer a growing parallelism, symbolized by a growing number of available cores, whether on CPU or GPU. The ray tracing algorithm should take advantage of this available computing power. Indeed, instead of treating the rays sequentially, parallel processing can significantly increase performance. Thesis contributions are spread over all the main elements for ray tracing algorithm acceleration. The first one speeds up the construction of a high quality acceleration structure: a KD-Tree. This method can speed up the construction by using jointly CPU and GPU, and outperforms previously published method. The second contribution allows to spread the KD-Tree traversal steps between CPU and GPU transparently for users. The third contribution concerns the ray-triangle intersection test applied to the KD-Tree and allows to maximize the use of the SIMD instructions on CPU in the intersection test while controlling memory usage and maintaining performance on GPU. Finally, the last contribution is more general, and spreads automatically and transparently parallel computations tasks between heterogeneous computing units

APA, Harvard, Vancouver, ISO, and other styles

20

Jamal, Aygul. "A parallel iterative solver for large sparse linear systems enhanced with randomization and GPU accelerator, and its resilience to soft errors." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS269/document.

Full text

Abstract:

Dans cette thèse de doctorat, nous abordons trois défis auxquels sont confrontés les solveurs d'algèbres linéaires dans la perspective des futurs systèmes exascale: accélérer la convergence en utilisant des techniques innovantes au niveau algorithmique, en profitant des accélérateurs GPU (Graphics Processing Units) pour améliorer le calcul sur plusieurs systèmes, en évaluant l'impact des erreurs due à l'augmentation du parallélisme dans les superordinateurs. Nous nous intéressons à l'étude des méthodes permettant d'accélérer la convergence et le temps d'exécution des solveurs itératifs pour les grands systèmes linéaires creux. Le solveur plus spécifiquement considéré dans ce travail est le “parallel Algebraic Recursive Multilevel Solver (pARMS)” qui est un soldeur parallèle sur mémoire distribuée basé sur les méthodes de sous-espace de Krylov.Tout d'abord, nous proposons d'intégrer une technique de randomisation appelée “Random Butterfly Transformations (RBT)” qui a été proposée avec succès pour éliminer le coût du pivotage dans la résolution des systèmes linéaires denses. Notre objectif est d'appliquer cette technique dans le préconditionneur ARMS de pARMS pour résoudre plus efficacement le dernier système Complément de Schur dans l'application du processus à multi-niveaux récursif. En raison de l'importance considérable du dernier Complément de Schur pour certains problèmes de test, nous proposons également d'utiliser une variante creux de RBT suivie d'un solveur direct creux (SuperLU). Les résultats expérimentaux sur certaines matrices de la collection de Davis montrent une amélioration de la convergence et de la précision par rapport aux implémentations existantes.Ensuite, nous illustrons comment une approche non intrusive peut être appliquée pour implémenter des calculs GPU dans le solveur pARMS, plus particulièrement pour la phase de préconditionnement locale qui représente une partie importante du temps pour la résolution. Nous comparons les solveurs purement CPU avec les solveurs hybrides CPU / GPU sur plusieurs problèmes de test issus d'applications physiques. Les résultats de performance du solveur hybride CPU / GPU utilisant le préconditionnement ARMS combiné avec RBT, ou le préconditionnement ILU(0), montrent un gain de performance jusqu'à 30% sur les problèmes de test considérés dans nos expériences.Enfin, nous étudions l'effet des défaillances logicielles variable sur la convergence de la méthode itérative flexible GMRES (FGMRES) qui est couramment utilisée pour résoudre le système préconditionné dans pARMS. Le problème ciblé dans nos expériences est un problème elliptique PDE sur une grille régulière. Nous considérons deux types de préconditionneurs: une factorisation LU incomplète à double seuil (ILUT) et le préconditionneur ARMS combiné avec randomisation RBT. Nous considérons deux modèle de fautes logicielles différentes où nous perturbons la multiplication du vecteur matriciel et la phase de préconditionnement, et nous comparons leur impact potentiel sur la convergence
In this PhD thesis, we address three challenges faced by linear algebra solvers in the perspective of future exascale systems: accelerating convergence using innovative techniques at the algorithm level, taking advantage of GPU (Graphics Processing Units) accelerators to enhance the performance of computations on hybrid CPU/GPU systems, evaluating the impact of errors in the context of an increasing level of parallelism in supercomputers. We are interested in studying methods that enable us to accelerate convergence and execution time of iterative solvers for large sparse linear systems. The solver specifically considered in this work is the parallel Algebraic Recursive Multilevel Solver (pARMS), which is a distributed-memory parallel solver based on Krylov subspace methods.First we integrate a randomization technique referred to as Random Butterfly Transformations (RBT) that has been successfully applied to remove the cost of pivoting in the solution of dense linear systems. Our objective is to apply this method in the ARMS preconditioner to solve more efficiently the last Schur complement system in the application of the recursive multilevel process in pARMS. The experimental results show an improvement of the convergence and the accuracy. Due to memory concerns for some test problems, we also propose to use a sparse variant of RBT followed by a sparse direct solver (SuperLU), resulting in an improvement of the execution time.Then we explain how a non intrusive approach can be applied to implement GPU computing into the pARMS solver, more especially for the local preconditioning phase that represents a significant part of the time to compute the solution. We compare the CPU-only and hybrid CPU/GPU variant of the solver on several test problems coming from physical applications. The performance results of the hybrid CPU/GPU solver using the ARMS preconditioning combined with RBT, or the ILU(0) preconditioning, show a performance gain of up to 30% on the test problems considered in our experiments.Finally we study the effect of soft fault errors on the convergence of the commonly used flexible GMRES (FGMRES) algorithm which is also used to solve the preconditioned system in pARMS. The test problem in our experiments is an elliptical PDE problem on a regular grid. We consider two types of preconditioners: an incomplete LU factorization with dual threshold (ILUT), and the ARMS preconditioner combined with RBT randomization. We consider two soft fault error modeling approaches where we perturb the matrix-vector multiplication and the application of the preconditioner, and we compare their potential impact on the convergence of the solver

APA, Harvard, Vancouver, ISO, and other styles

21

Yu, Tianyi. "Décomposition en temps réel de signaux iEMG : filtrage bayésien implémenté sur GPU." Thesis, Ecole centrale de Nantes, 2019. http://www.theses.fr/2019ECDN0006/document.

Full text

Abstract:

Un algorithme de décomposition des unités motrices constituant un signal électromyographiques intramusculaires (iEMG) a été proposé au laboratoire LS2N. Il s'agit d'un filtrage bayésien estimant l'état d'un modèle de Markov caché. Cet algorithme demande beaucoup de temps d'execution, même pour un signal ne contenant que 4 unités motrices. Dans notre travail, nous avons d'abord validé cet algorithme dans une structure série. Nous avons proposé quelques modifications pour le modèle de recrutement des unités motrices et implémenté deux techniques de pré-traitement pour améliorer la performance de l'algorithme. Le banc de filtres de Kalman a été remplacé par un banc de filtre LMS. Le filtre global consiste en l'examen de divers scénarios arborescents d'activation des unités motrices: on a introduit deux techniques heuristiques pour élaguer les divers scénarios. On a réalisé l'implémentation GPU de cet algorithme à structure parallèle intrinsèque. On a réussi la décomposition de 10 signaux expérimentaux enregistrés sur deux muscules, respectivement avec électrode aiguille et électrode filaire. Le nombre d'unités motrices est de 2 à 8. Le pourcentage de superposition des potentiels d'unité motrice, qui représente la complexité de signal, varie de 6.56 % à 28.84 %. La précision de décomposition de tous les signaux sont plus que 90 %, sauf deux signaux en 30 % MVC , sauf pour deux signaux qui sont à 30 % MVC et dont la précision de décomposition est supérieure à 85%. Nous sommes les premiers à réaliser la décomposition en temps réel pour un signal constitué de 10 unités motrices
:A sequential decomposition algorithm based on a Hidden Markov Model of the EMG, that used Bayesian filtering to estimate the unknown parameters of discharge series of motor units was previously proposed in the laboratory LS2N. This algorithm has successfully decomposed the experimental iEMG signal with four motor units. However, the proposed algorithm demands a high time consuming. In this work, we firstly validated the proposed algorithm in a serial structure. We proposed some modifications for the activation process of the recruitment model in Hidden Markov Model and implemented two signal pre-processing techniques to improve the performance of the algorithm. Then, we realized a GPU-oriented implementation of this algorithm, as well as the modifications applied to the original model in order to achieve a real-time performance. We have achieved the decomposition of 10 experimental iEMG signals acquired from two different muscles, respectively by fine wire electrodes and needle electrodes. The number of motor units ranges from 2 to 8. The percentage of superposition, representing the complexity of iEMG signal, ranges from 6.56 % to 28.84 %. The accuracies of almost all experimental iEMG signals are more than90 %, except two signals at 30 % MVC (more than 85 %). Moreover, we realized the realtime decomposition for all these experimental signals by the parallel implementation. We are the first one that realizes the real time full decomposition of single channel iEMG signal with number of MUs up to 10, where full decomposition means resolving the superposition problem. For the signals with more than 10 MUs, we can also decompose them quickly, but not reaching the real time level

APA, Harvard, Vancouver, ISO, and other styles

22

Tran, Tuan Tu. "Comparaisons de séquences biologiques sur architecture massivement multi-coeurs." Thesis, Lille 1, 2012. http://www.theses.fr/2012LIL10138/document.

Full text

Abstract:

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 multicœurs: 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 ichotomique) 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
Searching similarities between sequences is a fundamental operation in bioinformatics, providing insight in biological functions as well as tools for high-throughput data. There is a need to have algorithms able to process efficiently billions of sequences. To look for approximate similarities,a common heuristic is to consider short words that appear exactly in both sequences, the seeds, then to try to extend this similarity to the neighborhoods of the seeds. The thesis focuses on this second stage of seed-based heuristics : how can we retrieve and compare efficiently the neighborhoods of the seeds ? The thesis proposes several solutions tailored for manycore processors such as today’s GPUs. Such processors are making massively parallel computing more and more popular. The thesis proposes direct approaches (extension of bit-parallel Wu-Manber algorithm, published in PBC 2011, and binary search) and approaches with another index (with perfect hash functions). Each one of these solutions was conceived to obtain as much fine-grained parallelism as possible, requiring intensive but homogeneous computational operations. All proposed methods were implemented in OpenCL and benchmarked. Finally, the thesis presents MAROSE, a prototype parallel read mapper using these concepts. In some situations, MAROSE is more efficient than the existing read mappers with a comparable sensitivity

APA, Harvard, Vancouver, ISO, and other styles

23

Seznec, Mickaël. "From the algorithm to the targets, optimization flow for high performance computing on embedded GPUs." Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG074.

Full text

Abstract:

Les algorithmes de traitement numérique actuels nécessitent une puissance de calcul accrue pour obtenir des résultats plus précis et traiter des données plus volumineuses. Dans le même temps, les architectures matérielles se spécialisent, avec des accélérateurs très efficaces pour des tâches spécifiques. Dans ce contexte, le chemin du déploiement de l'algorithme à l'implémentation est de plus en plus complexe. Il est donc crucial de déterminer comment les algorithmes peuvent être modifiés pour tirer parti des capacités du matériel. Dans notre étude, nous nous sommes intéressé aux unités graphiques (GPU), un type de processeur massivement parallèle. Notre travail a consisté à l'adaptation entre l'algorithme et le matériel d'exécution. À l'échelle d'un opérateur mathématique, nous avons modifié un algorithme de convolution d'images pour utiliser les tensor cores et montré qu'on peut en doubler les performances pour de grands noyaux de convolution. Au niveau méthode, nous avons évalué des solveurs de systèmes linéaires pour l'estimation de flux optique afin de trouver le plus adéquat sur GPU. Grâce à ce choix et après de nouvelles optimisations spécifiques, comme la fusion d'itérations ou la réutilisation de zones mémoire, la méthode est deux fois plus rapide que l'implémentation initiale, fonctionnant à 60 images par seconde sur plateforme embarquée (30W). Enfin, nous avons également montré l'intérêt, dans le cadre des réseaux de neurones profonds, de cette méthode de conception d'algorithmes adaptée au matériel. Avec pour exemple l'hybridation entre un réseau conçu pour le flux optique avec une autre architecture préentrainée et conçue pour être efficace sur des cibles à faible puissance de calcul
Current digital processing algorithms require more computing power to achieve more accurate results and process larger data. In the meantime, hardware architectures are becoming more specialized, with highly efficient accelerators designed for specific tasks. In this context, the path of deployment from the algorithm to the implementation becomes increasingly complex. It is, therefore, crucial to determine how algorithms can be modified to take advantage of new hardware capabilities. Our study focused on graphics processing units (GPUs), a massively parallel processor. Our algorithmic work was done in the context of radio-astronomy or optical flow estimation and consisted of finding the best adaptation of the software to the hardware. At the level of a mathematical operator, we modified the traditional image convolution algorithm to use the matrix units and showed that its performance doubles for large convolution kernels. At a broader method level, we evaluated linear solvers for the combined local-global optical flow to find the most suitable one on GPU. With additional optimizations, such as iteration fusion or memory buffer re-utilization, the method is twice as fast as the initial implementation, running at 60 frames per second on an embedded platform (30 W). Finally, we also pointed out the interest of this hardware-aware algorithm design method in the context of deep neural networks. For that, we showed the hybridization of a convolutional neural network for optical flow estimation with a pre-trained image classification network, MobileNet, that was initially designed for efficient image classification on low-power platforms

APA, Harvard, Vancouver, ISO, and other styles

24

Avril, Quentin. "Détection de Collision pour Environnements Large Échelle : Modèle Unifié et Adaptatif pour Architectures Multi-coeur et Multi-GPU." Phd thesis, INSA de Rennes, 2011. http://tel.archives-ouvertes.fr/tel-00642067.

Full text

Abstract:

Les environnements de réalité virtuelle devenant de plus en plus complexes et de très grandes dimensions, un niveau d'interaction temps-réel devient impossible à garantir. En effet, de par leur complexité, due à une géométrie détaillée et aux propriétés physiques spécifiques, ces environnements large échelle engendrent un goulet d'étranglement calculatoire critique sur les algorithmes de simulation physique. Nous avons focalisé nos travaux sur la première étape de ces algorithmes qui concerne la détection de collision, car les problématiques font partie intégrante de ce goulet d'étranglement et leur complexité peut parfois se révéler quadratique dans certaines situations. Le profond bouleversement que subissent les architectures machines depuis quelques années ouvre une nouvelle voie pour réduire le goulet d'étranglement. La multiplication du nombre de cœurs offre ainsi la possibilité d'exécuter ces algorithmes en parallèle sur un même processeur. Dans le même temps, les cartes graphiques sont passées d'un statut de simple périphérique d'affichage graphique à celui de supercalculateur. Elles jouissent désormais d'une attention toute particulière de la part de la communauté traitant de la simulation physique. Afin de passer au large échelle et d'être générique sur la machine d'exécution, nous avons proposé des modèles unifiés et adaptatifs de correspondance entre les algorithmes de détection de collision et les architectures machines de type multi-coeur et multi-GPU. Nous avons ainsi défini des solutions innovantes et performantes permettant de réduire significativement le temps de calcul au sein d'environnements large échelle tout en assurant la pérennité des résultats. Nos modèles couvrent l'intégralité du pipeline de détection de collision en se focalisant aussi bien sur des algorithmes de bas ou de haut niveau. Nos modèles multi-coeur, GPU et multi-GPU allient différentes techniques de subdivision spatiale à des algorithmes basés topologie ainsi que des techniques d'équilibrage de charge basées sur le vol de données. Notre solution hybride permet d'accroitre l'espace et le temps de calcul ainsi que le passage au large échelle. L'association de ces nouveaux algorithmes nous a permis de concevoir deux modèles d'adaptation algorithmique dynamique basés, ou non, sur des scénarios de pré-calcul hors-ligne. Enfin, il nous est apparu indispensable d'ajouter au pipeline de détection de collision une nouvelle dimension révélant la prise en compte des architectures pour une exécution optimale. Grâce à ce formalisme, nous avons proposé un nouveau pipeline de détection de collision offrant une granularité de parallélisme sur processeurs multi-coeur. Il permet une exécution simultanée des différentes étapes du pipeline ainsi qu'un parallélisme interne à chacune de ces étapes.

APA, Harvard, Vancouver, ISO, and other styles

25

Ghannam, Boutros. "Modélisation ultra-rapide des transferts de chaleur par rayonnement et par conduction et exemple d'application." Phd thesis, Ecole Nationale Supérieure des Mines de Paris, 2012. http://pastel.archives-ouvertes.fr/pastel-00958145.

Full text

Abstract:

L'apparition de CUDA en 2007 a rendu les GPU hautement programmables permettant ainsi aux applications scientifiques et techniques de profiter de leur capacité de calcul élevée. Des solutions ultra-rapides pour la résolution des transferts de chaleur par rayonnement et par conduction sur GPU sont présentées dans ce travail. Tout d'abord, la méthode MACZM pour le calcul des facteurs de transferts radiatifs directs en 3D et en milieu semi-transparent est représentée et validée. Ensuite, une implémentation efficace de la méthode à la base d'algorithmes de géométrie discrète et d'une parallélisation optimisée sur GPU dans CUDA atteignant 300 à 600 fois d'accélération, est présentée. Ceci est suivi par la formulation du NRPA, une version non-récursive de l'algorithme des revêtements pour le calcul des facteurs d'échange radiatifs totaux. La complexité du NRPA est inférieure à celle du PA et sont exécution sur GPU est jusqu'à 750 fois plus rapide que l'exécution du PA sur CPU. D'autre part, une implémentation efficace de la LOD sur GPU est présentée, consistant d'une alternance optimisée des solveurs et schémas de parallélisation et achevant une accélération GPU de 75 à 250 fois. Finalement, toutes les méthodes sont appliquées ensemble pour la résolution des transferts de chaleur en 3D dans un four de réchauffage sidérurgique de brames d'acier. Dans ce but, MACZM est appliquée avec un maillage multi-grille et le NRPA est appliqué au four en le découpant en zones, permettant d'avoir un temps de calcul très rapide une précision élevée. Ceci rend les méthodes utilisées de très grande importance pour la conception de stratégies de contrôle efficaces et précises.

APA, Harvard, Vancouver, ISO, and other styles

26

Wang, Hongjian. "Cellular matrix for parallel k-means and local search to Euclidean grid matching." Thesis, Belfort-Montbéliard, 2015. http://www.theses.fr/2015BELF0280/document.

Full text

Abstract:

Dans cette thèse, nous proposons un modèle de calcul parallèle, appelé « matrice cellulaire », pour apporter des réponses aux problématiques de calcul parallèle appliqué à la résolution de problèmes d’appariement de graphes euclidiens. Ces problèmes d’optimisation NP-difficiles font intervenir des données réparties dans le plan et des structures élastiques représentées par des graphes qui doivent s’apparier aux données. Ils recouvrent des problèmes connus sous des appellations diverses telles que geometric k-means, elastic net, topographic mapping, elastic image matching. Ils permettent de modéliser par exemple le problème du voyageur de commerce euclidien, le problème du cycle médian, ainsi que des problèmes de mise en correspondance d’images. La contribution présentée est divisée en trois parties. Dans la première partie, nous présentons le modèle de matrice cellulaire qui partitionne les données et définit le niveau de granularité du calcul parallèle. Nous présentons une boucle générique de calcul parallèle qui modélise le principe des projections de graphes et de leur appariement. Dans la deuxième partie, nous appliquons le modèle de calcul parallèle aux algorithmes de k-means avec topologie dans le plan. Les algorithmes proposés sont appliqués au voyageur de commerce, à la génération de maillage structuré et à la segmentation d'image suivant le concept de superpixel. L’approche est nommée superpixel adaptive segmentation map (SPASM). Dans la troisième partie, nous proposons un algorithme de recherche locale parallèle, appelé distributed local search (DLS). La solution du problème résulte des opérations locales sur les structures et les données réparties dans le plan, incluant des évaluations, des recherches de voisinage, et des mouvements structurés. L’algorithme est appliqué à des problèmes d’appariement de graphe tels que le stéréo-matching et le problème de flot optique
In this thesis, we propose a parallel computing model, called cellular matrix, to provide answers to problematic issues of parallel computation when applied to Euclidean graph matching problems. These NP-hard optimization problems involve data distributed in the plane and elastic structures represented by graphs that must match the data. They include problems known under various names, such as geometric k-means, elastic net, topographic mapping, and elastic image matching. The Euclidean traveling salesman problem (TSP), the median cycle problem, and the image matching problem are also examples that can be modeled by graph matching. The contribution presented is divided into three parts. In the first part, we present the cellular matrix model that partitions data and defines the level of granularity of parallel computation. We present a generic loop for parallel computations, and this loop models the projection between graphs and their matching. In the second part, we apply the parallel computing model to k-means algorithms in the plane extended with topology. The proposed algorithms are applied to the TSP, structured mesh generation, and image segmentation following the concept of superpixel. The approach is called superpixel adaptive segmentation map (SPASM). In the third part, we propose a parallel local search algorithm, called distributed local search (DLS). The solution results from the many local operations, including local evaluation, neighborhood search, and structured move, performed on the distributed data in the plane. The algorithm is applied to Euclidean graph matching problems including stereo matching and optical flow

APA, Harvard, Vancouver, ISO, and other styles

27

Baboud, Lionel. "Représentations alternatives du détail visuel pour le rendu en temps-réel." Phd thesis, Université Joseph Fourier (Grenoble), 2009. http://tel.archives-ouvertes.fr/tel-00452293.

Full text

Abstract:

Cette thèse se place dans le cadre de la synthèse d'images en temps réel. Le problème auquel elle s'attaque est celui du rendu efficace du détail visuel, principal élément du réalisme d'une image. Pour faire face à la complexité du détail visuel, il est nécessaire de disposer de représentations adaptées à la fois aux objets que l'on cherche à rendre ainsi qu'aux capacités des processeurs graphiques actuels. Le premier axe de recherche porte sur l'utilisation du relief pour représenter et rendre efficacement du détail géométrique. La représentation compacte et structurée du relief par une carte hauteur permet la conception d'algorithmes de rendu exacts et efficaces. Nous en proposons deux~: le premier permet de rendre des reliefs dynamiques, alors que le second s'adresse aux reliefs statiques en exploitant la possibilité d'effectuer un pré-traitement sur la carte de hauteur. Nous développons aussi une réflexion sur l'utilisation du relief pour la représentation de surfaces quelconques, et présentons une application au rendu réaliste et en temps réel de volumes d'eau. Le deuxième axe de recherche se concentre sur les représentations non surfaciques, nécessaires lorsque les représentations géométriques sont inadaptées voire inexistantes. C'est le cas notamment des objets lointains ou des objets à géométrie dense, comme par exemple le feuillage d'un arbre. Le problème ici est d'être capable de représenter l'apparence d'un objet, sans recourir à un modèle géométrique. Nous proposons une méthode permettant, à partir de la seule donnée du light-field d'un objet, de déterminer les paramètres optimaux d'une représentation adaptée pour le rendu.

APA, Harvard, Vancouver, ISO, and other styles

28

Baboud, Lionel. "Représentations alternatives du détail visuel pour le rendu en temps-réel." Phd thesis, Grenoble 1, 2009. http://www.theses.fr/2009GRE10222.

Full text

Abstract:

Cette thèse se place dans le cadre de la synthèse d'images en temps réel. Le problème auquel elle s'attaque est celui du rendu efficace du détail visuel, principal élément du réalisme d'une image. Pour faire face à la complexité du détail visuel, il est nécessaire de disposer de représentations adaptées à la fois aux objets que l'on cherche à rendre ainsi qu'aux capacités des processeurs graphiques actuels. Le premier axe de recherche porte sur l'utilisation du relief pour représenter et rendre efficacement du détail géométrique. La représentation compacte et structurée du relief par une carte hauteur permet la conception d'algorithmes de rendu exacts et efficaces. Nous en proposons deux~: le premier permet de rendre des reliefs dynamiques, alors que le second s'adresse aux reliefs statiques en exploitant la possibilité d'effectuer un pré-traitement sur la carte de hauteur. Nous développons aussi une réflexion sur l'utilisation du relief pour la représentation de surfaces quelconques, et présentons une application au rendu réaliste et en temps réel de volumes d'eau. Le deuxième axe de recherche se concentre sur les représentations non surfaciques, nécessaires lorsque les représentations géométriques sont inadaptées voire inexistantes. C'est le cas notamment des objets lointains ou des objets à géométrie dense, comme par exemple le feuillage d'un arbre. Le problème ici est d'être capable de représenter l'apparence d'un objet, sans recourir à un modèle géométrique. Nous proposons une méthode permettant, à partir de la seule donnée du light-field d'un objet, de déterminer les paramètres optimaux d'une représentation adaptée pour le rendu
This thesis takes place in the context of real-time image synthesis. It addresses the problem of efficient rendering for visual detail, main component of an image's realism. To cope with the complexity of visual detail it is necessary to possess representations which are adapted to objects that are to be rendered, together with capabilities of modern graphics processors. The first research effort concerns the use of relief for efficiently representing and rendering geometrical detail. The compact and structured representation of relief by an height map allows to design efficient and accurate rendering algorithms. We propose two of them: the first one can render animated reliefs, while the second one focuses on static ones by exploiting the possibility to preprocess the height map. We also develop a consideration on the use of relief for the representation of general surfaces, and present an application for real-time rendering of realistic water volumes. The second research effort focuses on non-surfacic representations, necessary when geometrical representations are inadequate or even non-existent. It is notably the case of distant objects or objects possessing a dense geometry, like a tree's foliage for example. The problem here is to be able to represent the visual aspect of an object without resorting to any geometrical model. We propose a method taking the light-field of an object as only input data, to determine the optimal parameters for an efficiently renderable representation

APA, Harvard, Vancouver, ISO, and other styles

29

Zola, Wagner Machado Nunan 1961. "Parallel gpu algorithms for compressed implicit octrees." reponame:Repositório Institucional da UFPR, 2015. http://hdl.handle.net/1884/45749.

Full text

Abstract:

Orientador : Prof. Dr. Luis Carlos Erpen de Bona
Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 10/09/2015
Inclui referências : f. 97-101
Resumo: O algoritmo Barnes-Hut é um método aproximado amplamente usado para na simulação gravitacional de N-Corpos, que envolve a construção e eaminliamento de árvores esparsas a cada passo de simulação e assim reduzindo a complexidade computacional e possibilitando a solução de problemas práticos de grande escala, A natureza irregular desse código de eaminliamento em árvore apresenta desafios interessantes na sua computação em sistemas paralelos. Desafios adicionais ocorrem nesse tipo de padrão de computação paralela quando se deseja utilizar de maneira eficaz a capacidade computacional de arquiteturas de GPUs (processadores gráficos multieore de propósito geral), Oetrees são estruturas de dados que representam de maneira eficiente as informações de dados espaciais em várias áreas tais como computação científica, computação gráfica, processamento de imagens, dentre outras. Nosso enfoque nesse trabalho é de tratar explicitamente os padrões dinâmicos irregulares de acesso a dados em memória com o remapeamento de dados e transformações de lavouts, dependendo das estruturas acessadas. Também é feito o controle explicito, por programa, de fluxos divergentes de execuções em threads. Apresentamos uma nova estrutura de dados compacta para lavouts de oetrees esparsas, bem como algoritmos paralelos para GPUs, tanto para transformações de lavouts como para eaminliamento paralelo usando a técnica de simulação de "warps"-largos (SWW, Simulated Wide-Warps), Os benefícios de nossas técnicas ocorrem devido à transposição do algoritmo de eamin- nhamento na árvore para execução em padrões mais regulares, possibilitando uma melhor adaptação ao modelo GPU paralelo, A estrutura de dados permite explorar localidades de acessos à memória durante os percursos, ao mesmo tempo conservando espaço em memória eaehe ou em memória compartilhada (scratchpad). Desta forma a memória rápida intra-eore pode ser dedicada a acelerar eaminliamentos. Controle divergência de fluxos também é delimitado de maneira algorítmica, impondo uma execução uniforme na maior parte dos segmentos de execução. Nossos experimentos mostram melhoria de desempenho significativa em relação às soluções em GPU mais conhecidas para este algoritmo. Desenvolvemos um novo algoritmo paralelo eficiente que gera diretamente de uma só vez as oetrees implícitas comprimidas, como um método massivamente paralelo. Este método traz uma nova visão para tratar de forma eficiente com a natureza irregular também presente na construção de oetrees esparsas, O algoritmo proposto de geração massivamente paralela de oetrees esparsas tem aplicação imediata em nossa implementação GPU paralela da simulação Barnes-Hut e em outros métodos de N-eorpos, As técnicas e algoritmos propostos nesta tese também poderão ser aplicadas em outros contextos. Palavras-chave: Algoritmo Massivamente Paralelo para Geração de Octrees; Octrees esparsas; Octree implícita; Probleamas de N-Corpos; Barnes-Hut; GPGPIJ; WarpsLargos Simulados em Software; CIJDA; Algoritmo Paralelo irregular; Algoritmos paralelos; Manycore Computing; Acelerador de Computação;
Abstract: The Barnes-Hut algorithm is a widely used approximation method for the N-Body simulation problem, which involves the construction and traversal of sparse trees at each simulation step and thus reducing the complexity to solve large/praetieal problems. The irregular nature of this tree walking code presents interesting challenges for its computation on parallel systems. Additional problems arise in effectively exploiting the processing capacity of GPU architectures. Octrees are data structures that efficiently represent spatial data in many fields such as scientific computing, computer graphics and image processing, among others. In this work we explicitly deal with dynamic irregular patterns in data accesses with data remapping and data transformation, depending on the data structures being accessed, and by controlling the execution flow divergence of threads. We present a new compact data-strueture for sparse octree layouts, and also GPU parallel algorithms for tree transformation and parallel walking using software Simulated Wide-Warps (SWW), Benefits of our techniques are in transposing the tree algorithm to execute regular patterns to match the GPU parallel model. The data structure allows exploring localities during traversals, at the same time conserving space in caches or scratchpad memory. This way fast intra-eore memory can be dedicated to speed up traversals. Control flow divergence is also algorithmically constrained, enforcing a mostly uniform execution of threads. Our experiments show significant performance improvement over the best known GPU solutions to this algorithm. We have developed a novel efficient parallel algorithm that directly generates entire compressed implicit octrees at once, as a massively parallel method. This method brings new insight on how to efficiently deal with the irregular nature of algorithms for constructing sparse octrees. The proposed algorithm has immediate application to our GPU parallel Barnes-Hut implementation and other N-Body methods. We envision that the techniques and algorithms proposed in this dissertation can also be applied in other contexts. Keywords: Massively Parallel Octree Generation Algorithm; Sparse Octrees; Implicit Octree; N-Body; Barnes-Hut; GPGPU; Software Simulated Wide-Warp; CUDA; Irregular Parallel Algorithm; Parallel algorithms; Many core Computing; Accelerator Computing;

APA, Harvard, Vancouver, ISO, and other styles

30

Kang, Seunghwa. "On the design of architecture-aware algorithms for emerging applications." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/39503.

Full text

Abstract:

This dissertation maps various kernels and applications to a spectrum of programming models and architectures and also presents architecture-aware algorithms for different systems. The kernels and applications discussed in this dissertation have widely varying computational characteristics. For example, we consider both dense numerical computations and sparse graph algorithms. This dissertation also covers emerging applications from image processing, complex network analysis, and computational biology. We map these problems to diverse multicore processors and manycore accelerators. We also use new programming models (such as Transactional Memory, MapReduce, and Intel TBB) to address the performance and productivity challenges in the problems. Our experiences highlight the importance of mapping applications to appropriate programming models and architectures. We also find several limitations of current system software and architectures and directions to improve those. The discussion focuses on system software and architectural support for nested irregular parallelism, Transactional Memory, and hybrid data transfer mechanisms. We believe that the complexity of parallel programming can be significantly reduced via collaborative efforts among researchers and practitioners from different domains. This dissertation participates in the efforts by providing benchmarks and suggestions to improve system software and architectures.

APA, Harvard, Vancouver, ISO, and other styles

31

Ingram, Stephen F. "Multilevel multidimensional scaling on the GPU." Thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/409.

Full text

Abstract:

We present Glimmer, a new multilevel visualization algorithm for multidimensional scaling designed to exploit modern graphics processing unit (GPU) hard-ware. We also present GPU-SF, a parallel, force-based subsystem used by Glimmer. Glimmer organizes input into a hierarchy of levels and recursively applies GPU-SF to combine and refine the levels. The multilevel nature of the algorithm helps avoid local minima while the GPU parallelism improves speed of computation. We propose a robust termination condition for GPU-SF based on a filtered approximation of the normalized stress function. We demonstrate the benefits of Glimmer in terms of speed, normalized stress, and visual quality against several previous algorithms for a range of synthetic and real benchmark datasets. We show that the performance of Glimmer on GPUs is substantially faster than a CPU implementation of the same algorithm. We also propose a novel texture paging strategy called distance paging for working with precomputed distance matrices too large to fit in texture memory.

APA, Harvard, Vancouver, ISO, and other styles

32

Zaouche, Abdelouahib. "Egalisation aveugle utilisant des techniques d'optimisation évolutionistes et de recherche exhaustive par motifs généralistes." Valenciennes, 2007. https://ged.uphf.fr/nuxeo/site/esupversions/057b4ef6-37a6-4118-b768-5684a88e0912.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Zheng, Lu. "Parallel Junction Tree Algorithm on GPU." Thesis, Carnegie Mellon University, 2013. http://pqdtopen.proquest.com/#viewpdf?dispub=3575068.

Full text

Abstract:

Bayesian networks (BNs) are an effective tool in a diverse range of applications that require representation and reasoning with uncertain knowledge and data. Mathematically, a Bayesian network (BN) is a type of statistical model that can compactly represent complex probability distributions of random variables. Inference over BNs can be either exact or approximate. The junction tree algorithm is perhaps the most popular exact inference algorithm. The junction tree algorithm propagates beliefs (or posteriors) over a junction tree when a new piece of evidence comes in so that the factors over the junction tree stay consistent with each other.

However, belief propagation over junction trees is known to be computationally hard. The cornputational complexity hinders the application of BNs in cases where real-time inference is required. This thesis accelerates the junction tree belief propagation algorithm through parallelizing and using a state of the art manycore computing platform. Recent manycore computing platforms, like the recent Graphical Processing Units (GPUs) from NVIDIA and Intel's Knights Ferry, employ a Single Instruction Multiple Data (SIMD) architecture. They can provide massive computational power to address various computational problems. However, it is not trivial to map a problem instance to the manycore platform. The problem has to be carefully parallelized and the implementation has to be carefully optimized in order to make full use of the computation resources on a GPU.

In this thesis, we will thoroughly investigate the junction tree algorithm and identify the possible parallel opportunities. Our work mainly focuses on node-level parallelizati on, i.e., we parallelize each message passing of junction tree belief propagation. We first identify two kinds of parallelism in the message passing, namely, element-wise parallelism and arithmetic parallelism. Then, based on these two kinds parallelism, we propose a two-dimensional parallel message passing algorithm. In case of message passings that do not contain enough parallel opportunity, we also propose a junction tree pruning techniques called clique merging. Clique merging eliminates extremely small nodes in a junction tree so that the junction tree is better adjusted to the GPU platform.

Performance tuning for the parallel junction tree algorithm is necessary. Yet the diversity in size typically seen in the junction tree cliques makes the GPU input workload vary; the two dimensions of parallelism further add to the complexity of this tuning issue. Therefore it is hard to set the GPU configuration parameters for optimal performance. In this thesis, we parameterize the GPU tuning process and propose a machine learning framework to automatically optimize the performance. This framework essentially trains a machine learning model to capture causal relationships between a GPUs workload, its configuration, and resulting performance characteristics. The machine learning model is then used to optimize the GPU configuration. Experiments show that this auto-tuning framework can improve the performance significantly more than extensive manual tuning.

We implemented the parallel junction tree algorithm on a NVIDIA GTX 460 GPU card, and employed the clique merging and auto-tuning techniques. Compared with a benchmark sequential code that runs on an Intel Core 2 Quad CPU, the fully tuned code show up to 19.90x speedup. On average over all data-sets, we get a speedup of 10.70x (arithmetic average) or 8.68x (geometric average).

APA, Harvard, Vancouver, ISO, and other styles

34

Anders, Söderholm, and Sörman Justus. "GPU-accelleration of image rendering and sorting algorithms with the OpenCL framework." Thesis, Linköpings universitet, Programvara och system, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-127479.

Full text

Abstract:

Today's computer systems often contains several different processing units aside from the CPU. Among these the GPU is a very common processing unit with an immense compute power that is available in almost all computer systems. How do we make use of this processing power that lies within our machines? One answer is the OpenCL framework that is designed for just this, to open up the possibilities of using all the different types of processing units in a computer system. This thesis will discuss the advantages and disadvantages of using the integrated GPU available in a basic workstation computer for computation of image processing and sorting algorithms. These tasks are computationally intensive and the authors will analyze if an integrated GPU is up to the task of accelerating the processing of these algorithms. The OpenCL framework makes it possible to run one implementation on different processing units, to provide perspective we will benchmark our implementations on both the GPU and the CPU and compare the results. A heterogeneous approach that combines the two above mentioned processing units will also be tested and discussed. The OpenCL framework is analyzed from a development perspective and what advantages and disadvantages it brings to the development process will be presented.

APA, Harvard, Vancouver, ISO, and other styles

35

McLaughlin, Adam Thomas. "Power-constrained performance optimization of GPU graph traversal." Thesis, Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/50209.

Full text

Abstract:

Graph traversal represents an important class of graph algorithms that is the nucleus of many large scale graph analytics applications. While improving the performance of such algorithms using GPUs has received attention, understanding and managing performance under power constraints has not yet received similar attention. This thesis first explores the power and performance characteristics of breadth first search (BFS) via measurements on a commodity GPU. We utilize this analysis to address the problem of minimizing execution time below a predefined power limit or power cap exposing key relationships between graph properties and power consumption. We modify the firmware on a commodity GPU to measure power usage and use the GPU as an experimental system to evaluate future architectural enhancements for the optimization of graph algorithms. Specifically, we propose and evaluate power management algorithms that scale i) the GPU frequency or ii) the number of active GPU compute units for a diverse set of real-world and synthetic graphs. Compared to scaling either frequency or compute units individually, our proposed schemes reduce execution time by an average of 18.64% by adjusting the configuration based on the inter- and intra-graph characteristics.

APA, Harvard, Vancouver, ISO, and other styles

36

Sreehari, Ambuluri. "Implementations of the FFT algorithm on GPU." Thesis, Linköpings universitet, Elektroniksystem, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-91351.

Full text

Abstract:

The fast Fourier transform (FFT) plays an important role in digital signal processing (DSP) applications, and its implementation involves a large number of computations. Many DSP designers have been working on implementations of the FFT algorithms on different devices, such as central processing unit (CPU), Field programmable gate array (FPGA), and graphical processing unit (GPU), in order to accelerate the performance. We selected the GPU device for the implementations of the FFT algorithm because the hardware of GPU is designed with highly parallel structure. It consists of many hundreds of small parallel processing units. The programming of such a parallel device, can be done by a parallel programming language CUDA (Compute Unified Device Architecture). In this thesis, we propose different implementations of the FFT algorithm on the NVIDIA GPU using CUDA programming language. We study and analyze the different approaches, and use different techniques to accelerate the computations of the FFT. We also discuss the results and compare different approaches and techniques. Finally, we compare our best cases of results with the CUFFT library, which is a specific library to compute the FFT on NVIDIA GPUs.

APA, Harvard, Vancouver, ISO, and other styles

37

Zhu, Huanzhou. "Developing graph-based co-scheduling algorithms with GPU acceleration." Thesis, University of Warwick, 2016. http://wrap.warwick.ac.uk/92000/.

Full text

Abstract:

On-chip cache is often shared between processes that run concurrently on different cores of the same processor. Resource contention of this type causes the performance degradation to the co-running processes. Contention-aware co-scheduling refers to the class of scheduling techniques to reduce the performance degradation. Most existing contention-aware co-schedulers only consider serial jobs. However, there often exist both parallel and serial jobs in computing systems. This thesis aims to tackle these issues. We start with modelling the problem of co-scheduling the mix of serial and parallel jobs as an Integer Programming (IP) problem. Then we construct a co-scheduling graph to model the problem, and a set of algorithms are developed to find both optimal and near-optimal solutions. The results show that the proposed algorithms can find the optimal co-scheduling solution and that the proposed approximation technique is able to find the near optimal solutions. In order to improve the scalability of the algorithms, we use GPU to accelerate the solving process. A graph processing framework, called WolfPath, is proposed in this thesis. By taking advantage of the co-scheduling graph, WolfPath achieves significant performance improvement. Due to the long preprocessing time of WolfPath, we developed WolfGraph, a GPU-based graph processing framework that features minimal preprocessing time and uses the hard disk as a memory extension to solve large-scale graphs on a single machine equipped with a GPU device. Comparing with existing GPU-based graph processing frameworks, WolfGraph can achieve similar execution time but with minimal preprocessing time.

APA, Harvard, Vancouver, ISO, and other styles

38

Harvey, Jesse Patrick. "GPU acceleration of object classification algorithms using NVIDIA CUDA /." Online version of thesis, 2009. http://hdl.handle.net/1850/10894.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Knight, David Warwick. "Algorithms for MARS spectral CT." Thesis, University of Canterbury. Medical Physics, 2015. http://hdl.handle.net/10092/10422.

Full text

Abstract:

This thesis reports on algorithmic design and software development completed for the Medipix All Resolution System (MARS) multi-energy CT scanner. Two areas of research are presented - the speed and usability improvements made to the post-reconstruction material decomposition software; and the development of two algorithms designed for the implementation of a novel voxel system into the MARS image reconstruction chain. The MARS MD software package is the primary material analysis tool used by members of the MARS group. The photon-processing ability of the MARS scanner is what makes material decomposition possible. MARS MD loads reconstructed images created after a scan and creates a new set of images, one for every individual material within the object. The software is capable of discriminating at least six different materials, plus air, within the object. A significant speed improvement to this program was attained by moving the code base from GNU Octave to MATLAB and applying well known optimisation routines, while the creation of a graphical user interface made the software more accessible and easy to use. The changes made to MARS MD represented a significant contribution to the productivity of the entire MARS group. A drawback of the MARS image reconstruction chain is the time required to generate images of a scanned object. Compared to commercially available CT systems, the MARS system takes several orders of magnitude longer to do essentially the same job. With up to eight energy bins worth of data to consider during reconstruction, compared to a single energy bin in most com- mercial scanners, it is not surprising that there is a shortfall. A major performance limitation of the reconstruction process lies in the calculation of the small distances travelled by every detected photon within individual portions of the reconstruction volume. This thesis investigates a novel volume geometry that was developed by Prof. Phil Butler and Dr. Peter Renaud, and is designed to partially mitigate this time constraint. By treating the volume as a cylinder instead of a traditional cubic structure, the number of individual path length calculations can be drastically reduced. Two sets of algorithms are prototyped, coded in MATLAB, C++ and CUDA, and finally compared in terms of speed and visual accuracy.

APA, Harvard, Vancouver, ISO, and other styles

40

Lerchundi, Osa Gorka. "Fast Implementation of Two Hash Algorithms on nVidia CUDA GPU." Thesis, Norwegian University of Science and Technology, Department of Telematics, 2009. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-9817.

Full text

Abstract:

User needs increases as time passes. We started with computers like the size of a room where the perforated plaques did the same function as the current machine code object does and at present we are at a point where the number of processors within our graphic device unit its not enough for our requirements. A change in the evolution of computing is looming. We are in a transition where the sequential computation is losing ground on the benefit of the distributed. And not because of the birth of the new GPUs easily accessible this trend is novel but long before it was used for projects like SETI@Home, fightAIDS@Home, ClimatePrediction and there were shouting from the rooftops about what was to come. Grid computing was its formal name. Until now it was linked only to distributed systems over the network, but as this technology evolves it will take different meaning. nVidia with CUDA has been one of the first companies to make this kind of software package noteworthy. Instead of being a proof of concept its a real tool. Where the transition is expressed in greater magnitude in which the true artist is the programmer who uses it and achieves performance increases. As with many innovations, a community distributed worldwide has grown behind this software package and each one doing its bit. It is noteworthy that after CUDA release a lot of software developments grown like the cracking of the hitherto insurmountable WPA. With Sony-Toshiba-IBM (STI) alliance it could be said the same thing, it has a great community and great software (IBM is the company in charge of maintenance). Unlike nVidia is not as accessible as it is but IBM is powerful enough to enter home made supercomputing market. In this case, after IBM released the PS3 SDK, a notorious application was created using the benefits of parallel computing named Folding@Home. Its purpose is to, inter alia, find the cure for cancer. To sum up, this is only the beginning, and in this thesis is sized up the possibility of using this technology for accelerating cryptographic hash algorithms. BLUE MIDNIGHT WISH (The hash algorithm that is applied to the surgery) is undergone to an environment change adapting it to a parallel capable code for creating empirical measures that compare to the current sequential implementations. It will answer questions that nowadays havent been answered yet. BLUE MIDNIGHT WISH is a candidate hash function for the next NIST standard SHA-3, designed by professor Danilo Gligoroski from NTNU and Vlastimil Klima an independent cryptographer from Czech Republic. So far, from speed point of view BLUE MIDNIGHT WISH is on the top of the charts (generally on the second place right behind EDON-R - another hash function from professor Danilo Gligoroski). One part of the work on this thesis was to investigate is it possible to achieve faster speeds in processing of Blue Midnight Wish when the computations are distributed among the cores in a CUDA device card. My numerous experiments give a clear answer: NO. Although the answer is negative, it still has a significant scientific value. The point is that my work acknowledges viewpoints and standings of a part of the cryptographic community that is doubtful that the cryptographic primitives will benefit when executed in parallel in many cores in one CPU. Indeed, my experiments show that the communication costs between cores in CUDA outweigh by big margin the computational costs done inside one core (processor) unit.

APA, Harvard, Vancouver, ISO, and other styles

41

Marques, Ricardo Jorge dos Santos. "Algorithmic skeleton framework for the orchestration of GPU computations." Master's thesis, Faculdade de Ciências e Tecnologia, 2012. http://hdl.handle.net/10362/8382.

Full text

Abstract:

Dissertação para obtenção do Grau de Mestre em Engenharia Informática
The Graphics Processing Unit (GPU) is gaining popularity as a co-processor to the Central Processing Unit (CPU), due to its ability to surpass the latter’s performance in certain application fields. Nonetheless, harnessing the GPU’s capabilities is a non-trivial exercise that requires good knowledge of parallel programming. Thus, providing ways to extract such computational power has become an emerging research topic. In this context, there have been several proposals in the field of GPGPU (Generalpurpose Computation on Graphics Processing Unit) development. However, most of these still offer a low-level abstraction of the GPU computing model, forcing the developer to adapt application computations in accordance with the SPMD model, as well as to orchestrate the low-level details of the execution. On the other hand, the higher-level approaches have limitations that prevent the full exploitation of GPUs when the purpose goes beyond the simple offloading of a kernel. To this extent, our proposal builds on the recent trend of applying the notion of algorithmic patterns (skeletons) to GPU computing. We propose Marrow, a high-level algorithmic skeleton framework that expands the set of skeletons currently available in this field. Marrow’s skeletons orchestrate the execution of OpenCL computations and introduce optimizations that overlap communication and computation, thus conjoining programming simplicity with performance gains in many application scenarios. Additionally, these skeletons can be combined (nested) to create more complex applications. We evaluated the proposed constructs by confronting them against the comparable skeleton libraries for GPGPU, as well as against hand-tuned OpenCL programs. The results are favourable, indicating that Marrow’s skeletons are both flexible and efficient in the context of GPU computing.
FCT-MCTES - financing the equipment

APA, Harvard, Vancouver, ISO, and other styles

42

Alexandre, Fernando Jorge Marques. "Multi-GPU support on the marrow algorithmic skeleton framework." Master's thesis, Faculdade de Ciências e Tecnologia, 2013. http://hdl.handle.net/10362/10746.

Full text

Abstract:

Dissertação para obtenção do Grau de Mestre em Engenharia Informática
With the proliferation of general purpose GPUs, workload parallelization and datatransfer optimization became an increasing concern. The natural evolution from using a single GPU, is multiplying the amount of available processors, presenting new challenges, as tuning the workload decompositions and load balancing, when dealing with heterogeneous systems. Higher-level programming is a very important asset in a multi-GPU environment, due to the complexity inherent to the currently used GPGPU APIs (OpenCL and CUDA), because of their low-level and code overhead. This can be obtained by introducing an abstraction layer, which has the advantage of enabling implicit optimizations and orchestrations such as transparent load balancing mechanism and reduced explicit code overhead. Algorithmic Skeletons, previously used in cluster environments, have recently been adapted to the GPGPU context. Skeletons abstract most sources of code overhead, by defining computation patterns of commonly used algorithms. The Marrow algorithmic skeleton library is one of these, taking advantage of the abstractions to automate the orchestration needed for an efficient GPU execution. This thesis proposes the extension of Marrow to leverage the use of algorithmic skeletons in the modular and efficient programming of multiple heterogeneous GPUs, within a single machine. We were able to achieve a good balance between simplicity of the programming model and performance, obtaining good scalability when using multiple GPUs, with an efficient load distribution, although at the price of some overhead when using a single-GPU.
projects PTDC/EIA-EIA/102579/2008 and PTDC/EIA-EIA/111518/2009

APA, Harvard, Vancouver, ISO, and other styles

43

Nilsson, Mattias. "Evaluation of Computer Vision Algorithms Optimized for Embedded GPU:s." Thesis, Linköpings universitet, Datorseende, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-112575.

Full text

Abstract:

The interest of using GPU:s as general processing units for heavy computations (GPGPU) has increased in the last couple of years. Manufacturers such as Nvidia and AMD make GPU:s powerful enough to outrun CPU:s in one order of magnitude, for suitable algorithms. For embedded systems, GPU:s are not as popular yet. The embedded GPU:s available on the market have often not been able to justify hardware changes from the current systems (CPU:s and FPGA:s) to systems using embedded GPU:s. They have been too hard to get, too energy consuming and not suitable for some algorithms. At SICK IVP, advanced computer vision algorithms run on FPGA:s. This master thesis optimizes two such algorithms for embedded GPU:s and evaluates the result. It also evaluates the status of the embedded GPU:s on the market today. The results indicates that embedded GPU:s perform well enough to run the evaluatedd algorithms as fast as needed. The implementations are also easy to understand compared to implementations for FPGA:s which are competing hardware.

APA, Harvard, Vancouver, ISO, and other styles

44

Hopson, Benjamin Thomas Ken. "Techniques of design optimisation for algorithms implemented in software." Thesis, University of Edinburgh, 2016. http://hdl.handle.net/1842/20435.

Full text

Abstract:

The overarching objective of this thesis was to develop tools for parallelising, optimising, and implementing algorithms on parallel architectures, in particular General Purpose Graphics Processors (GPGPUs). Two projects were chosen from different application areas in which GPGPUs are used: a defence application involving image compression, and a modelling application in bioinformatics (computational immunology). Each project had its own specific objectives, as well as supporting the overall research goal. The defence / image compression project was carried out in collaboration with the Jet Propulsion Laboratories. The specific questions were: to what extent an algorithm designed for bit-serial for the lossless compression of hyperspectral images on-board unmanned vehicles (UAVs) in hardware could be parallelised, whether GPGPUs could be used to implement that algorithm, and whether a software implementation with or without GPGPU acceleration could match the throughput of a dedicated hardware (FPGA) implementation. The dependencies within the algorithm were analysed, and the algorithm parallelised. The algorithm was implemented in software for GPGPU, and optimised. During the optimisation process, profiling revealed less than optimal device utilisation, but no further optimisations resulted in an improvement in speed. The design had hit a local-maximum of performance. Analysis of the arithmetic intensity and data-flow exposed flaws in the standard optimisation metric of kernel occupancy used for GPU optimisation. Redesigning the implementation with revised criteria (fused kernels, lower occupancy, and greater data locality) led to a new implementation with 10x higher throughput. GPGPUs were shown to be viable for on-board implementation of the CCSDS lossless hyperspectral image compression algorithm, exceeding the performance of the hardware reference implementation, and providing sufficient throughput for the next generation of image sensor as well. The second project was carried out in collaboration with biologists at the University of Arizona and involved modelling a complex biological system – VDJ recombination involved in the formation of T-cell receptors (TCRs). Generation of immune receptors (T cell receptor and antibodies) by VDJ recombination is an enormously complex process, which can theoretically synthesize greater than 1018 variants. Originally thought to be a random process, the underlying mechanisms clearly have a non-random nature that preferentially creates a small subset of immune receptors in many individuals. Understanding this bias is a longstanding problem in the field of immunology. Modelling the process of VDJ recombination to determine the number of ways each immune receptor can be synthesized, previously thought to be untenable, is a key first step in determining how this special population is made. The computational tools developed in this thesis have allowed immunologists for the first time to comprehensively test and invalidate a longstanding theory (convergent recombination) for how this special population is created, while generating the data needed to develop novel hypothesis.

APA, Harvard, Vancouver, ISO, and other styles

45

Kump, Joseph Lee. "Efficient Algorithms for Data Analytics in Geophysical Imaging." Thesis, Virginia Tech, 2021. http://hdl.handle.net/10919/103864.

Full text

Abstract:

Modern sensing systems such as distributed acoustic sensing (DAS) can produce massive quantities of geophysical data, often in remote locations. This presents significant challenges with regards to data storage and performing efficient analysis. To address this, we have designed and implemented efficient algorithms for two commonly utilized techniques in geophysical imaging: cross-correlations, and multichannel analysis of surface waves (MASW). Our cross-correlation algorithms operate directly in the wavelet domain on compressed data without requiring a reconstruction of the original signal, reducing memory costs and improving scalabiliy. Meanwhile, our MASW implementations make use of MPI parallelism and GPUs, and present a novel problem for the GPU.
Master of Science
Modern sensor designs make it easier to collect large quantities of seismic vibration data. While this data can provide valuable insight, it is difficult to effectively store and perform analysis on such a high data volume. We propose a few new, general-purpose algorithms that enable speedy use of two common methods in geophysical modeling and data analytics: crosscorrelation, which provides a measure of similarity between signals; and multichannel analysis of surface waves, which is a seismic imaging technique. Our algorithms take advantage of hardware and software typically available on modern computers, and the mathematical properties of these two methods.

APA, Harvard, Vancouver, ISO, and other styles

46

Ponce, Sean Philip. "Towards Algorithm Transformation for Temporal Data Mining on GPU." Thesis, Virginia Tech, 2009. http://hdl.handle.net/10919/34387.

Full text

Abstract:

Data Mining allows one to analyze large amounts of data. With increasing amounts of data being collected, more computing power is needed to mine these larger and larger sums of data. The GPU is an excellent piece of hardware with a compelling price to performance ratio and has rapidly risen in popularity. However, this increase in speed comes at a cost. The GPU's architecture executes non-data parallel code with either marginal speedup or even slowdown. The type of data mining we examine, temporal data mining, uses a Â¯nite state machine (FSM), which is non-data parallel. We contribute the concept of algorithm transformation for increasing the data parallelism of an algorithm. We apply the algorithm transformation process to the problem of temporal data mining which solves the same problem as the FSM-based algorithm, but is data parallel. The new GPU implementation shows a 6x speedup over the best CPU implementation and 11x speedup over a previous GPU implementation.
Master of Science

APA, Harvard, Vancouver, ISO, and other styles

47

Wang, Kaibo. "Algorithmic and Software System Support to Accelerate Data Processing in CPU-GPU Hybrid Computing Environments." The Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1447685368.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Valladares, Cereceda Ignacio. "GPU parallel algorithms for reporting movement behaviour patterns in spatiotemporal databases." Doctoral thesis, Universitat de Girona, 2013. http://hdl.handle.net/10803/119544.

Full text

Abstract:

In this thesis we treat and solve various problems related to movement pattern detection by designing and implementing parallel algorithms using the GPU. We first propose a GPU pipeline based algorithm to report the ’Popular places’ pattern. Then, we study the problem of reporting all subtrajectory clusters of a trajectory. To measure similarity between curves we choose the Fréchet distance. Finally we solve the ’Flock pattern’. To this aim, we present two algorithms to solve two problems related with the ’Flock pattern’: finding the maximal sets of a family and intersecting two families of sets. The GPU parallel algorithms proposed to solve these two problems are later used for reporting flock patterns
En aquesta tesi tractem i resolem varis problemes relacionats amb el càlcul de patrons de moviment en bases de dades espai-temporals, dissenyant i implementant algoritmes paral·lels utilitzant GPUs. Primer, proposem un algoritme que utilitza els processos gràfics de la GPU per reportar el patró ‘Llocs Populars’. Després estudiem el problema de reportar tots els grups de subtrajectories d’una trajectòria. Per mesurar la similitud entre corbes hem triat la distancia de Fréchet. Finalment resolem el problema del patró ‘Ramat’. Amb aquest objectiu, presentem dos algorismes per resoldre dos problemes relacionats amb el patró ‘Ramat’: El problema de trobar tots els conjunts maximals de una família, i el problema de intersecar dos famílies de conjunts. Proposem algorismes paral·lels per resoldre els dos problemes que després s’utilitzen per reportar patrons ’Ramat’

APA, Harvard, Vancouver, ISO, and other styles

49

Koskinas, Stefanos. "Denoising using randomized matching pursuit: algorithmic improvements and GPU implementation." Thesis, McGill University, 2013. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=116991.

Full text

Abstract:

Matching Pursuit (MP) techniques have recently been considered for signal denoising purposes. MP can reconstruct a clean signal from a noisy observation by greedily evaluating a least-squares (LS) estimate as a linear combination of elements (atoms) of a dictionary. This reconstruction approach avoids the intensive computation of the LS solution for large problems, but also exhibits improved performance in the context of denoising especially in the case where the clean signal is sparse. The original MP as well as other MP-type algorithms, such as the Orthogonal Matching Pursuit (OMP), iteratively solve the reconstruction problem through deterministic selections of atoms from the dictionary at each iteration step. Recent work has proposed randomized versions of MP and OMP that employ random selection of atoms instead and have the potential for further improvement of the denoising performance. In this thesis, we investigate further the performance of the Randomized MP (RMP) and OMP (ROMP) methods and compare them to their deterministic counterparts through Monte Carlo simulations and through a 2D geometric analysis of their behaviour. Motivated by our studies, we propose a novel multi-stage MP-based (MS-MP) denoising approach, and we show through simulations that, under certain conditions, it can significantly improve denoising performance. Finally, we observe that randomized MP algorithms exhibit a strong potential for parallelism and we present an implementation of a parallel RMP algorithm on a CUDA-capable GPU. Our implementation offers up to 9$\times$ improvement in runtime compared to a traditional serial algorithm.
Les techniques de Matching Pursuit (MP) ont été considérées récemment pour le débruitage des signaux. L'algorithme MP peut reconstruire un signal pur à partir d'une observation bruyante à travers une estimation gloutonne (greedy) des moindres carrés (MC) comme une combinaison linéaire des éléments (atomes) d'un dictionnaire. Cette méthode de reconstruction évite les calculs intensifs de la solution de MC pour de larges problèmes, et elle exhibe une performance améliorée pour enlever du bruit, particulièrement dans le cas où le signal est creux. L'algorithme MP original et d'autres algorithmes de type MP, comme Orthogonal Matching Pursuit (OMP), résolvent itérativement le problème de la reconstruction en utilisant, à chaque iteration, des sélections déterministes des atomes du dictionnaire. Cependant, des recherches récentes ont proposé l'emploi d'une sélection aléatoire d'atomes au lieu d'une sélection déterministe, qui est capable d'améliorer encore la performance du débruitage. Dans cette thèse, nous explorons la performance des algorithmes MP et OMP avec des sélections aléatoires d'atomes, et nous les comparons vis-à-vis des sélections déterministes en utilisant des simulations Monte Carlo et d'une analyse géométrique du leur comportement en deux dimensions. Motivés par nos études, nous proposons Multi-Stage MP (MS-MP), une nouvelle approche de MP qui utilise plusieurs étapes pour enlever le bruit. Les simulations démontrent que, sous certaines conditions, MS-MP peut améliorer la performance de manière significative. Enfin, nous observons que les algorithmes MP avec des sélections aléatoires d'atomes présentent un potentiel pour le parallélisme, et nous implémentons un algorithme parallèle de RMP sur un GPU compatible avec CUDA. Notre implémentation aboutit à une amélioration de la durée d'exécution jusqu' à neuf fois par rapport à un algorithme classique en série.

APA, Harvard, Vancouver, ISO, and other styles

50

Pospíchal, Petr. "Akcelerace genetického algoritmu s využitím GPU." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2009. http://www.nusl.cz/ntk/nusl-236783.

Full text

Abstract:

This thesis represents master's thesis focused on acceleration of Genetic algorithms using GPU. First chapter deeply analyses Genetic algorithms and corresponding topics like population, chromosome, crossover, mutation and selection. Next part of the thesis shows GPU abilities for unified computing using both DirectX/OpenGL with Cg and specialized GPGPU libraries like CUDA. The fourth chapter focuses on design of GPU implementation using CUDA, coarse-grained and fine-grained GAs are discussed, and completed by sorting and random number generation task accelerated by GPU. Next chapter covers implementation details -- migration, crossover and selection schemes mapped on CUDA software model. All GA elements and quality of GPU results are described in the last chapter.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Algorithmes GPU'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles