Tese (doutorado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-01-21T13:09:08Z No. of bitstreams: 1 2015_EdansFlaviusOliveiraSandes.pdf: 8651626 bytes, checksum: eb6970a8085ba3a4dc141481620451c6 (MD5) / Approved for entry into archive by Patrícia Nunes da Silva(patricia@bce.unb.br) on 2016-05-15T13:57:40Z (GMT) No. of bitstreams: 1 2015_EdansFlaviusOliveiraSandes.pdf: 8651626 bytes, checksum: eb6970a8085ba3a4dc141481620451c6 (MD5) / Made available in DSpace on 2016-05-15T13:57:40Z (GMT). No. of bitstreams: 1 2015_EdansFlaviusOliveiraSandes.pdf: 8651626 bytes, checksum: eb6970a8085ba3a4dc141481620451c6 (MD5) / O alinhamento de sequências biológicas é uma das operações mais importantes em Bioinformática, sendo executado milhares de vezes a cada dia ao redor do mundo. Os algoritmos exatos existentes para este fim possuem complexidade quadrática de tempo. Logo, quando a comparação é realizada com sequências muito longas, tais como no escopo do genoma humano, matrizes na ordem de petabytes devem ser calculadas, algo considerado inviável pela maioria dos pesquisadores. O principal objetivo desta tese de Doutorado é propor e avaliar algoritmos e otimizações que permitam que o alinhamento ótimo de sequências muito longas de DNA seja obtido em tempo reduzido em plataformas de alto desempenho. Os algoritmos propostos utilizam técnicas paralelas de dividir e conquistar com complexidade de memória reduzida mantendo a complexidade quadrática do tempo de execução. O CUDAlign, em suas versões 2.0, 2.1, 3.0 e 4.0, é a principal contribuição desta tese, onde os algoritmos propostos estão integrados na mesma ferramenta, permitindo a recuperação eficiente do alinhamento ótimo entre duas sequências longas de DNA em múltiplas GPUs (Graphics Processing Unit) da NVIDIA. As otimizações propostas neste trabalho permitem que o nível máximo de paralelismo seja mantido durante quase todo o processamento. No cálculo do alinhamento em uma GPU, as otimizações Orthogonal Execution, Balanced Partition e Block Pruning foram propostas, aumentando o desempenho no cálculo da matriz e descartando áreas que não contribuem para o alinhamento ótimo. A análise formal do Block Pruning mostra que sua eficácia depende de vários fatores, tais como a similaridade entre as sequências e a forma de processamento da matriz. No cálculo do alinhamento com várias GPUs, a otimização Incremental Speculative Traceback é proposta para acelerar a obtenção do alinhamento utilizando valores especulados com alta taxa de acerto. Também são propostos métodos de balanceamento dinâmico de carga que se mostraram eficientes em ambientes simulados. A arquitetura de software chamada de Multi-Platform Architecture for Sequence Aligners (MASA) foi proposta para facilitar a portabilidade do CUDAlign para diferentes plataformas de hardware ou software. Com esta arquitetura, foi possível portar o CUDAlign para plataformas de hardware como CPUs e Intel Phi e utilizando plataformas de software como OpenMP e OmpSs. Nesta tese, sequências reais são utilizadas para validar a eficácia dos algoritmos e otimizações nas várias arquiteturas suportadas. Por meio do desempenho das ferramentas implementadas, avançou-se o estado da arte para permitir o alinhamento, em tempo viável, de todos os cromossomos homólogos do homem e do chimpanzé, utilizando algoritmos exatos de comparação de sequências com um desempenho de até 10,35 TCUPS (Trilhões de Células Atualizadas por Segundo). Até onde sabemos, esta foi a primeira vez que tal tipo de comparação foi realizada com métodos exatos. / Biological sequence alignment is one of the most important operations in Bioinformatics, executing thousands of times every day around the world. The exact algorithms for this purpose have quadratic time complexity. So when the comparison involves very long sequences, such as in the human genome, matrices with petabytes must be calculated, and this is still considered unfeasible by most researchers. The main objective of this Thesis is to propose and evaluate algorithms and optimizations that produce the optimal alignment of very long DNA sequences in a short time using high-performance computing platforms. The proposed algorithms use parallel divide-and-conquer techniques with reduced memory complexity, whilst with quadratic time complexity. CUDAlign, in its versions 2.0, 2.1, 3.0 and 4.0, is the main contribution of this Thesis. The proposed algorithms are integrated into the same tool, allowing efficient retrieval of the optimal alignment between two long DNA sequences using multiple GPUs (Graphics Processing Unit) from NVIDIA. The proposed optimizations maintain the maximum parallelism during most of the processing time. To accelerate the matrix calculation in a single GPU, the Orthogonal Execution, Balanced Partition and Block Pruning optimizations were proposed, increasing the performance of the matrix computation and discarding areas that do not contribute to the optimal alignment. The formal analysis of Block Pruning shows that its effectiveness depends on factors such as the sequences similarity and the matrix processing order. During the alignment computation with multiple GPUs, the Incremental Speculative Traceback optimization is proposed to accelerate the alignment retrieval, using speculated values with high accuracy rate. A dynamic load balancing method has also been proposed and its effectiveness has been shown in simulated environments. Finally, the software architecture called Multi-Platform Architecture for Sequence aligners (MASA) was proposed to simplify the portability of CUDAlign to different hardware and software platforms. With this architecture, it was possible to port CUDAlign to hardware platforms such as CPU and Intel Phi, and using software platforms such as OpenMP and OmpSs. In this Thesis, real sequences are used to validate the effectiveness of the proposed algorithms and optimizations in several supported architectures. Our proposed tools were able to advance the state-of-the-art of sequence alignment algorithms, allowing a fast retrieval of all human and chimpanzee homologous chromosomes, using exact algorithms at an unprecedented rate of up to 10.35 TCUPS (Trillions of Cells Updated Per Second). As far as we know, this was the first time that this type of comparison was carried out with exact sequence comparison algorithms.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015. / Submitted by Raquel Viana (raquelviana@bce.unb.br) on 2016-02-04T15:52:54Z No. of bitstreams: 1 2015_MarcoAntônioCaldasdeFigueirêdoJúnior.pdf: 2211162 bytes, checksum: 999b7a9af378fd239a06877f9dbd003b (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-02-04T15:56:38Z (GMT) No. of bitstreams: 1 2015_MarcoAntônioCaldasdeFigueirêdoJúnior.pdf: 2211162 bytes, checksum: 999b7a9af378fd239a06877f9dbd003b (MD5) / Made available in DSpace on 2016-02-04T15:56:38Z (GMT). No. of bitstreams: 1 2015_MarcoAntônioCaldasdeFigueirêdoJúnior.pdf: 2211162 bytes, checksum: 999b7a9af378fd239a06877f9dbd003b (MD5) / A comparação de sequências biológicas é uma tarefa importante executada com frequência na análise genética de organismos. Algoritmos que realizam este procedimento utilizando um método exato possuem complexidade quadrática de tempo, demandando alto poder computacional e uso de técnicas de paralelização. Muitas soluções têm sido propostas para tratar este problema em GPUs, mas a maioria delas são implementadas em CUDA, restringindo sua execução a GPUs NVidia. Neste trabalho, propomos e avaliamos o MASA-OpenCL, solução desenvolvida em OpenCL capaz de executar a comparação paralela de sequências biológicas em plataformas heterogêneas de computação. O MASA-OpenCL foi testado em diferentes modelos de CPUs e GPUs, avaliando pares de sequências de DNA cujos tamanhos variam entre 10 KBP (milhares de pares de bases) e 47 MBP (milhões de pares de bases), com desempenho superior a outras soluções existentes baseadas em CUDA. A solução obteve um máximo de 179,2 GCUPS (bilhões de células atualizadas por segundo) em uma GPU AMD R9 280X. Até onde temos conhecimento, esta é única solução implementada em OpenCL que realiza a comparação de sequências longas de DNA, e o desempenho alcançado é, até o momento, o melhor já obtido com uma única GPU. ______________________________________________________________________________________________ ABSTRACT / The comparison of biological sequences is an important task performed frequently in the genetic analysis of organisms. Algorithms that perform biological comparison using an exact method require quadratic time complexity, demanding high computational power and use of parallelization techniques. Many solutions have been proposed to address this problem on GPUs, but most of them are implemented in CUDA, restricting its execution to NVidia GPUs. In this work, we propose and evaluate MASA-OpenCL, which is developed in OpenCL and capable of performing parallel comparison of biological sequences in heterogeneous computing platforms. The application was tested in different families of CPUs and GPUs, evaluating pairs of DNA sequences whose sizes range between 10 KBP (thousands of base pairs) and 47 MBP (millions of base pairs) with superior performance to other existing solutions based on CUDA. Our solution achieved a maximum of 179.2 GCUPS (billions of cells updated per second) on an AMD R9 280X GPU. As far as we know, this is the only solution implemented in OpenCL that performs long DNA sequence comparison, and the achieved performance is, so far, the best ever obtained on a single GPU.

Orientador: Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC. Programa de Pós-Graduação em Ciências da Computação, 2013

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2012. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2013-04-11T12:42:16Z No. of bitstreams: 1 2012_DanielSundfeldLima.pdf: 2274332 bytes, checksum: 03f64cd52764929edc5ad78619656562 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-05-20T14:40:19Z (GMT) No. of bitstreams: 1 2012_DanielSundfeldLima.pdf: 2274332 bytes, checksum: 03f64cd52764929edc5ad78619656562 (MD5) / Made available in DSpace on 2013-05-20T14:40:19Z (GMT). No. of bitstreams: 1 2012_DanielSundfeldLima.pdf: 2274332 bytes, checksum: 03f64cd52764929edc5ad78619656562 (MD5) / O alinhamento múltiplo de sequências biológicas é um problema muito importante em Biologia Molecular, pois permite que sejam detectadas similaridades e diferenças entre um conjunto de sequências. Esse problema foi provado NP-Difícil e, por essa razão, geralmente algoritmos heurísticos são usados para resolvê-lo. No entanto, a obtenção da solucão ótima é bastante desejada e, por essa razão, existem alguns algoritmos exatos que solucionam esse problema para um número reduzido de sequências. Dentre esses algoritmos, destaca-se o método exato Carrillo-Lipman, que permite reduzir o espaço de busca utilizando um limite inferior e superior. Mesmo com essa redução, o algoritmo com Carrillo-Lipman executa-se em tempo exponencial. Com o objetivo de acelerar a obtenção de resultados, plataformas computacionais de alto desempenho podem ser utilizadas para resolver o problema do alinhamento múltiplo. Dentre essas plataformas, destacam-se as Unidades de Processamento Gráfico (GPU) devido ao seu potencial para paralelismo massivo e baixo custo. O objetivo dessa dissertação de mestrado é propor e avaliar uma estratégia paralela para execução do algoritmo Carrillo-Lipman em GPU. A nossa estratégia permite a exploração do paralelismo em granularidade na, onde o espaço de busca é percorrido por várias threads em um cubo tridimensional, divido em janelas de processamento que são diagonais projetadas em duas dimensões. Os resultados obtidos com a comparação de conjuntos de 3 sequências reais e sintéticas de diversos tamanhos mostram que speedups de até 8,60x podem ser atingidos com a nossa estratégia. ______________________________________________________________________________ ABSTRACT / Multiple Sequence Alignment is a very important problem in Molecular Biology since it is able to detect similarities and di erences in a set of sequences. This problem has been proven NP-Hard and, for this reason, heuristic algorithms are usually used to solve it. Nevertheless, obtaining the optimal solution is highly desirable and there are indeed some exact algorithms that solve this problemfor a reduced number of sequences. Carrillo-Lipman is a well-known exact algorithmfor the Multiple Sequence Alignment problemthat is able to reduce the search space by using inferior and superior bounds. Even with this reduction, the Carrillo-Lipman algorithm executes in exponential time. High Performance Computing (HPC) Platforms can be used in order to produce results faster. Among the existing HPC platforms, GPUs (Graphics Processing Units) are receiving a lot of attention due to their massive parallelism and low cost. The goal of this MsC dissertation is to propose and evaluate a parallel strategy to execute the Carrillo-Lipman algorithm in GPU. Our strategy explores parallelism at ne granularity, where the search space is a tridimensional cube, divided on processing windows with bidimensional diagonals, explored by multiple threads. The results obtained when comparing several sets of 3 real and synthetic sequences show that speedups of 8.60x can be obtained with our strategy.

The parallel and distributed platforms of High Performance Computing available today have became more and more heterogeneous (CPUs, GPUs, FPGAs, etc). Graphics Processing Units (GPU) are specialized co-processor to accelerate and improve the performance of parallel vector operations. GPUs have a high degree of parallelism and can execute thousands or millions of threads concurrently and hide the latency of the scheduler. GPUs have a deep hierarchical memory of different types as well as different configurations of these memories. Performance prediction of applications executed on these devices is a great challenge and is essential for the efficient use of resources in machines with these co-processors. There are different approaches for these predictions, such as analytical modeling and machine learning techniques. In this thesis, we present an analysis and characterization of the performance of applications executed on GPUs. We propose a simple and intuitive BSP-based model for predicting the CUDA application execution times on different GPUs. The model is based on the number of computations and memory accesses of the GPU, with additional information on cache usage obtained from profiling. We also compare three different Machine Learning (ML) approaches: Linear Regression, Support Vector Machines and Random Forests with BSP-based analytical model. This comparison is made in two contexts, first, data input or features for ML techniques were the same than analytical model, and, second, using a process of feature extraction, using correlation analysis and hierarchical clustering. We show that GPU applications that scale regularly can be predicted with simple analytical models, and an adjusting parameter. This parameter can be used to predict these applications in other GPUs. We also demonstrate that ML approaches provide reasonable predictions for different cases and ML techniques required no detailed knowledge of application code, hardware characteristics or explicit modeling. Consequently, whenever a large data set with information about similar applications are available or it can be created, ML techniques can be useful for deploying automated on-line performance prediction for scheduling applications on heterogeneous architectures with GPUs. / As plataformas paralelas e distribuídas de computação de alto desempenho disponíveis hoje se tornaram mais e mais heterogêneas (CPUs, GPUs, FPGAs, etc). As Unidades de processamento gráfico são co-processadores especializados para acelerar operações vetoriais em paralelo. As GPUs têm um alto grau de paralelismo e conseguem executar milhares ou milhões de threads concorrentemente e ocultar a latência do escalonador. Elas têm uma profunda hierarquia de memória de diferentes tipos e também uma profunda configuração da memória hierárquica. A predição de desempenho de aplicações executadas nesses dispositivos é um grande desafio e é essencial para o uso eficiente dos recursos computacionais de máquinas com esses co-processadores. Existem diferentes abordagens para fazer essa predição, como técnicas de modelagem analítica e aprendizado de máquina. Nesta tese, nós apresentamos uma análise e caracterização do desempenho de aplicações executadas em Unidades de Processamento Gráfico de propósito geral. Nós propomos um modelo simples e intuitivo fundamentado no modelo BSP para predizer a execução de funções kernels de CUDA sobre diferentes GPUs. O modelo está baseado no número de computações e acessos à memória da GPU, com informação adicional do uso das memórias cachês obtidas do processo de profiling. Nós também comparamos três diferentes enfoques de aprendizado de máquina (ML): Regressão Linear, Máquinas de Vetores de Suporte e Florestas Aleatórias com o nosso modelo analítico proposto. Esta comparação é feita em dois diferentes contextos, primeiro, dados de entrada ou features para as técnicas de aprendizado de máquinas eram as mesmas que no modelo analítico, e, segundo, usando um processo de extração de features, usando análise de correlação e clustering hierarquizado. Nós mostramos que aplicações executadas em GPUs que escalam regularmente podem ser preditas com modelos analíticos simples e um parâmetro de ajuste. Esse parâmetro pode ser usado para predizer essas aplicações em outras GPUs. Nós também demonstramos que abordagens de ML proveem predições aceitáveis para diferentes casos e essas abordagens não exigem um conhecimento detalhado do código da aplicação, características de hardware ou modelagens explícita. Consequentemente, sempre e quando um banco de dados com informação de \\textit esteja disponível ou possa ser gerado, técnicas de ML podem ser úteis para aplicar uma predição automatizada de desempenho para escalonadores de aplicações em arquiteturas heterogêneas contendo GPUs.

The parallel and distributed platforms of High Performance Computing available today have became more and more heterogeneous (CPUs, GPUs, FPGAs, etc). Graphics Processing Units (GPU) are specialized co-processor to accelerate and improve the performance of parallel vector operations. GPUs have a high degree of parallelism and can execute thousands or millions of threads concurrently and hide the latency of the scheduler. GPUs have a deep hierarchical memory of different types as well as different configurations of these memories. Performance prediction of applications executed on these devices is a great challenge and is essential for the efficient use of resources in machines with these co-processors. There are different approaches for these predictions, such as analytical modeling and machine learning techniques. In this thesis, we present an analysis and characterization of the performance of applications executed on GPUs. We propose a simple and intuitive BSP-based model for predicting the CUDA application execution times on different GPUs. The model is based on the number of computations and memory accesses of the GPU, with additional information on cache usage obtained from profiling. We also compare three different Machine Learning (ML) approaches: Linear Regression, Support Vector Machines and Random Forests with BSP-based analytical model. This comparison is made in two contexts, first, data input or features for ML techniques were the same than analytical model, and, second, using a process of feature extraction, using correlation analysis and hierarchical clustering. We show that GPU applications that scale regularly can be predicted with simple analytical models, and an adjusting parameter. This parameter can be used to predict these applications in other GPUs. We also demonstrate that ML approaches provide reasonable predictions for different cases and ML techniques required no detailed knowledge of application code, hardware characteristics or explicit modeling. Consequently, whenever a large data set with information about similar applications are available or it can be created, ML techniques can be useful for deploying automated on-line performance prediction for scheduling applications on heterogeneous architectures with GPUs. / As plataformas paralelas e distribuídas de computação de alto desempenho disponíveis hoje se tornaram mais e mais heterogêneas (CPUs, GPUs, FPGAs, etc). As Unidades de processamento gráfico são co-processadores especializados para acelerar operações vetoriais em paralelo. As GPUs têm um alto grau de paralelismo e conseguem executar milhares ou milhões de threads concorrentemente e ocultar a latência do escalonador. Elas têm uma profunda hierarquia de memória de diferentes tipos e também uma profunda configuração da memória hierárquica. A predição de desempenho de aplicações executadas nesses dispositivos é um grande desafio e é essencial para o uso eficiente dos recursos computacionais de máquinas com esses co-processadores. Existem diferentes abordagens para fazer essa predição, como técnicas de modelagem analítica e aprendizado de máquina. Nesta tese, nós apresentamos uma análise e caracterização do desempenho de aplicações executadas em Unidades de Processamento Gráfico de propósito geral. Nós propomos um modelo simples e intuitivo fundamentado no modelo BSP para predizer a execução de funções kernels de CUDA sobre diferentes GPUs. O modelo está baseado no número de computações e acessos à memória da GPU, com informação adicional do uso das memórias cachês obtidas do processo de profiling. Nós também comparamos três diferentes enfoques de aprendizado de máquina (ML): Regressão Linear, Máquinas de Vetores de Suporte e Florestas Aleatórias com o nosso modelo analítico proposto. Esta comparação é feita em dois diferentes contextos, primeiro, dados de entrada ou features para as técnicas de aprendizado de máquinas eram as mesmas que no modelo analítico, e, segundo, usando um processo de extração de features, usando análise de correlação e clustering hierarquizado. Nós mostramos que aplicações executadas em GPUs que escalam regularmente podem ser preditas com modelos analíticos simples e um parâmetro de ajuste. Esse parâmetro pode ser usado para predizer essas aplicações em outras GPUs. Nós também demonstramos que abordagens de ML proveem predições aceitáveis para diferentes casos e essas abordagens não exigem um conhecimento detalhado do código da aplicação, características de hardware ou modelagens explícita. Consequentemente, sempre e quando um banco de dados com informação de \\textit esteja disponível ou possa ser gerado, técnicas de ML podem ser úteis para aplicar uma predição automatizada de desempenho para escalonadores de aplicações em arquiteturas heterogêneas contendo GPUs.