Comparação paralela de sequências biológicas em múltiplas GPUs com descarte de blocos e estratégias de distribuição de carga

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).