Submitted by Erika Demachki (erikademachki@gmail.com) on 2017-01-06T16:59:11Z No. of bitstreams: 2 Tese - Walid Abdala Rfaei Jradi - 2016.pdf: 5339936 bytes, checksum: 0a0a6bdc4791ee31c229b5175ae3af03 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-09T09:29:25Z (GMT) No. of bitstreams: 2 Tese - Walid Abdala Rfaei Jradi - 2016.pdf: 5339936 bytes, checksum: 0a0a6bdc4791ee31c229b5175ae3af03 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-01-09T09:29:25Z (GMT). No. of bitstreams: 2 Tese - Walid Abdala Rfaei Jradi - 2016.pdf: 5339936 bytes, checksum: 0a0a6bdc4791ee31c229b5175ae3af03 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-11-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The present work studies and proposes GPU-based parallel algorithms and implementations for the problem of macroscopic assignment of urban traffic on large-scale networks, promoting an in-depth investigation on each sub-problem that must be efficiently solved during the traffic assignment process. Among the main contributions of this work, there are: 1) the first GPU-based algorithm for the enumeration of chordless cycles; 2) a new parallel GPU-based shortest path algorithm that takes advantage of some common properties of urban traffic networks; a refinement in the parallel reduction implementation proposed by one of the leaders in the GPU market, which resulted in a 2.8x speedup relative to its original version; and finally, 3) a parallel algorithm for the macroscopic traffic assignment problem, 39x faster than the equivalent sequential approach when applied to large scale networks. The main goal of this thesis is to contribute to the extension of the PET-Gyn software, proposing efficient GPU data structures and parallel algorithms for a faster resolution of two well known problems in the literature: The Traffic Assignment Problem (TAP) and the Enumeration of Chordless Cycles. When applied to difficult input sets, the performed experiments showed a clear advantage of the parallel algorithms over their sequential versions. / O presente trabalho estuda e propõe algoritmos e implementações paralelas baseadas em GPU para o problema de alocação macroscópica de tráfego urbano em redes de grande porte, promovendo uma investigação aprofundada de cada sub-problema que deve ser resolvido de forma eficiente durante o processo de atribuição de tráfego. Entre as principais contribuições deste trabalho, estão: 1) o primeiro algoritmo baseado em GPU para a enumeração de ciclos sem corda; 2) um novo algoritmo de caminho mínimo paralelo que tira vantagem de algumas propriedades comuns das redes de tráfego urbano; Um refinamento na implementação de redução paralela proposta por um dos líderes no mercado de GPU, o que resultou em uma aceleração de 2,8x em relação à sua versão original; 3) e, finalmente, um algoritmo paralelo para o problema de alocação macroscópica de tráfego, 39x mais rápido do que a abordagem equivalente sequencial quando aplicado a redes de larga escala. O objetivo principal desta tese é de contribuir para a expansão do software PET-Gyn, propondo estruturas de dados de GPU eficientes e algoritmos paralelos para uma resolução mais rápida de dois problemas bem conhecidos na literatura: O Problema de Alocação de Tráfego e a Enumeração de Ciclos sem Corda. Quando aplicados a conjuntos de entrada difíceis, os experimentos realizados mostraram uma clara vantagem dos algoritmos paralelos sobre suas versões sequenciais.

Nos últimos anos, uma das alternativas adotadas para aumentar o desempenho de sistemas de processamento de alto desempenho têm sido o uso de arquiteturas híbridas. Essas arquiteturas são constituídas de processadores multicore e coprocessadores especializados, como GPUs. Esses coprocessadores atuam como aceleradores em alguns tipos de operações. Por outro lado, as ferramentas e modelos de programação paralela atuais não são adequados para cenários híbridos, produzindo aplicações pouco portáveis. O paralelismo de tarefas considerado um paradigma de programação genérico e de alto nível pode ser adotado neste cenário. Porém, exige o uso de algoritmos de escalonamento dinâmicos, como o algoritmo de roubo de tarefas. Neste contexto, este trabalho apresenta um middleware (WORMS) que oferece suporte ao paralelismo de tarefas com escalonamento por roubo de tarefas em sistemas híbridos multi-CPU e multi-GPU. Esse middleware permite que as tarefas tenham implementação tanto para execução em CPUs quanto em GPUs, decidindo em tempo de execução qual das implementações será executada de acordo com os recursos de hardware disponíveis. Os resultados obtidos com o WORMS mostram ser possível superar, em algumas aplicações, tanto o desempenho de ferramentas de referência para execução em CPU quanto de ferramentas para execução em GPUs. / In the last years, one of alternatives adopted to increase performance in high performance computing systems have been the use of hybrid architectures. These architectures consist of multicore processors and specialized coprocessors, like GPUs. Coprocessors act as accelerators in some types of operations. On the other hand, current parallel programming models and tools are not suitable for hybrid scenarios, generating less portable applications. Task parallelism, considered a generic and high level programming paradigm, can be used in this scenario. However, it requires the use of dynamic scheduling algorithms, such as work stealing. In this context, this work presents a middleware (WORMS) that supports task parallelism with work stealing scheduling in multi-CPU and multi-GPU systems. This middleware allows task implementations for both CPU and GPU, deciding at runtime which implementation will run according to the available hardware resources. The performance results obtained with WORMS showed that is possible to outperform both CPU and GPU reference tools in some applications.

[pt] Ultimamente, sensores orbitais de alta resolução espacial estão fornecendo uma quantidade crescente de dados sobre a superfície da Terra. A análise destes dados implica em uma alta carga computacional, que tem motivado pesquisas envolvendo hardwares e softwares mais eficientes para estas aplicações. Neste contexto, uma questão importante reside na segmentação de imagens que envolve longos tempos de processamento e é etapa fundamental na análise de imagens baseada em objetos. Os avanços recentes das modernas unidades de processamento gráfico ou GPUs abriram a possibilidade de se explorar a capacidade de processamento paralelo para melhorar o desempenho da segmentação. Este trabalho apresenta uma versão paralela do algoritmo de segmentação multicritério, introduzido originalmente por Baatz e Schappe (2000), concebido para ser executado por GPUs. A arquitetura do hardware subjacente consiste em um sistema massivamente paralelo com múltiplos elementos processadores projetado especialmente para o processamento de imagens. O algoritmo paralelo é baseado no processamento de cada pixel em uma diferente linha de controle (thread) de modo a aproveitar a capacidade paralela da GPU. Esta dissertação também sugere alterações no cálculo de heterogeneidade do algoritmo, o que aumenta o desempenho computacional da segmentação. Os experimentos com o algoritmo paralelo proposto apresentaram uma aceleração maior do que 7 em relação à versão sequencial. / [en] Lately, orbital sensors of high spatial resolution are providing an increasing amount of data about the Earth surface. Analysis of these data implies in a high computational load, which has motivated researches on more efficient hardware and software for these applications. In this context, an important issue lies in the image segmentation that involves long processing times and is a key step in object based image analysis. The recent advances in modern programmable graphics units or GPUs have opened the possibility of exploiting the parallel processing capabilities to improve the segmentation performance. This work presents a parallel version of the multicriterion segmentation algorithm, introduced originally by Baatz and Schappe (2000), implemented in a GPU. The underlying hardware architecture consists of a massive parallel system with multiple processing elements designed especially for image processing. The parallel algorithm is based on processing each pixel as a different thread so as to take advantage of the fine-grain parallel capability of the GPU. In addition to the parallel algorithm, this dissertation also suggests a modification to the heterogeneity computation that improves the segmentation performance. The experiments under the proposed parallel algorithm present a speedup greater than 7 in relation to the sequential version.

La génération d'images de synthèse pour la production cinématographique n'a cessé d'évoluer durant ces dernières décennies. Pour le non-expert, il semble que les effets spéciaux aient atteint un niveau de réalisme ne pouvant être dépassé. Cependant, les logiciels mis à la disposition des artistes ont encore du progrès à accomplir. En effet, encore trop de temps est passé à attendre le résultat de longs calculs, notamment lors de la prévisualisation d'effets spéciaux. La lenteur ou la mauvaise qualité des logiciels de prévisualisation pose un réel problème aux artistes. Cependant, l'évolution des cartes graphiques ces dernières années laisse espérer une potentielle amélioration des performances de ces outils, notamment par la mise en place d'algorithmes hybrides rasterisation/ lancer de rayons, tirant profit de la puissance de calcul de ces processeurs, et ce, grâce à leur architecture massivement parallèle. Cette thèse explore les différentes briques logicielles nécessaires à la mise en place d'un pipeline de rendu complexe sur carte graphique, permettant une meilleure prévisualisation des effets spéciaux. Différentes contributions ont été apportées à l'entreprise durant cette thèse. Tout d'abord, un pipeline de rendu hybride a été développé (cf. Chapitre 2). Par la suite, différentes méthodes d'implémentation de l'algorithme de Path Tracing ont été testées (cf. Chapitre 3), de façon à accroître les performances du pipeline de rendu sur GPU. Une structure d'accélération spatiale a été implémentée (cf. Chapitre 4), et une amélioration de l'algorithme de traversée de cette structure sur GPU a été proposée (cf. Section 4.3.2). Ensuite, une nouvelle méthode de décorrélation d'échantillons, dans le cadre de la génération de nombres aléatoires a été proposée (cf. Section 5.4) et a donné lieu à une publication [Dufay et al., 2016]. Pour finir, nous avons tenté de combiner l'algorithme de Path Tracing et les solutions Many Lights, toujours dans le but d'améliorer la prévisualisation de l'éclairage global. Cette thèse a aussi donné lieu à la soumission de trois mémoires d'invention et a permis le développement de deux outils logiciels présentés en Annexe A. / Image synthesis for movie production never stopped evolving over the last decades. It seems it has reached a level of realism that cannot be outperformed. However, the software tools available for visual effects (VFX) artists still need to progress. Indeed, too much time is still wasted waiting for results of long computations, especially when previewing VFX. The delays or poor quality of previsualization software poses a real problem for artists. However, the evolution of graphics processing units (GPUs) in recent years suggests a potential improvement of these tools. In particular, by implementing hybrid rasterization/ray tracing algorithms, taking advantage of the computing power of these processors and their massively parallel architecture. This thesis explores the different software bricks needed to set up a complex rendering pipeline on the GPU, that enables a better previsualization of VFX. Several contributions have been brought during this thesis. First, a hybrid rendering pipeline was developed (cf. Chapter 2). Subsequently, various implementation schemes of the Path Tracing algorithm have been tested (cf. Chapter 3), in order to increase the performance of the rendering pipeline on the GPU. A spatial acceleration structure has been implemented (cf. Chapter 4), and an improvement of the traversal algorithm of this structure on GPU has been proposed (cf. Section 4.3.2). Then, a new sample decorrelation method, in the context of random number generation was proposed (cf. Section 5.4) and resulted in a publication [Dufay et al., 2016]. Finally, we combined the Path Tracing algorithm with the Many Lights solution, always with the aim of improving the preview of global illumination. This thesis also led to the submission of three patents and allowed the development of two software tools presented in Appendix A.

With recent advances and cost reductions in next generation sequencing (NGS), the amount of genetic sequence data is increasing rapidly. However, before patient specific genetic information reaches its full potential to advance clinical diagnostics, the immense degree of genetic heterogeneity that contributes to human disease must be more fully understood. For example, although large numbers of genetic variations are discovered during clinical use of NGS, annotating and understanding the impact of such coding variations on protein phenotype remains a bottleneck (i.e. what is the molecular mechanism behind deafness phenotypes). Fortunately, computational methods are emerging that can be used to efficiently study protein coding variants, and thereby overcome the bottleneck brought on by rapid adoption of clinical sequencing. To study proteins via physics-based computational algorithms, high-quality 3D structural models are essential. These protein models can be obtained using a variety of numerical optimization methods that operate on physics-based potential energy functions. Accurate protein structures serve as input to downstream variation analysis algorithms. In this work, we applied a novel amino acid side-chain optimization algorithm, which operated on an advanced model of atomic interactions (i.e. the AMOEBA polarizable force field), to a set of 164 protein structural models implicated in deafness. The resulting models were evaluated with the MolProbity structure validation tool. MolProbity “scores” were originally calibrated to predict the quality of X-ray diffraction data used to generate a given protein model (i.e. a 1.0 Å or lower MolProbity score indicates a protein model from high quality data, while a score of 4.0 Å or higher reflects relatively poor data). In this work, the side-chain optimization algorithm improved mean MolProbity score from 2.65 Å (42nd percentile) to nearly atomic resolution at 1.41 Å (95th percentile). However, side-chain optimization with the AMOEBA many-body potential function is computationally expensive. Thus, a second contribution of this work is a parallelization scheme that utilizes nVidia graphical processing units (GPUs) to accelerate the side-chain repacking algorithm. With the use of one GPU, our side-chain optimization algorithm achieved a 25 times speed-up compared to using two Intel Xeon E5-2680v4 central processing units (CPUs). We expect the GPU acceleration scheme to lessen demand on computing resources dedicated to protein structure optimization efforts and thereby dramatically expand the number of protein structures available to aid in interpretation of missense variations associated with deafness.

Le problème du suivi d'objets dans une vidéo se pose dans des domaines tels que la vision par ordinateur (vidéo-surveillance par exemple) et la post-production télévisuelle et cinématographique (effets spéciaux). Il se décline en deux variantes principales : le suivi d'une région d'intérêt, qui désigne un suivi grossier d'objet, et la segmentation spatio-temporelle, qui correspond à un suivi précis des contours de l'objet d'intérêt. Dans les deux cas, la région ou l'objet d'intérêt doivent avoir été préalablement détourés sur la première, et éventuellement la dernière, image de la séquence vidéo. Nous proposons dans cette thèse une méthode pour chacun de ces types de suivi ainsi qu'une implémentation rapide tirant partie du Graphics Processing Unit (GPU) d'une méthode de suivi de régions d'intérêt développée par ailleurs. La première méthode repose sur l'analyse de trajectoires temporelles de points saillants et réalise un suivi de régions d'intérêt. Des points saillants (typiquement des lieux de forte courbure des lignes isointensité) sont détectés dans toutes les images de la séquence. Les trajectoires sont construites en liant les points des images successives dont les voisinages sont cohérents. Notre contribution réside premièrement dans l'analyse des trajectoires sur un groupe d'images, ce qui améliore la qualité d'estimation du mouvement. De plus, nous utilisons une pondération spatio-temporelle pour chaque trajectoire qui permet d'ajouter une contrainte temporelle sur le mouvement tout en prenant en compte les déformations géométriques locales de l'objet ignorées par un modèle de mouvement global. La seconde méthode réalise une segmentation spatio-temporelle. Elle repose sur l'estimation du mouvement du contour de l'objet en s'appuyant sur l'information contenue dans une couronne qui s'étend de part et d'autre de ce contour. Cette couronne nous renseigne sur le contraste entre le fond et l'objet dans un contexte local. C'est là notre première contribution. De plus, la mise en correspondance par une mesure de similarité statistique, à savoir l'entropie du résiduel, d'une portion de la couronne et d'une zone de l'image suivante dans la séquence permet d'améliorer le suivi tout en facilitant le choix de la taille optimale de la couronne. Enfin, nous proposons une implémentation rapide d'une méthode de suivi de régions d'intérêt existante. Cette méthode repose sur l'utilisation d'une mesure de similarité statistique : la divergence de Kullback-Leibler. Cette divergence peut être estimée dans un espace de haute dimension à l'aide de multiples calculs de distances au k-ème plus proche voisin dans cet espace. Ces calculs étant très coûteux, nous proposons une implémentation parallèle sur GPU (grâce à l'interface logiciel CUDA de NVIDIA) de la recherche exhaustive des k plus proches voisins. Nous montrons que cette implémentation permet d'accélérer le suivi des objets, jusqu'à un facteur 15 par rapport à une implémentation de cette recherche nécessitant au préalable une structuration des données.

La comparaison de séquences est une des tâches fondamentales de la bioinformatique. Les nouvelles technologies de séquençage conduisent à une production accélérée des données génomiques et renforcent les besoins en outils rapides et efficaces pour effectuer cette tâche. Dans cette thèse, nous proposons un nouvel algorithme de comparaison intensive de séquences, explicitement conçu pour exploiter toutes les formes de parallélisme présentes dans les microprocesseurs de dernière génération (instruction SIMD, architecture multi-coeurs). Cet algorithme s'adapte également à un parallélisme massif que l'on peut trouver sur des accélérateurs de type FPGA ou GPU. Cet algorithme a été mis en oeuvre à travers le logiciel PLAST (Parallel Local Alignment Search Tool). Différentes versions sont disponibles suivant les données à traiter (protéine et/ou ADN). Une version MPI a également été mise au point pour un déploiement sur un cluster de PCs. En fonction de la nature des données et des technologies employées des accélérations de 3 à 20 ont été mesurées par rapport à la référence du domaine, le logiciel BLAST, pour un niveau de qualité équivalent.

Les fonctions de texture directionnelle (« Bidirectional Texture Function » ou BTF) ont rencontré un certain succès ces dernières années dans le contexte de la synthèse d'images en temps-réel grâce à la fois au réalisme qu'elles apportent et au faible coût de calcul nécessaire. Cependant, un inconvénient de cette approche reste la taille gigantesque des données et de nombreuses méthodes ont été proposées afin de les compresser. Dans ce document, nous proposons une nouvelle représentation des BTFs qui améliore la cohérence des données et qui permet ainsi une compression plus efficace de celles-ci. Dans un premier temps, nous étudions les méthodes d'acquisition et de génération des BTFs et plus particulièrement, les méthodes de compression adaptées à une utilisation sur cartes graphiques. Nous réalisons ensuite une étude à l'aide de notre logiciel BTFInspect afin de déterminer parmi les différents phénomènes visuels mesurés dans les BTFs, ceux qui influencent majoritairement la cohérence des données par pixel. Dans un deuxième temps, nous proposons une nouvelle représentation pour les BTFs, appelées « Flat Bidirectional Texture Function » Flat-BTFs, qui améliore la cohérence des données d'une BTF et synthétiques afin de valider sa mise en œuvre. Dans l'analyse des résultats obtenus, nous montrons statistiquement et visuellement le gain de cohérence obtenu ainsi que l'absence d'une perte significative de qualité en comparaison avec la représentation d'origine. Enfin, dans un troisième temps, nous validons l'utilisation de notre nouvelle représentation dans des applications de rendu en temps-réel sur cartes graphiques. Puis, nous proposons une compression de l'apparence grâce à une méthode de quantification adaptée et présentée dans le cadre d'une application de diffusion de données 3D entre un serveur contenant des modèles 3D et un client désirant visualiser ces données.

La complexité visuelle des objets ne réside pas uniquement dans leurs formes, mais également dans l'apparence de leurs surfaces. Les détails de surface ne sont pas nécessaires à la compréhension des<br />formes. Ils sont cependant primordiaux pour enrichir l'aspect visuel des images produites, et répondre aux besoins croissants de réalisme des applications graphiques modernes (jeux vidéos, effets spéciaux,<br />simulateurs).<br />En synthèse d'image, les modèles d'habillage de surface, tels que le placage de texture, sont utilisés conjointement à la représentation des formes pour enrichir l'aspect des objets. Ils permettent de représenter les variations des propriétés du matériau le long de la surface, et ainsi de créer de nombreux détails, allant de fins motifs colorés à des aspects rugueux ou abimés.<br />Cependant, la demande croissante de l'industrie, en terme de richesse, de qualité et de finesse de détails, implique une utilisation des ressources toujours plus grande : quantité de données à stocker, temps et difficulté de création pour les artistes, temps de calcul des images. Les modèles d'habillage de surface actuels, en particulier le placage de texture, ne permettent plus de répondre efficacement à toutes les situations.<br />Nous proposons dans cette thèse de nouveaux modèles d'habillage, qui permettent d'atteindre de très hautes résolutions de détails sur les surfaces, avec peu de mémoire, un temps de création réduit et avec des performances interactives : nous les avons conçus pour les processeurs graphiques programmables récents. Nos approches sont multiples : combinaison semi-automatique de motifs sur la surface, gestion de texture dépendante du point de vue, méthodes basées sur des textures hiérarchiques pour éviter le recours à une paramétrisation planaire globale. Nous proposons également, à titre d'exemple, des applications concrètes de nos modèles d'habillage génériques à des cas difficiles, voire impossibles, à réaliser auparavant.

Même si le docking protéine-protéine devient un outil incontournable pour répondre aux problématiques biologiques actuelles, il reste cependant deux difficultés inhérentes aux méthodes actuelles: 1) la majorité de ces méthodes ne considère pas les possibles déformations internes des protéines durant leur association. 2) Il n'est pas toujours simple de traduire les informations issues de la littérature ou d'expérimentations en contraintes intégrables aux programmes de docking. Nous avons donc tenté de développer une approche permettant d'améliorer les programmes de docking existants. Pour cela nous nous sommes inspirés des méthodologies mises en place sur des cas concrets traités durant cette thèse. D'abord, à travers la création du complexe ERBIN PDZ/Smad3 MH2, nous avons pu tester l'utilité de la Dynamique Moléculaire en Solvant Explicite (DMSE) pour mettre en évidence des résidus importants pour l'interaction. Puis, nous avons étendu cette recherche en utilisant divers serveurs de docking puis la DMSE pour cibler un résultat consensus. Enfin, nous avons essayé le raffinage par DMSE sur une cible du challenge CAPRI et comparé les résultats avec des simulations courtes de Monte-Carlo. La dernière partie de cette thèse portait sur le développement d'un nouvel outil de visualisation de la surface moléculaire. Ce programme, nommé MetaMol, permet de visualiser un nouveau type de surface moléculaire: la Skin Surface Moléculaire. La distribution des calculs à la fois sur le processeur de l'ordinateur (CPU) et sur ceux de la carte graphique (GPU) entraine une diminution des temps de calcul autorisant la visualisation, en temps réel, des déformations de la surface moléculaire.