La méthode des éléments frontières pour l’équation des ondes (BEM) est utilisée en acoustique eten électromagnétisme pour simuler la propagation d’une onde avec une discrétisation en temps(TD). Elle permet d’obtenir un résultat pour plusieurs fréquences à partir d’une seule résolution.Dans cette thèse, nous nous intéressons à l’implémentation efficace d’un simulateur TD-BEM sousdifférents angles. Nous décrivons le contexte de notre étude et la formulation utilisée qui s’exprimesous la forme d’un système linéaire composé de plusieurs matrices d’interactions/convolutions.Ce système est naturellement calculé en utilisant l’opérateur matrice/vecteur creux (SpMV). Nousavons travaillé sur la limite du SpMV en étudiant la permutation des matrices et le comportementde notre implémentation aidé par la vectorisation sur CPU et avec une approche par bloc surGPU. Nous montrons que cet opérateur n’est pas approprié pour notre problème et nous proposonsde changer l’ordre de calcul afin d’obtenir une matrice avec une structure particulière.Cette nouvelle structure est appelée une matrice tranche et se calcule à l’aide d’un opérateur spécifique.Nous décrivons des implémentations optimisées sur architectures modernes du calculhaute-performance. Le simulateur résultant est parallélisé avec une approche hybride (mémoirespartagées/distribuées) sur des noeuds hétérogènes, et se base sur une nouvelle heuristique pouréquilibrer le travail entre les processeurs. Cette approche matricielle a une complexité quadratiquesi bien que nous avons étudié son accélération par la méthode des multipoles rapides (FMM). Nousavons tout d’abord travaillé sur la parallélisation de l’algorithme de la FMM en utilisant différentsparadigmes et nous montrons comment les moteurs d’exécution sont adaptés pour relâcher le potentielde la FMM. Enfin, nous présentons des résultats préliminaires d’un simulateur TD-BEMaccéléré par FMM . / The time-domain BEM for the wave equation in acoustics and electromagnetism is used to simulatethe propagation of a wave with a discretization in time. It allows to obtain several frequencydomainresults with one solve. In this thesis, we investigate the implementation of an efficientTD-BEM solver using different approaches. We describe the context of our study and the TD-BEMformulation expressed as a sparse linear system composed of multiple interaction/convolutionmatrices. This system is naturally computed using the sparse matrix-vector product (SpMV). Wework on the limits of the SpMV kernel by looking at the matrix reordering and the behavior of ourSpMV kernels using vectorization (SIMD) on CPUs and an advanced blocking-layout on NvidiaGPUs. We show that this operator is not appropriate for our problem, and we then propose toreorder the original computation to get a special matrix structure. This new structure is called aslice matrix and is computed with a custom matrix/vector product operator. We present an optimizedimplementation of this operator on CPUs and Nvidia GPUs for which we describe advancedblocking schemes. The resulting solver is parallelized with a hybrid strategy above heterogeneousnodes and relies on a new heuristic to balance the work among the processing units. Due tothe quadratic complexity of this matrix approach, we study the use of the fast multipole method(FMM) for our time-domain BEM solver. We investigate the parallelization of the general FMMalgorithm using several paradigms in both shared and distributed memory, and we explain howmodern runtime systems are well-suited to express the FMM computation. Finally, we investigatethe implementation and the parametrization of an FMM kernel specific to our TD-BEM, and weprovide preliminary results.

L'échographie est largement utilisée pour l'imagerie du flux sanguin pour ses nombreux avantages tels que son inocuité, son cout réduit, sa facilité d'utilisation et ses performances. Cette thèse a pour objectif de proposer de nouvelles méthodes ultrasonores d'imagerie du flux sanguin. Après une étude bibliographique, plusieurs approches ont été étudiées en détail jusqu'à leur implémentation sur l'échographe de recherche ULA-OP développé au sein du laboratoire et ont été validées en laboratoire et en clinique. La transmission d'ondes planes a été proposée pour améliorer la technique d'imagerie utilisant les oscillations transverses. Des champs de pression ultrasonores présentant des oscillations transverses sont générés dans de larges régions et exploités pour l'estimation vectorielle du flux sanguin à une haute cadence d'imagerie. Des cartes du flux sanguin sont obtenues grâce à une technique s'appuyant sur la transmission d'ondes planes couplées à un nouvel algorithme d'estimation de la vitesse dans le domaine fréquentiel. Les méthodes vectorielles implémentées en temps réel dans le ULA-OP ont été comparées à la méthode Doppler classique lors d'une étude clinique. Les résultats ont montré le bénéfice des méthodes vectorielles en termes de précision et de répétabilité. La nouvelle méthode proposée a démontré sa grande précision ainsi que son gain en termes de temps de calcul aussi bien en simulations qu'en acquisitions en laboratoire ou lors d'essais in vivo. Une solution logicielle temps réel implémentée sur une carte GPU a été proposée et testée afin de réduire encore le temps de calcul et permettre l'emploi de la méthode en clinique / Ultrasound is widely used for blood flow imaging because of the considerable advantages for the clinician, in terms of performance, costs, portability, and ease of use, and for the patient, in terms of safety and rapid checkup. The undesired limitations of conventional methods (1-D estimations and low frame-rate) are widely overtaken by new vector approaches that offer detailed descriptions of the flow for a more accurate diagnosis of cardiovascular system diseases. This PhD project concerns the development of novel methods for blood flow imaging. After studying the state-of-the-art in the field, a few approaches have been examined in depth up to their experimental validation, both in technical and clinical environments, on a powerful ultrasound research platform (ULA-OP). Real-time novel vector methods implemented on ULA-OP were compared to standard Doppler methods in a clinical study. The results attest the benefits of the vector methods in terms of accuracy and repeatability. Plane-wave transmissions were exploited to improve the transverse oscillation imaging method. Double oscillating fields were produced in large regions and exploited for the vectorial description of blood flow at high frame rates. Blood flow maps were obtained by plane waves coupled to a novel velocity estimation algorithm operating in the frequency domain. The new method was demonstrated capable of high accuracy and reduced computational load by simulations and experiments (also in vivo). The investigation of blood flow inside the common carotid artery has revealed the hemodynamic details with unprecedented quality. A software solution implemented on a graphic processing unit (GPU) board was suggested and tested to reduce the computational time and support the clinical employment of the method

Ce travail porte sur l'étude théorique et numérique des cristaux phononiques non linéaires. Les non linéarités étudiées sont celles dues aux constantes élastiques d'ordre deux (quadratiques) et trois (cubiques) des matériaux constituant les cristaux. Les effets non linéaires sont étudiés grâce à des méthodes d'éléments finis en simulant la propagation d'une onde élastique à travers les cristaux.Un premier projet de recherche a porté sur l'étude d'une structure osseuse, et plus spécifiquement sur la dispersion des ondes élastiques dans une structure constituée d'une alternance de couches de collagène et d'hydroxy apatite. Les simulations montrent qu'il existe un lien étroit entre l'hydratation des os et leur capacité à dissiper l'énergie.La seconde étude réalisée concerne un résonateur élastique. Une structure constituée d'inclusions d'acier dans de la silice présente un comportement de commutateur lorsque les non linéarités cubiques de l'acier sont prises en compte. Cet effet fortement non linéaire apparaît lorsque l'amplitude de l'onde incidente dépasse un certain seuil. Un modèle analytique complet est fourni.La dernière étude réalisée montre la conception de matériaux composites possédant de fortes non linéarités cubiques mais de faibles non linéarités quadratiques. La dérivation des lois de mélange des paramètres élastiques d'un matériau non linéaire dans un matériau linéaire est effectuée à l'ordre trois. Les équations montrent une forte amplification des paramètres non linéaires du matériau résultant pour certaines concentrations. Les simulations permettent de conclure que le résonateur mentionné ci-dessus peut effectivement être réalisé. / This work is dedicated to the theoretical and numerical study of nonlinear phononic crystals. The studied nonlinearities are those due to the second (quadratic) and third (cubic) order elastic constants of the materials that constitute the crystals. Nonlinear effects are studied by the means of finite element methods, used to simulate the propagation of an elastic wave through the crystals.A first research project concerns the study of a bone structure, namely the dispersion of elastic waves in a structure composed of collagen and hydroxy apatite alternate constituent layers. Simulations showed that it exists a strong link between bones hydration and their ability to dissipate the energy.The second study relates to an elastic resonator. A structure composed of steel inclusions in a silica matrix shows a switch behavior when the cubic nonlinearities of steel are taken into account. This strong nonlinear effect appears when the amplitude of the incident wave reaches a threshold. A full analytical model is provided.The last study demonstrates the design of composite materials with both strong cubic nonlinearities and weak quadratic nonlinearities. The derivation of the mixing laws of the elastic parameters of a nonlinear material inside a linear one is performed up to order three. Equations show a strong amplification of the nonlinear parameters of the material for some concentrations. Numerical simulations allow to conclude that the above mentioned resonator can be produced.

Les travaux présentés visent à améliorer les modèles de physique nucléaireutilisés dans l’évaluation des sections efficaces neutroniques de fission. Le résultat deces travaux donne les clefs pour une percée significative dans ce domaine et a permisd’étendre fortement les capacités du code d’évaluation CONRAD. Les sections partiellesétant naturellement corrélées entre-elles pour respecter la valeur de la section totale, cesaméliorations bénéficient à l’ensemble des sections partielles. Un cadre solide pour lamodélisation des processus concurrent à la fission a dû être établi sur le modèle du codede référence TALYS. Après s’être assuré de la fiabilité et de la cohérence du cadre, lesinvestigations spécifiques concernant la fission ont pu être réalisées. Les perspectivesd’applications offertes par les modèles macro-microscopiques FRDM et FRLDM ont étéanalysées. Ces modèles ont été implémentés et validés sur des données expérimentaleset des benchmarks. Afin d’obtenir des temps de calcul compatibles avec les besoins del’évaluation, des méthodes numériques sophistiquées ont été sélectionnées et une partiedes calculs a été portée sur GPU. Ces modèles macro-microscopiques peuvent être utiliséspour construire des surfaces d’énergie potentielle qui sont à leur tour traitées afin d’obtenirdes barrières de fission à une dimension, puis des coefficients de transmission fission. Cesderniers sont alors utilisés dans le cadre de modélisation des sections efficaces moyennesdu domaine statistique sur la base d’un modèle Hauser-Feshbach. Les résultats de cetteapproche seront présentés sur le cas du 239Pu(n,f). / The work presented here aims to improve models used in the fission crosssectionevaluation. The results give insights for a significant breakthrough in this fieldand yielded large extensions of the evaluation code CONRAD. Partial cross sections areinherently strongly correlated together as of the competition of the related reactions mustyield the total cross section. Therefore improving fission cross section benefits to all partialcross sections. A sound framework for the simulation of competitive reactions hadto be settled in order to further investigate on the fission reaction; this was implementedusing the TALYS reference code as guideline. After ensuring consistency and consistencyof the framework, focus was made on fission. Perspective resulting from the useof macroscopic-microscopic models such as the FRDM and FRLDM were analyzed; thesemodels have been implemented and validated on experimental data and benchmarks. Tocomply with evaluation requirements in terms of computation time, several specific numericalmethods have been used and parts of the program were written to run on GPU.These macroscopic-microscopic models yield potential energy surfaces that can be used toextract a one-dimensional fission barrier. This latter can then be used to obtained fissiontransmission coefficients that can be used in a Hauser-Feshbach model. This method hasbeen finally tested for the calculation of the average fission cross section for 239Pu(n,f).

Le travail présenté dans ce mémoire étudie et propose des modèles de calcul parallèles de type cellulaire pour traiter différents problèmes d’optimisation NP-durs définis dans l’espace euclidien, et leur implantation sur des processeurs graphiques multi-fonction (Graphics Processing Unit; GPU). Le but est de pouvoir traiter des problèmes de grande taille tout en permettant des facteurs d’accélération substantiels à l’aide du parallélisme massif. Les champs d’application visés concernent les systèmes embarqués pour la stéréovision de même que les problèmes de transports définis dans le plan, tels que les problèmes de tournées de véhicules. La principale caractéristique du modèle cellulaire est qu’il est fondé sur une décomposition du plan en un nombre approprié de cellules, chacune comportant une part constante de la donnée, et chacune correspondant à une unité de calcul (processus). Ainsi, le nombre de processus parallèles et la taille mémoire nécessaire sont en relation linéaire avec la taille du problème d’optimisation, ce qui permet de traiter des instances de très grandes tailles.L’efficacité des modèles cellulaires proposés a été testée sur plateforme parallèle GPU sur quatre applications. La première application est un problème d’appariement d’images stéréo. Elle concerne la stéréovision couleur. L’entrée du problème est une paire d’images stéréo, et la sortie une carte de disparités représentant les profondeurs dans la scène 3D. Le but est de comparer des méthodes d’appariement local selon l’approche winner-takes-all et appliquées à des paires d’images CFA (color filter array). La deuxième application concerne la recherche d’améliorations de l’implantation GPU permettant de réaliser un calcul quasi temps-réel de l’appariement. Les troisième et quatrième applications ont trait à l’implantation cellulaire GPU des réseaux neuronaux de type carte auto-organisatrice dans le plan. La troisième application concerne la génération de maillages structurés appliquée aux cartes de disparité afin de produire des représentations compressées des surfaces 3D. Enfin, la quatrième application concerne le traitement d’instances de grandes tailles du problème du voyageur de commerce euclidien comportant jusqu’à 33708 villes.Pour chacune des applications, les implantations GPU permettent une accélération substantielle du calcul par rapport aux versions CPU, pour des tailles croissantes des problèmes et pour une qualité de résultat obtenue similaire ou supérieure. Le facteur d’accélération GPU par rapport à la version CPU est d’environ 20 fois plus vite pour la version GPU sur le traitement des images CFA, cependant que le temps de traitement GPU est d’environ de 0,2s pour une paire d’images de petites tailles de la base Middlebury. L’algorithme amélioré quasi temps-réel nécessite environ 0,017s pour traiter une paire d’images de petites tailles, ce qui correspond aux temps d’exécution parmi les plus rapides de la base Middlebury pour une qualité de résultat modérée. La génération de maillages structurés est évaluée sur la base Middlebury afin de déterminer les facteurs d’accélération et qualité de résultats obtenus. Le facteur d’accélération obtenu pour l’implantation parallèle des cartes auto-organisatrices appliquée au problème du voyageur de commerce et pour l’instance avec 33708 villes est de 30 pour la version parallèle. / The work presented in this PhD studies and proposes cellular computation parallel models able to address different types of NP-hard optimization problems defined in the Euclidean space, and their implementation on the Graphics Processing Unit (GPU) platform. The goal is to allow both dealing with large size problems and provide substantial acceleration factors by massive parallelism. The field of applications concerns vehicle embedded systems for stereovision as well as transportation problems in the plane, as vehicle routing problems. The main characteristic of the cellular model is that it decomposes the plane into an appropriate number of cellular units, each responsible of a constant part of the input data, and such that each cell corresponds to a single processing unit. Hence, the number of processing units and required memory are with linear increasing relationship to the optimization problem size, which makes the model able to deal with very large size problems.The effectiveness of the proposed cellular models has been tested on the GPU parallel platform on four applications. The first application is a stereo-matching problem. It concerns color stereovision. The problem input is a stereo image pair, and the output a disparity map that represents depths in the 3D scene. The goal is to implement and compare GPU/CPU winner-takes-all local dense stereo-matching methods dealing with CFA (color filter array) image pairs. The second application focuses on the possible GPU improvements able to reach near real-time stereo-matching computation. The third and fourth applications deal with a cellular GPU implementation of the self-organizing map neural network in the plane. The third application concerns structured mesh generation according to the disparity map to allow 3D surface compressed representation. Then, the fourth application is to address large size Euclidean traveling salesman problems (TSP) with up to 33708 cities.In all applications, GPU implementations allow substantial acceleration factors over CPU versions, as the problem size increases and for similar or higher quality results. The GPU speedup factor over CPU was of 20 times faster for the CFA image pairs, but GPU computation time is about 0.2s for a small image pair from Middlebury database. The near real-time stereovision algorithm takes about 0.017s for a small image pair, which is one of the fastest records in the Middlebury benchmark with moderate quality. The structured mesh generation is evaluated on Middlebury data set to gauge the GPU acceleration factor and quality obtained. The acceleration factor for the GPU parallel self-organizing map over the CPU version, on the largest TSP problem with 33708 cities, is of 30 times faster.

La méthode PIC MCC (Particle-In-Cell Monte-Carlo Collision) est un outils très performant et efficace en ce qui concerne l'étude des plasmas (dans notre cas, pour des plasmas froids) car il permet de décrire l'évolution dans le temps et dans l'espace, des particules chargées sous l'effet des champs auto-consistants et des collisions. Dans un cas purement électrostatique, la méthode consiste à suivre les trajectoires d'un nombre représentatif de particules chargées, des électrons et des ions, dans l'espace des phases, et de décrire l'interaction collective de ces particules par la résolution de l'équation de Poisson. Dans le cas de plasmas froid, les trajectoires dans l'espace des phase sont déterminées par le champ électrique auto-consistant et par les collisions avec les atomes neutres ou les molécules et, pour des densités relativement importantes, par les collisions entre les particules chargées. Le coût des simulations pour ce type de méthode est très élevé en termes de ressources (CPU et mémoire). Ceci est dû aux fortes contraintes (dans les simulations PIC explicites) sur le pas de temps (plus petit qu'une fraction de la période plasma et inverse à la fréquence de giration électronique), sur le pas d'espace (de l'ordre de la longueur de Debye), et sur le nombre de particules par longueur de Debye dans la simulation (généralement de l'ordre de plusieurs dizaines). L'algorithme PIC MCC peut être parallélisé sur des fermes de calculs de CPU (le traitement de la trajectoires des particules est facilement parallélisable, mais la parallélisation de Poisson l'est beaucoup moins). L'émergence du GPGPU (General Purpose on Graphics Processing Unit) dans la recherche en informatique a ouvert la voie aux simulations massivement parallèle à faible coût et ceci par l'utilisation d'un très grand nombre de processeurs disponible sur les cartes graphiques permettant d'effectuer des opérations élémentaires (e.g. calcul de la trajectoires des particules) en parallèle. Un certain nombre d'outils numérique pour le calcul sur GPU ont été développés lors de ces 10 dernières années. De plus, le constructeur de cartes graphiques NVIDIA a développé un environnement de programmation appelé CUDA (Compute Unified Device Architecture) qui permet une parallélisation efficace des codes sur GPU. La simulation PIC avec l'utilisation des cartes graphiques ou de la combinaison des GPU et des CPU a été reporté par plusieurs auteurs, cependant les modèles PIC avec les collisions Monte-Carlo sur GPU sont encore en pleine étude. A l'heure actuelle, de ce que nous pouvons savoir, ce travail est le premier a montrer des résultats d'un code PIC MCC 2D et 3D entièrement parallélisé sur GPU et dans le cas de l'étude de plasma froid magnétisé. Dans les simulation PIC, il est relativement facile de suivre les particules lorsqu'il n'y a ni pertes ni création (e.g. limites périodiques ou pas d'ionisation) de particules au cours du temps. Cependant il devient nécessaire de réordonner les particules à chaque pas en temps dans le cas contraire (ionisation, recombinaison, absorption, etc). Cette Thèse met en lumière les stratégies qui peuvent être utilisées dans les modèles PIC MCC sur GPU permettant d'outre passer les difficultés rencontrées lors du réarrangement des particules après chaque pas de temps lors de la création et/ou des pertes. L'intérêt principal de ce travail est de proposer un algorithme implémenté sur GPU du modèle PIC MCC, de mesurer l'efficacité de celui-ci (parallélisation) et de le comparer avec les calculs effectués sur GPU et enfin d'illustrer les résultats de ce modèle par la simulation de plasma froid magnétisé. L'objectif est de présenter en détail le code utilisé en de montrer les contraintes et les avantages liées à la programmation de code PIC MCC sur GPU. La discussion est largement ciblé sur le cas en 2D, cependant un algorithme 3D a également été développé et testé comme il est montré à la fin de cette thèse.

No description available.

La simulation interactive du corps humain est un problème crucial en informatique médicale. Les approches sont multiples pour arriver à cet objectif. Diminuer le temps de calcul est le leitmotiv d'un grand nombre de travaux ces dernières années. Pour les recherches qui utilisent des modèles physiques inspirés de la Mécanique des Milieux Continus pour la simulation des objets déformables, ce sont principalement les forces internes et leurs dérivées qui font l'objet d'études pour l'amélioration des performances au niveau du temps de calcul. Nous avons choisi de développer la Méthode des Masses-Tenseurs, modèle physique souvent utilisé pour son bon compromis temps de calcul — précision. Notre première contribution est l'utilisation du calcul formel pour la génération des équations des forces internes et de leurs dérivées. Notre deuxième contribution est la parallélisation de ce modèle physique en calculant les équations générées sur le GPU. Notre troisième contribution est l'extension de ce modèle physique à d'autres types d'éléments : triangle, quadrangle, hexaèdre, prisme et pyramide. Tenir compte des déformations pour utiliser la loi de comportement la plus efficace en temps de calcul lorsque c'est possible, est une stratégie que nous avons mis en place. Dans la même idée, nous prenons en compte la géométrie du modèle à simuler pour utiliser des éléments plus complexes mais en nombre réduit. Pour utiliser ces stratégies, nous avons développé et utilisé des modèles mixtes en loi de comportement et en type d'éléments. Nos travaux se placent dans le contexte du projet ETOILE pour le développement d'un modèle biomécanique du système respiratoire / Interactive simulation of the human body is a crucial issue in medical computer sciences. There are many approaches to reach this goal. Reducing the computation time is the leitmotiv of a large number of efforts in recent years. For researches which use physical models derived from continuum mechanics for the simulation of deformable objects, it is primarily the internal forces and their derivatives which are the subject of study for improving computation time. We chose to develop the Tensor Mass Method, a physical model often used for its good computation time vs accuracy trade-off. Our first contribution is the use of computer algebra to generate the internal forces and their derivatives. Our second contribution is the parallelization of this physical model by computing the generated equations on the GPU. Our third contribution is an extension of this physical model to other elements : triangle, quandrangle , hexahedron, prism and pyramid. Considering deformations to use the most effective constitutive law in terms of computation time whenever possible is a good strategy that we started developing. In the same idea, we take the geometry of the simulated model into account to introduce more complex elements, albeit in reduced numbers. To use these strategies, we have developed mixed models in constitutive laws and elements. Our research was performed in the framework of the ETOILE project, to develop a biomechanical model of the respiratory system

The Intrusion Detection System (IDS) needs to compare the contents of all packets arriving at the network interface with a set of signatures for indicating possible attacks, a task that consumes much CPU processing time. In order to alleviate this problem, some researchers have tried to parallelize the IDS's comparison engine, transferring execution from the CPU to GPU. This This dissertation aims to parallelize the Brute Force and Aho-Corasick string matching algorithms and to propose a new compression of the State Transition Table of the Aho-Corasick algorithm in order to make it possible to use it in shared memory and accelerate the comparison of strings. The two algorithms were parallelized using the NVIDIA CUDA platform and executed in the GPU memories to allow a comparative analysis of the performance of these memories. Initially, the AC algorithm proved to be faster than the Brute Force algorithm and so it was followed for optimization. The AC algorithm was compressed and executed in parallel in shared memory, achieving a performance gain of 15% over other GPU memories and being 48 times faster than its serial version when testing with real network packets. When the tests were done with synthetic data (less random data) the gain reached 73% and the parallel algorithm was 56 times faster than its serial version. Thus, it can be seen that the use of compression in shared memory becomes a suitable solution to accelerate the processing of IDSs that need agility in the search for patterns. / Um Sistema de Detecção de Intrusão (IDS) necessita comparar o conteúdo de todos os pacotes que chegam na interface da rede com um conjunto de assinaturas que indicam possíveis ataques, tarefa esta que consome bastante tempo de processamento da CPU. Para amenizar esse problema, tem-se tentado paralelizar o motor de comparação dos IDSs transferindo sua execução da CPU para a GPU. Esta dissertação tem como objetivo fazer a paralelização dos algoritmos de comparação de strings Força-Bruta e Aho-Corasick e propor uma nova compactação da Tabela de Transição de Estados do algoritmo Aho-Corasick a fim de possibilitar o uso dela na memória compartilhada e acelerar a comparação de strings. Os dois algoritmos foram paralelizados utilizando a plataforma CUDA da NVIDIA e executados nas memórias da GPU a fim de possibilitar uma análise comparativa de desempenho dessas memórias. Inicialmente, o algoritmo AC mostrou-se mais veloz do que o algoritmo Força-Bruta e por isso seguiu-se para sua otimização. O algoritmo AC foi compactado e executado de forma paralela na memória compartilhada, alcançando um ganho de desempenho de 15% em relação às outras memórias da GPU e sendo 48 vezes mais rápido que sua versão na CPU quando os testes foram feitos com pacotes de redes reais. Já quando os testes foram feitos com dados sintéticos (dados menos aleatórios) o ganho chegou a 73% e o algoritmo paralelo chegou a ser 56 vezes mais rápido que sua versão serial. Com isso, pode-se perceber que o uso da compactação na memória compartilhada torna-se uma solução adequada para acelerar o processamento de IDSs que necessitem de agilidade na busca por padrões.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-30T14:24:27Z No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-30T14:29:29Z (GMT) No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-30T14:29:29Z (GMT). No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-08-08 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / This paper presents a Graphics Processing Unit (GPU) based parallels implementations for the All Pairs Shortest Paths and Transitive Closure problems in graph. The implementations are based on the main sequential algorithms and takes full advantage of the highly multithreaded architecture of current manycore GPUs. Our solutions reduces the communication between CPU and GPU, improves the Streaming Multiprocessors (SMs) utilization, and makes intensive use of coalesced memory access to optimize graph data access. The advantages of the proposed implementations are demonstrated for several graphs randomly generated using the widely known graph library GTgraph. Graphs containing thousands of vertices and different edges densities, varying from sparse to complete graphs, were generated and used in the experiments. Our results confirm that GPU implementations can be competitive even for graph algorithms whose memory accesses and work distribution are both irregular and data-dependent. Keywords / Este trabalho apresenta implementações paralelas baseadas em Graphics Processing Unit (GPU) para os problemas da identificação dos caminhos mínimos entre todos os pares de vértices e do fecho transitivo em um grafo. As implementações são baseadas nos principais algoritmos sequenciais e tiram o máximo proveito da arquitetura multithreaded das GPUs atuais. Nossa solução reduz a comunicação entre a Central Processing Unit (CPU) e a GPU, melhora a utilização dos Streaming Multiprocessors (SMs) e faz um uso intensivo de acesso aglutinado em memória para otimizar o acesso de dados do grafo. As vantagens dessas implementações propostas são demonstradas por vários grafos gerados aleatoriamente utilizando a ferramenta GTgraph. Grafos contendo milhares de vértices foram gerados e utilizados nos experimentos. Nossos resultados confirmam que implementações baseadas em GPU podem ser viáveis mesmo para algoritmos de grafos cujo acessos à memória e distribuição de trabalho são irregulares e causam dependência de dados.