Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.unb.br/handle/10482/41495
Files in This Item:
File Description SizeFormat 
2021_MarcoAntônioCaldasdeFigueirêdoJúnior.pdf6,41 MBAdobe PDFView/Open
Title: Comparação paralela de sequências biológicas em múltiplas GPUs com descarte de blocos e estratégias de distribuição de carga
Authors: Figueirêdo Júnior, Marco Antônio Caldas de
Orientador(es):: Melo, Alba Cristina Magalhães Alves de
Assunto:: Bioinformática
Sequências biológicas
Descarte de células
Distribuição de carga
Issue Date: 26-Jul-2021
Citation: FIGUEIRÊDO JÚNIOR, Marco Antônio Caldas de. Comparação paralela de sequências biológicas em múltiplas GPUs com descarte de blocos e estratégias de distribuição de carga. 2021. 153 f., il. Tese (Doutorado em Informática)—Universidade de Brasília, Brasília, 2021.
Abstract: A comparação de sequências biológicas é um problema bastante importante em Bioinformática. A utilização de métodos exatos para a solução deste problema requer um alto poder computacional, sobretudo quando duas sequências biológicas longas são comparadas. Para acelerar a obtenção de resultados, diversas estratégias têm sido propostas na literatura, envolvendo o processamento paralelo usando diversos dispositivos ou modificações nos algoritmos. Uma técnica de modificação do algoritmo aplicada com certa frequência em comparações que usam um único dispositivo é a poda da matriz de programação dinâmica, que reduz bastante o espaço de computação quando as sequências comparadas são similares. Ao nosso conhecimento, até o desenvolvimento da presente Tese, só havia uma solução que aplicava técnica de poda para múltiplos dispositivos. No entanto, essa solução usava somente duas GPUs (Graphics Processing Units), com distribuição estática básica de carga. O principal objetivo da presente Tese de Doutorado é investigar o uso de processamento paralelo em conjunto com estratégia de poda, visando acelerar a execução de soluções de comparação de sequências biológicas longas. Para atingir esse objetivo, inicialmente fizemos o estudo estatístico de duas soluções em uma única GPU com descarte de blocos, para estimar o tempo de execução das comparações. A seguir, avaliamos soluções em ambientes heterogêneos e híbridos com descarte de blocos para determinar o impacto da poda no balanceamento da execução. Com base nesses estudos, propusemos uma estratégia leve de distribuição estática de carga (StaticMultiBP), que aplica o descarte de blocos em conjunto com a comunicação periódica do melhor escore entre as GPUs. Para ambientes heterogêneos de GPUs e para comparações entre sequências bastante similares, propusemos uma estratégia de distribuição dinâmica de carga (Dynamic-MultiBP), que divide a computação da matriz em diversas partes (ciclos) e, ao final da computação de cada ciclo, reavalia a distribuição de carga e a modifica, caso não esteja apropriada. Por fim, propusemos um módulo flexível de decisão que pode ser usado para decidir entre as duas estratégias. O Static-MultiBP, o Dynamic-MultiBP e o módulo de decisão foram integrados em um único framework, chamado MultiBP. O MultiBP foi integrado à ferramenta MASA-CUDAlign, que representa o estado da arte em ferramentas de comparação de sequências em GPU. As estratégias MultiBP foram executadas em diversos ambientes, sendo obtidos ganhos expressivos em comparação ao MASA-CUDAlign original. Finalmente, executamos o Static-MultiBP em um grande cluster de GPUs NVidia Volta (512 V100), obtendo o impressionante desempenho de 82,82 TCUPS (Trillions of matrix Cells Updated Per Second). A nosso conhecimento, este é o melhor desempenho na literatura de ferramentas de comparação de sequências em GPU que usam o algoritmo Smith- Waterman e suas variantes, e o melhor desempenho entre ferramentas que comparam sequências longas (em qualquer dispositivo).
Abstract: Biological sequence alignment is a very important problem in Bioinformatics. The use of exact methods to solve this problem requires high computational power, especially if two long biological sequences are compared. To speed up results, several strategies have been proposed in the literature, involving the parallel processing using several devices or algorithm modifications. A technique frequently applied in the algorithms used to compare sequences in one device is the pruning of the dynamic programming matrix, which reduces the computation space when the compared sequences are similar. To our knowledge, until the development of this Thesis, there was only solution that used the pruning technique in multiple devices. However, this solution used only two GPUs (Graphics Processing Units), with basic static load distribution. The main objective of this PhD Thesis is to investigate the use of parallel processing in conjunction with pruning strategies, aiming to accelerate the execution of long biological sequences comparison. To achieve this objective, initially we did a statistical study of two solutions in a single GPU with block pruning, to estimate the execution time of the comparisons. Next, we evaluated solutions on heterogeneous and hybrid environments with block pruning to investigate the impact of pruning on the execution balance. Based on these studies, we proposed a lightweight static load distribution strategy (Static-MultiBP), which applies block pruning together with the periodic communication of the best score among the GPUs. For heterogeneous GPU environments and for comparisons between very similar sequences, we proposed a dynamic load distribution strategy (Dynamic-MultiBP), which divides the matrix computation into several parts (cycles) and, at the end of the computation of each cycle, reevaluates the load distribution and modifies it, if not appropriate. Finally, we proposed a flexible decision module that can be used to decide which strategy to use. Static-MultiBP, Dynamic-MultiBP and the decision module were integrated into a single framework, called MultiBP. MultiBP was integrated with the MASA-CUDAlign tool, which represents the state-of-the-art in GPU sequence comparison tools. MultiBP strategies were executed in several environments, and significant gains were obtained in comparison to the original MASA-CUDAlign. Finally, we executed Static-MultiBP on a large cluster of NVidia Volta GPUs (512 V100), achieving an impressive performance of 82.82 TCUPS (Trillions of matrix Cells Updated Per Second). To our knowledge, this is the best performance in the literature for sequence comparison tools that use SmithWaterman algorithm and its variants in GPU, and the best performance obtained by tools that compare long sequences (on any device).
Description: Tese (doutorado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2021.
Licença:: A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.
Appears in Collections:CIC - Doutorado em Informática (Teses)

Show full item record Recommend this item " class="statisticsLink btn btn-primary" href="/handle/10482/41495/statistics">



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.