Masa-StarPU : estratégia com múltiplas políticas de escalonamento de tarefas para alinhamento de sequências com pruning

Abstract

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 utilizam aceleradores como GPUs e FPGAs, porém poucas soluções utilizam apenas CPUs. O MASA é uma ferramenta multiplataforma específica para realizar a comparação de sequências biológicas. Uma de suas maiores virtudes é a otimização block pruning que realiza a poda da matriz de programação dinâmica em tempo de execução acelerando o processamento, porém introduzindo um problema de desbalanceamento de carga. O StarPU é uma ferramenta de programação paralela que possui implementações de diversas políticas de escalonamento dinâmico de tarefas. Neste trabalho, propomos e avaliamos o MASA-StarPU, uma ferramenta que utiliza a estrutura do MASA para realizar a comparação de sequências biológicas e as políticas do StarPU adequadas ao block pruning com o objetivo de eliminar o problema de desbalanceamento de carga. O MASA-StarPU foi testado em dois ambientes, 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), e as políticas de escalonamento de tarefas foram avaliadas em diferentes casos. Quando comparado com outras soluções da literatura que utilizam apenas CPU, o MASA-StarPU obteve o melhor resultado para todas as comparações. O MASA-StarPU atingiu o máximo de 18,4 GCUPS (bilhões de células atualizadas por segundo).