Título: | Alinhamento múltiplo de sequências com A-Star paralelo em cluster MPI |
Autor(es): | Ferreira, Gabriel de C. |
Orientador(es): | Melo, Alba Cristina Magalhães Alves de |
Assunto: | Alinhamento Múltiplo de Sequências (MSA) Algoritmos de computador Processamento paralelo (Computadores) |
Data de apresentação: | 8-Ago-2016 |
Data de publicação: | 18-Jan-2017 |
Referência: | FERREIRA, Gabriel de C. Alinhamento múltiplo de sequências com A-Star paralelo em cluster MPI. 2016. xi, 75 f., il. Trabalho de conclusão de curso (Bacharelado em Ciência da Computação)—Universidade de Brasília, Brasília, 2016. |
Resumo: | O alinhamento múltiplo de sequências visa ressaltar as similaridades e diferenças em
um conjunto de sequências biológicas. O alinhamento múltiplo com a soma de pares é
um problema NP-Difícil e métodos heurísticos são usados para solucioná-lo, porém esses
métodos não garantem que o resultado ótimo será produzido. Algumas das técnicas exatas
que produzem o resultado ótimo são baseadas no algoritmo de busca A-Star, sendo
uma delas o A-Star Paralelo (PA-Star). O PA-Star divide o espaço de busca entre múltiplas
threads, acelerando a obtenção de resultados, contudo tem sua execução limitada a
uma única máquina. O objetivo deste trabalho de graduação é propor, implementar e
avaliar o MPI-PAStar, uma estratégia que permita reduzir o tempo de busca ao executar
o PA-Star em diversas máquinas, utilizando o ambiente MPI para trocar mensagens, distribuindo
carga de trabalho entre as máquinas. O MPI-PAStar adiciona ao PA-Star um
pool de threads de processamento de mensagens e duas threads responsáveis pelo envio
e recebimento de mensagens. Diversas estratégias são utilizadas para reduzir o tráfego
de dados e a latência de rede, como a serialização de blocos de carga de trabalho e compactação
destes antes do envio, reduzindo efeitos colaterais negativos da rede sobre a
computação do alinhamento. Os resultados do MPI-PAStar apresentaram ganhos de até
36.8% no tempo de busca do alinhamento ótimo e de até 29,7% no tempo total de execução
do programa, quando comparado ao PA-Star, a depender do número e similaridade
das sequências sendo alinhadas, além do comprimento da maior sequência. |
Abstract: | The multiple sequence alignment purpose is to highlight similarities and differences
between a set of biological sequences. The multiple alignment is an NP-Hard problem and
heuristic methods are used to solve it, however those do not guarantee that an optimal
result is produced. Some exact techniques that can produce an optimal result are based
on the A-Star graph search algorithm, being one of them the Parallel A-Star (PA-Star).
The PA-Star divides the search space to multiple threads, accelerating the search for the
result, but its execution is limited to a single machine. The objective of this undergraduate
work is to propose, implement and evaluate the MPI-PAStar, a strategy that allows the
reduction of the search time by executing the PA-Star on multiple machines, using the MPI
environment to exchange messages, distributing the workload across different machines.
The MPI-PAStar adds to PA-Star a pool of message processing threads and two threads
responsible for sending and receiving messages. Multiple strategies are used to reduce
network traffic and latency, like serialized workload blocks and compressing them before
sending them, reducing negative network effects over the alignment computation. Results
obtained with the MPI-PAStar showed that it can yield up to 36.8% reduction in terms
of alignment time and up to 29.7% in terms of total execution time, depending on the
number of sequences being aligned, the length of longest sequence and the content of the
sequences. |
Informações adicionais: | Trabalho de conclusão de curso (graduação)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2016. |
Aparece na Coleção: | Ciência da Computação
|