ads:
Evandro Augusto Marucci
Paraleliza¸c˜ao da ferramenta de
alinhamento de seq
¨
uˆencias MUSCLE para
um ambiente distribu´ıdo
S˜ao Jos´e do Rio Preto – SP
Fevereiro / 2009
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Evandro Augusto Marucci
Paraleliza¸c˜ao da ferramenta de
alinhamento de seq
¨
uˆencias MUSCLE para
um ambiente distribu´ıdo
Disserta¸c˜ao apresentada `a Coordena¸c˜ao do
Mestrado em Ciˆencia da Computa¸c˜ao da
UNESP/IBILCE para a obten¸c˜ao do t´ıtulo
de Mestre em Ciˆencia da Computa¸c˜ao
Orientador:
Prof. Dr. Jos´e M´arcio Machado
Mestrado em Ci
ˆ
encia da Computa¸c
˜
ao
Departamento de Ci
ˆ
encias da Computa¸c
˜
ao e Estat
´
ıstica
Instituto de Bioci
ˆ
encias, Letras e Ci
ˆ
encias Exatas
Universidade Estadual Paulista
S˜ao Jos´e do Rio Preto – SP
Fevereiro / 2009
ads:
Dedico esta disserta¸c˜ao `a mem´oria de meu amigo Angelo ’Bozo’ Morato (1985 - 2008)
Agradecimentos
Devo este trabalho a muitas pessoas e institui¸c˜oes, sem aos quais sua realiza¸c˜ao n˜ao
seria poss´ıvel.
Antes de tudo, por´em, dou gra¸cas `a Deus pela felicidade que ele proporciona constante-
mente em minha vida. Por me fazer acreditar no amor e nas pessoas e por me proporcionar
uma paz integral, em momentos de grandes incertezas.
Aos meus pais, Luis e Zez´e, pelo constante amor e suporte em todas as minhas realiza-
¸c˜oes. Ao meu irm˜ao Gustavo pelo seu amor e cuidado, e tamb´em por estar sempre presente.
Aos meus primos, tios e minhas av´os, que sempre me passam um carinho muito grande.
Todo este amor e carinho esteja eu aqui ou h´a milhares de quilˆometros de distˆancia.
Ao meu orientador, Prof. Dr. Jos´e M´arcio Machado, por compartilhar comigo recursos
e pontos de vista essenciais para o meu crescimento pessoal e profissional. Toda a estru-
tura provida por ele foi, sem d´uvida, de suma importˆancia para o desenvolvimento deste
trabalho. Mais do que isto agrade¸co a sua disposi¸c˜ao em me oferecer est´ımulos e inspira-
¸c˜ao, motivando-me a percorrer novos caminhos. Agrade¸co a nossa amizade desenvolvida,
principalmente.
Ao meu grande amigo Geraldo (Bochecha), por al´em de amigo ser um grande parceiro
profissional. Agrade¸co a sua presen¸ca constante na solu¸c˜ao de problemas, dentro e fora do
laborat´orio, e por tudo o que compartilhamos em nossa vida pessoal. Por ter sido a pessoa
mais presente enquanto universit´ario.
Ao Prof. Dr. Yang Shiyou pelo per´ıodo maravilhoso que passei na China. Pelo seu
cuidado e sua generosidade em me oferecer at´e mais do que precisava. Pela confian¸ca em
minhas atitudes e pela liberdade me proporcionada.
Ao Prof. Dr. Aleardo Manacero Jr., por ter me iniciado `a pesquisa e ter me introduzido
Agradecimentos
`a computa¸c˜ao paralela. A base de pesquisa que obtive com ele foi fundamental para o
tranq
¨
uilo andamento deste trabalho.
Aos meus amigos do Brasil, Ivan, S´ergio, Alex, Luizinho, Francˆes, aos amigos do Chuck
Norris, e a todos que, de alguma forma, se divertiram comigo durante este per´ıodo.
Aos meus amigos na China, Forrest, Mayur, Ma Rui, Alisa, Pardo, Michael, Tracey,
meu mais que brother Thiago Lins e meu quase tio Am´erico. Em especial `a minha namorada
Sissi por todo o seu amor.
Ao pessoal do laborat´orio genˆoma pela estrutura f´ısica, em especial `a Helen e ao Ger-
rard.
`
A Helen pela disposi¸c˜ao em prover o cluster para a execu¸c˜ao dos meus primeiros
testes e pelo prazer de trabalhar com uma pessoa simp´atica como ela. Ao Gerrard pela
amizade, pelas garrafas de vinho e por constantemente compartilhar suas hist´orias de vida.
`
A Aline do IFT por me dar acesso ao cluster em S˜ao Paulo, atrav´es do qual tamb´em
pude testar e medir os resultados de meu trabalho.
`
A FAPESP, que durante 24 meses financiou minha pesquisa.
Agrade¸co `a todos profundamente.
I can’t be as confident about computer science as I can about biology. Biology easily has
500 years of exciting problems to work on. It’s at that level.
Donald Knuth
Resumo
Devido a crescente quantidade de dados genˆomicos para compara¸c˜ao, a computa¸c˜ao
paralela est´a se tornando cada vez mais necess´aria para realizar uma das opera¸c˜oes mais
importantes da bioinform´atica, o alinhamento m´ultiplo de seq
¨
uˆencias. Atualmente, muitas
ferramentas computacionais s˜ao utilizadas para resolver alinhamentos e o uso da compu-
ta¸c˜ao paralela est´a se tornando cada vez mais generalizado. Entretanto, embora diferentes
algoritmos paralelos tenham sido desenvolvidos para suportar as pesquisas genˆomicas, mui-
tos deles n˜ao consideram aspectos fundamentais da computa¸c˜ao paralela.
O MUSCLE [1] ´e uma ferramenta que realiza o alinhamento m´ultiplo de seq
¨
uˆencias com
um bom desempenho computacional e resultados biol´ogicos significativamente precisos [2].
Embora os m´etodos utilizados por ele apresentem diferentes vers˜oes paralelas propostas
na literatura, apenas uma vers˜ao paralela do MUSCLE foi proposta [3]. Essa vers˜ao,
entretanto, foi desenvolvida para sistemas de mem´oria compartilhada.
O desenvolvimento de uma vers˜ao paralela do MUSCLE para sistemas distribu´ıdos ´e
importante dado o grande uso desses sistemas em laborat´orios de pesquisa genˆomica. Esta
paraleliza¸c˜ao ´e o foco deste trabalho e ela foi realizada utilizando-se abordagens paralelas
existentes e criando-se novas abordagens. Como resultado, diferentes estrat´egias parale-
las foram propostas. Estas estrat´egias podem ser incorporadas a outras ferramentas de
alinhamento que utilizam, em determinadas etapas, a mesma abordagem seq
¨
uencial.
Em cada m´etodo paralelizado, considerou-se principalmente a eficiˆencia, a escalabili-
dade e a capacidade de atender problemas reais da biologia. Os testes realizados mostram
que, para cada etapa paralela, ao menos uma estrat´egia definida atende bem todos esses
crit´erios. Al´em deste trabalho realizar um paralelismo in´edito, ao viabilizar a execu¸c˜ao da
ferramenta MUSCLE em sistemas distribu´ıdos, os resultados obtidos mostram que as novas
estrat´egias definidas apresentam um desempenho melhor do que as estrat´egias existentes.
Abstract
Due to increasing amount of genetic data for comparison, parallel computing is beco-
ming increasingly necessary to perform one of the most important operations in bioinfor-
matics, the multiple sequence alignments. Nowadays, many software tools are used to solve
sequence alignments and the use of parallel computing is becoming more and more wides-
pread. However, although different parallel algorithms were developed to support genetic
researches, many of them do not consider fundamental aspects of parallel computing.
The MUSCLE [1] is a tool that performs multiple sequence alignments with good
computational performance and biological results significantly precise [2]. Although the
methods used by them have different parallel versions proposed in the literature, only
one parallel version of the MUSCLE tool was proposed [3]. This version, however, was
developed for shared memory systems.
The development of a parallel MUSCLE tool for distributed systems is important given
the wide use of such systems in laboratories of genomic researches. This parallelization
is the aim of this work and it was done using existing parallel approaches and creating
new approaches. Consequently, different parallel strategies have been proposed. These
strategies can be incorporated into other alignment tools that use, in a given stage, the
same sequential approach.
In each parallel method, we considered mainly the efficiency, scalability and ability to
meet real biological problems. The tests show that, for each parallel step, at least one
defined strategy meets all these criteria. In addition to the new MUSCLE parallelization,
enabling it execute in a distributed systems, the results show that the defined strategies
have a better performance than the existing strategies.
Sum´ario
Lista de Figuras
Lista de Tabelas
1 Introdu¸c˜ao p. 17
1.1 Organiza¸c˜ao da disserta¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . p. 19
2 Fundamenta¸c˜ao te´orica do projeto p. 20
2.1 Gen´etica e bioinform´atica . . . . . . . . . . . . . . . . . . . . . . . . . . p. 20
2.1.1 C´odigo Gen´etico: ´acidos nucl´eicos e prote´ınas . . . . . . . . . . . p. 21
2.1.2 Compara¸c˜ao de seq
¨
uˆencias . . . . . . . . . . . . . . . . . . . . . . p. 22
2.2 Alinhamento de seq
¨
uˆencias . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
2.2.1 Alinhamento entre pares de perfis . . . . . . . . . . . . . . . . . . p. 25
2.2.2 Algoritmo progressivo . . . . . . . . . . . . . . . . . . . . . . . . p. 27
2.2.3 Algoritmo iterativo . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27
2.3 A metodologia da ferramenta MUSCLE . . . . . . . . . . . . . . . . . . . p. 28
2.3.1 Funcionamento b´asico . . . . . . . . . . . . . . . . . . . . . . . . p. 28
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE . . . . . . . . . . . . . . . . p. 29
2.4.1 Medidas de similaridades e estimativas de distˆancia . . . . . . . . p. 29
2.4.2 Constru¸c˜ao da ´arvore . . . . . . . . . . . . . . . . . . . . . . . . . p. 33
Sum´ario
2.4.3 Compara¸c˜ao de ´arvores . . . . . . . . . . . . . . . . . . . . . . . . p. 34
2.4.4 Alinhamento entre perfis . . . . . . . . . . . . . . . . . . . . . . . p. 34
2.4.5 Pontua¸c˜ao objetiva . . . . . . . . . . . . . . . . . . . . . . . . . . p. 36
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos . . . . . . . . . p. 37
2.5.1 O modelo tarefa/canal . . . . . . . . . . . . . . . . . . . . . . . . p. 38
2.5.2 Metodologia de projeto de programas paralelos . . . . . . . . . . p. 39
2.5.3 MPI - Message Passage Interface . . . . . . . . . . . . . . . . . . p. 44
2.5.4 Medidas de desempenho . . . . . . . . . . . . . . . . . . . . . . . p. 46
2.6 Abordagens paralelas de alinhamento . . . . . . . . . . . . . . . . . . . . p. 48
2.6.1 CLUSTALW-MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 50
2.6.2 MUSCLE-SMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 50
2.6.3 T´ecnicas paralelas do alinhamento progressivo . . . . . . . . . . . p. 51
2.6.4 T´ecnicas paralelas do alinhamento par-a-par . . . . . . . . . . . . p. 54
3 Detalhamento e desenvolvimento do projeto p. 56
3.1 Paraleliza¸c˜ao do m´etodo de contagem de k-mers . . . . . . . . . . . . . . p. 57
3.2 Paraleliza¸c˜ao do m´etodo da identidade fracional . . . . . . . . . . . . . . p. 59
3.3 Paraleliza¸c˜ao do alinhamento progressivo . . . . . . . . . . . . . . . . . . p. 60
3.3.1 Abordagem com gargalo e solu¸c˜oes . . . . . . . . . . . . . . . . . p. 61
3.3.2 O problema da abordagem existente . . . . . . . . . . . . . . . . p. 61
3.3.3 Estrat´egia baseada na abordagem com gargalo . . . . . . . . . . . p. 63
3.3.4 Novas abordagens paralelas . . . . . . . . . . . . . . . . . . . . . p. 63
3.3.5 Solu¸c˜oes 1 e 2: Escalonar apenas tarefas com dependˆencias em
processos ociosos . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 65
Sum´ario
3.3.6 Solu¸c˜ao 3: Fazer c´opia de todos os dados no processo mestre . . . p. 67
3.3.7 Solu¸c˜ao 4: Criar threads exclusivos para a troca de dados . . . . . p. 70
3.3.8 Considera¸c˜oes sobre as implementa¸c˜oes no segundo est´agio . . . . p. 71
3.4 Paraleliza¸c˜ao do alinhamento par-a-par . . . . . . . . . . . . . . . . . . . p. 73
3.4.1 Estrat´egias implementadas sobre ambas as solu¸c˜oes . . . . . . . . p. 76
3.4.2 O tamanho dos blocos da matriz . . . . . . . . . . . . . . . . . . p. 77
3.5 Paraleliza¸c˜ao do c´alculo da pontua¸c˜ao objetiva . . . . . . . . . . . . . . . p. 77
4 Testes e Resultados p. 79
4.1 Contagem de k-mers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 79
4.2 Identidade fracional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 84
4.3 Alinhamento progressivo . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 87
4.3.1 Compara¸c˜ao entre as estrat´egias . . . . . . . . . . . . . . . . . . . p. 89
4.3.2 O n´ıvel de paralelismo . . . . . . . . . . . . . . . . . . . . . . . . p. 98
4.3.3 A ´arvore filogen´etica e a escalabilidade do algoritmo . . . . . . . . p. 99
4.4 Alinhamento par-a-par . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 102
4.4.1 Compara¸c˜ao entre as estrat´egias . . . . . . . . . . . . . . . . . . . p. 103
5 Conclus˜oes p. 110
5.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 111
Referˆencias Bibliogr´aficas p. 113
Lista de Figuras
2.1 Exemplo de um alinhamento m´ultiplo de seq
¨
uˆencias . . . . . . . . . . . . p. 23
2.2 Armazenamento do perfil em uma matriz . . . . . . . . . . . . . . . . . . p. 26
2.3 Diagrama de fluxo do algoritmo do MUSCLE . . . . . . . . . . . . . . . p. 30
2.4 C´alculo da identidade fracional entre duas seq
¨
uˆencias . . . . . . . . . . . p. 31
2.5 O modelo tarefa/canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 39
2.6 O modelo de passagem de mensagens . . . . . . . . . . . . . . . . . . . . p. 45
2.7 Fluxograma do algoritmo do processo mestre do alinhamento progressivo
paralelo com escalonamento dinˆamico . . . . . . . . . . . . . . . . . . . . p. 52
2.8 Fluxograma do algoritmo do processo escravo do alinhamento progressivo
paralelo com escalonamento dinˆamico . . . . . . . . . . . . . . . . . . . . p. 53
2.9 Mapeamento da ´arvore filogen´etica para a ´arvore de tarefas . . . . . . . . p. 53
2.10 Particionamento da matriz de programa¸c˜ao dinˆamica em trˆes regi˜oes . . p. 54
2.11 Estrat´egia block-based wavefront . . . . . . . . . . . . . . . . . . . . . . p. 55
3.1 Fluxograma do algoritmo paralelo do m´etodo de contagem de k-mers . . . p. 58
3.2 Exemplo de como o c´alculo da matriz de similaridades ´e distribu´ıdo entre
os processos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 59
3.3 Fluxograma do algoritmo paralelo do m´etodo da identidade fracional . . . p. 60
3.4 Exemplo de caso da espera pela execu¸c˜ao de processo de escravo vizinho
para envio de dados dependentes . . . . . . . . . . . . . . . . . . . . . . . p. 62
3.5 Fluxograma do algoritmo do processo mestre da primeira estrat´egia . . . p. 64
Lista de Figuras
3.6 Fluxograma do processo mestre das estrat´egias waitall e waitany . . . . . p. 67
3.7 Fluxograma do processo escravo das estrat´egias waitall e waitany . . . . p. 68
3.8 Fluxograma do algoritmo do processo mestre da estrat´egia sendmaster . . p. 70
3.9 Fluxograma do algoritmo do processo escravo da estrat´egia sendmaster . p. 71
3.10 Fluxograma do algoritmo do processo mestre da estrat´egia com threads . p. 72
3.11 Fluxograma do algoritmo do processo escravo da estrat´egia com threads . p. 73
4.1 Gr´afico de tempo de execu¸c˜ao do algoritmo paralelo de contagem de k-mers
para entradas com seq
¨
uˆencias de aproximadamente 1000 res´ıduos . . . . . p. 80
4.2 Gr´afico de speedup real do algoritmo paralelo de contagem de k-mers para
entradas com seq
¨
uˆencias de aproximadamente 1000 res´ıduos . . . . . . . p. 81
4.3 Gr´afico de tempo de execu¸c˜ao do algoritmo paralelo de contagem de k-mers
para entradas com seq
¨
uˆencias de aproximadamente 50 res´ıduos . . . . . . p. 81
4.4 Gr´afico de speedup real do algoritmo paralelo de contagem de k-mers para
entradas com seq
¨
uˆencias de aproximadamente 50 res´ıduos . . . . . . . . . p. 82
4.5 Gr´afico de compara¸c˜ao do speedup real do algoritmo paralelo de contagem
de k-mers para entradas com 4000 seq
¨
uˆencias de aproximadamente 50 e
1000 res´ıduos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 83
4.6 Percentual de tempo gasto com comunica¸c˜ao e sincronismo do algoritmo
de contagem de k-mers para a entrada com 500 seq
¨
uˆencias de aproxima-
damente 1000 res´ıduos . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 83
4.7 Gr´afico de tempo de execu¸c˜ao do algoritmo paralelo da identidade fracional
para entradas com seq
¨
uˆencias de aproximadamente 1000 res´ıduos . . . . . p. 85
4.8 Gr´afico de tempo de execu¸c˜ao do algoritmo paralelo da identidade fracional
para entradas com seq
¨
uˆencias de aproximadamente 50 res´ıduos . . . . . . p. 86
4.9 Gr´afico de speedup real do algoritmo paralelo da identidade fracional para
entradas com seq
¨
uˆencias de aproximadamente 50 res´ıduos . . . . . . . . . p. 86
Lista de Figuras
4.10 Gr´afico de ganho de desempenho do algoritmo paralelo da identidade fra-
cional para entradas com 4000 seq
¨
uˆencias de aproximadamente 50 e 1000
res´ıduos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 87
4.11 Percentual de tempo gasto com comunica¸c˜ao e sincronismo do algoritmo
paralelo da identidade fracional para a entrada com 500 seq
¨
uˆencias de
aproximadamente 1000 res´ıduos . . . . . . . . . . . . . . . . . . . . . . . p. 88
4.12 Gr´afico de tempo de execu¸c˜ao da estrat´egia com gargalo do alinhamento
progressivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 89
4.13 Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
do alinhamento progressivo com gargalo para a entrada com 500 seq
¨
uˆencias p. 90
4.14 Gr´afico de tempo de execu¸c˜ao da estrat´egia sendmaster . . . . . . . . . . p. 90
4.15 Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
sendmaster para a entrada com 500 seq
¨
uˆencias . . . . . . . . . . . . . . . p. 91
4.16 Gr´afico de tempo de execu¸c˜ao da estrat´egia waitall . . . . . . . . . . . . . p. 92
4.17 Gr´afico de tempo de execu¸c˜ao da estrat´egia waitany . . . . . . . . . . . . p. 92
4.18 Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
waitall para a entrada com 500 seq
¨
uˆencias . . . . . . . . . . . . . . . . . p. 93
4.19 Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
waitany para a entrada com 500 seq
¨
uˆencias . . . . . . . . . . . . . . . . . p. 93
4.20 Gr´afico de tempo de execu¸c˜ao da estrat´egia com threads . . . . . . . . . p. 94
4.21 Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
com threads para a entrada com 500 seq
¨
uˆencias . . . . . . . . . . . . . . p. 94
4.22 Compara¸c˜ao do tempo de execu¸c˜ao das estrat´egias paralelas do alinha-
mento progressivo para a entrada com 500 seq
¨
uˆencias . . . . . . . . . . . p. 95
4.23 Compara¸c˜ao dos speedups reais das estrat´egias paralelas do alinhamento
progressivo para a entrada com 500 seq
¨
uˆencias . . . . . . . . . . . . . . . p. 95
Lista de Figuras
4.24 Compara¸c˜ao do ganho de desempenho das estrat´egias paralelas do alinha-
mento progressivo para a entrada com 2000 seq
¨
uˆencias . . . . . . . . . . p. 96
4.25 Compara¸c˜ao do ganho de desempenho da estrat´egia com threads para as
entradas com 500, 1000, 2000 e 4000 seq
¨
uˆencias . . . . . . . . . . . . . . p. 97
4.26 Compara¸c˜ao do tempo de execu¸c˜ao da estrat´egia com threads com a ´arvore
balanceada e a ´arvore normal para a entrada com 1000 seq
¨
uˆencias . . . . p. 100
4.27 Compara¸c˜ao do speedup real da estrat´egia com threads com a ´arvore ba-
lanceada e a ´arvore normal para a entradas com 1000 seq
¨
uˆencias . . . . . p. 101
4.28 Perfil da execu¸c˜ao em trˆes n´os da estrat´egia que envia os dados ap´os todos
serem computados para uma entrada de duas seq
¨
uˆencias de aproximada-
mente 1000 res´ıduos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 104
4.29 Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
que envia dados ap´os todos serem computados para uma entrada de cinco
seq
¨
uˆencias de aproximadamente 3000 res´ıduos . . . . . . . . . . . . . . . p. 104
4.30 Perfil da execu¸c˜ao em trˆes n´os da estrat´egia que envia dados em partes
para uma entrada de duas seq
¨
uˆencias de aproximadamente 1000 res´ıduos p. 105
4.31 Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
que envia dados em peda¸cos para uma entrada de cinco seq
¨
uˆencias de
aproximadamente 3000 res´ıduos . . . . . . . . . . . . . . . . . . . . . . . p. 105
4.32 Perfil da execu¸c˜ao em trˆes n´os da estrat´egia que paraleliza o m´etodo de
constru¸c˜ao do caminho de alinhamento para uma entrada de duas seq
¨
uˆen-
cias de aproximadamente 1000 res´ıduos . . . . . . . . . . . . . . . . . . . p. 106
4.33 Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
que paraleliza o m´etodo de constru¸c˜ao do caminho de alinhamento para
uma entrada de cinco seq
¨
uˆencias de aproximadamente 3000 res´ıduos . . . p. 107
4.34 Compara¸c˜ao do tempo de execu¸c˜ao das trˆes estrat´egias paralelas do ali-
nhamento par-a-par para entradas com sequencias de aproximadamente
1000 res´ıduos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 107
Lista de Figuras
4.35 Compara¸c˜ao do tempo de execu¸c˜ao das trˆes estrat´egias paralelas do ali-
nhamento par-a-par para entradas com seq
¨
uˆencias de aproximadamente
5000 res´ıduos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 108
4.36 Compara¸c˜ao do speedup real da estrat´egia que paraleliza o m´etodo de cons-
tru¸c˜ao do caminho de alinhamento para entradas com seq
¨
uˆencias de apro-
ximadamente 1000, 2000, 3000, 4000 e 5000 res´ıduos . . . . . . . . . . . p. 109
Lista de Tabelas
2.1 Tabela de amino´acidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
4.1 N´ıvel de paralelismo com o uso da ´arvore normal produzida pelo MUSCLE
para as entradas com 500, 1000, 2000 e 4000 seq
¨
uˆencias . . . . . . . . . p. 99
4.2 Compara¸c˜ao do n´ıvel de paralelismo com o uso da ´arvore normal produzida
pelo MUSCLE e da ´arvore balanceada para a entrada com 1000 seq
¨
uˆencias p. 101
17
1 Introdu¸c˜ao
O alinhamento m´ultiplo de seq
¨
uˆencias possui uma diversidade de aplica¸c˜oes na bioinfor-
m´atica, sendo considerado uma das opera¸c˜oes mais importantes desta ´area. Esta opera¸c˜ao
´e realizada atrav´es de ferramentas computacionais, que incorporam diferentes m´etodos e
apresentam diferentes metodologias.
Uma das abordagens mais utilizadas para o alinhamento m´ultiplo de seq
¨
uˆencias, ´e a
abordagem progressiva. Essa abordagem foi incorporada primeiramente em 1994, na ferra-
menta CLUSTALW [4]. Esta ferramenta utiliza uma vers˜ao pura do algoritmo progressivo e
´e muito utilizada at´e hoje devido a sua popularidade. Entretanto, devido ao intenso avan¸co
das pesquisas genˆomicas, abordagens mais complexas foram desenvolvidas e aplicadas em
novas ferramentas.
O MUSCLE [1] ´e uma ferramenta que realiza o alinhamento m´ultiplo de seq
¨
uˆencias.
Segundo um artigo de revis˜ao publicado em 2006 [2], a estrat´egia do MUSCLE apresenta,
em rela¸c˜ao a outras ferramentas de alinhamento existentes, um bom desempenho compu-
tacional e resultados biol´ogicos significativamente precisos. Adicionalmente, vale destacar
que desde a sua primeira vers˜ao, anunciada em 2004, at´e a data de publica¸c˜ao dessa dis-
serta¸c˜ao, v´arias otimiza¸c˜oes foram feitas em seus algoritmos. Isto o vˆem mantendo com
uma boa aceita¸c˜ao pela comunidade cient´ıfica, visto que uma gama de trabalhos genˆomicos
recentes referenciam o MUSCLE como ferramenta de alinhamento utilizada [5–7].
A estrat´egia do MUSCLE divide o alinhamento em trˆes est´agios. O primeiro consiste
basicamente em efetuar um alinhamento m´ultiplo progressivo com m´etodos computacionais
relativamente r´apidos. O segundo est´agio aprimora este alinhamento tamb´em com uma
abordagem progressiva, por´em com t´ecnicas de maior precis˜ao biol´ogica. O terceiro, por
1 Introdu¸c˜ao 18
fim, faz um refinamento no alinhamento atrav´es de um processo iterativo. Como o resultado
de um est´agio ´e a entrada para o est´agio seguinte, a ordem de execu¸c˜ao do programa deve
ser mantida.
Embora exista essa dependˆencia no algoritmo completo da ferramenta, cada est´agio ´e
composto de m´etodos que possuem trechos independentes. Essa independˆencia possibilita
a paraleliza¸c˜ao em n´ıvel de est´agio. A ferramenta MUSCLE atual, desenvolvida por Robert
C. Edgar, executa cada est´agio de forma seq
¨
uencial.
O algoritmo seq
¨
uencial, original do MUSCLE, n˜ao permite que o alinhamento de
seq
¨
uˆencias, que contenham uma quantidade muito grande de dados, seja executado em um
sistema de arquitetura paralela. E o desempenho ´e um fator cada vez mais importante em
problemas de alinhamento devido ao uso crescente de seq
¨
uˆencias para alinhamento. Com
o alinhamento, por exemplo, classificamos novas seq
¨
uˆencias e essas seq
¨
uˆencias s˜ao utiliza-
das em futuros alinhamentos. Isto o classifica como um problema de ordem crescente, e
o emprego de t´ecnicas computacionais cada vez mais eficientes ´e de grande relevˆancia. A
paraleliza¸c˜ao de algoritmos ultrapassa barreiras de desempenho impostas pelo algoritmo
seq
¨
uˆencial e por sistemas seq
¨
uˆencias, sendo uma boa abordagem para problemas de ali-
nhamento m´ultiplo de seq
¨
uˆencias, que, em geral, lidam com uma quantidade grande de
dados.
O objetivo deste trabalho ´e desenvolver uma vers˜ao paralelizada da ferramenta MUSCLE
para sistemas distribu´ıdos, visto que este tipo de sistema ´e o mais comum em laborat´orios
de pesquisa genˆomica. No decorrer do mesmo, os algoritmos de alinhamento foram pri-
meiramente compreendidos, atrav´es de um estudo te´orico de cada m´etodo implementado
pelo MUSCLE e de uma investiga¸c˜ao em seu c´odigo fonte. Em seguida, foi feito um levan-
tamento das abordagens paralelas de alinhamento adequadas a metodologia do MUSCLE.
Apenas com este conhecimento, foi poss´ıvel definir abordagens eficientes de paraleliza¸c˜ao,
seguindo a metodologia de Foster [8], inovadoras para esta classe de problemas. Como o sis-
tema alvo da aplica¸c˜ao paralela ´e de mem´oria distribu´ıda, a implementa¸c˜ao do paralelismo
foi feita atrav´es da biblioteca MPI (message passage interface).
Ap´os o estudo inicial, cada est´agio da ferramenta MUSCLE foi paralelizado, contem-
plando a execu¸c˜ao das seguintes fases:
1.1 Organiza¸c˜ao da disserta¸c˜ao 19
Investiga¸c˜ao do c´odigo: Busca por trechos que caracterizam poss´ıveis pontos de para-
leliza¸c˜ao. Estes trechos s˜ao m´etodos que utilizam conjuntos de dados independentes
e que podem ser distribu´ıdos entre os processadores para que sejam executados si-
multaneamente;
Verifica¸c˜ao da viabilidade do paralelismo: Verifica¸c˜ao da viabilidade de paraleliza¸c˜ao
dos trechos de cada est´agio atrav´es de diversas estrat´egias. Nesta fase, levantam-
se as vantagens e desvantagens de cada estrat´egia, considerando, principalmente, o
balanceamento de carga poss´ıvel entre os processadores envolvidos e a vaz˜ao de dados
na rede;
Implementa¸c˜ao da estrat´egia definida: Implementa¸c˜ao das estrat´egias de paralelismo
adotadas, em que concretiza-se a inser¸c˜ao das estrat´egias de paraleliza¸c˜ao definidas
anteriormente;
Realiza¸c˜ao de testes: Testes e verifica¸c˜ao da eficiˆencia, em que verifica-se, atrav´es de
v´arios tipos de entrada, o aumento de desempenho obtido com a paraleliza¸c˜ao em
cada est´agio. Para cada entrada, os desempenhos dos algoritmos paralelos s˜ao testa-
dos, variando-se o n´umero de n´os de execu¸c˜ao, comparando-os com seus respectivos
algoritmos seq
¨
uenciais.
Ajustes no algoritmo do MUSCLE tamb´em foram feitos para estabelecer uma coorde-
na¸c˜ao na execu¸c˜ao dos trˆes est´agios paralelos.
1.1 Organiza¸c˜ao da disserta¸c˜ao
Al´em da introdu¸c˜ao, esta disserta¸c˜ao est´a organizada em outros quatro cap´ıtulos. No
cap´ıtulo dois apresenta-se toda a revis˜ao bibliogr´afica e alguns conceitos necess´arios para a
contextualiza¸c˜ao e entendimento do projeto. No cap´ıtulo trˆes apresenta-se como decorreu
o processo de sele¸c˜ao dos algoritmos para a paraleliza¸c˜ao, o novo algoritmo em cada etapa
paralelizada e uma an´alise te´orica das estrat´egias adotadas. No cap´ıtulo quatro apresenta-
se os resultados obtidos. No cap´ıtulo cinco apresenta-se as considera¸c˜oes finais e poss´ıveis
projetos futuros.
20
2 Fundamenta¸c˜ao te´orica do
projeto
Esta revis˜ao bibliogr´afica abrange todo o conhecimento pr´evio necess´ario `a paraleliza¸c˜ao
da ferramenta MUSCLE [1] para um ambiente distribu´ıdo. Inicialmente, apresenta-se toda
a metodologia da ferramenta MUSCLE, juntamente com alguns conceitos de bioinform´a-
tica. Em seguida, apresenta-se todos os aspectos referentes `a paraleliza¸c˜ao da ferramenta.
2.1 Gen´etica e bioinform´atica
A ciˆencia respons´avel pelo estudo da transmiss˜ao das caracter´ısticas biol´ogicas de gera-
¸c˜ao para gera¸c˜ao ´e a gen´etica. Essas caracter´ısticas s˜ao representadas atrav´es de seq
¨
uˆencias
de nucleot´ıdeos e amino´acidos.
A informa¸c˜ao que essas seq
¨
uˆencias carregam representa o c´odigo gen´etico de cada
indiv´ıduo. No processo de propaga¸c˜ao da informa¸c˜ao gen´etica para seus descendentes,
essas seq
¨
uˆencias s˜ao propensas a erros.
Esses erros nem sempre s˜ao vis´ıveis ao olho humano. Apenas uma an´alise nas bios-
sequˆencias de cada indiv´ıduo permite-nos ver qu˜ao diferente um indiv´ıduo est´a de outro
indiv´ıduo. As diferen¸cas em suas biossequˆencias possibilitam o surgimento de diferentes
indiv´ıduos de uma determinada esp´ecie.
Este mecanismo da vida conduz ao estudo de m´etodos computacionais que procuram
determinar, com maior precis˜ao poss´ıvel, similaridades e diferen¸cas entre biossequˆencias,
atrav´es de t´ecnicas computacionais de alinhamento de strings. Colocando seq
¨
uˆencias de
diferentes indiv´ıduos alinhadas, podemos, por exemplo, identificar muta¸c˜oes ou regi˜oes
2.1 Gen´etica e bioinform´atica 21
conservadas. Essa identifica¸c˜ao habilita o estudo e a classifica¸c˜ao de novas doen¸cas ou
indiv´ıduos. Como essas novas seq
¨
uˆencias tamb´em s˜ao utilizadas para compara¸c˜ao em
futuros alinhamentos, estes m´etodos genˆomicos lidam com problemas de ordem crescente
e que, continuamente, necessitam de melhores recursos computacionais.
2.1.1 C´odigo Gen´etico: ´acidos nucl´eicos e prote´ınas
Os ´acidos nucl´eicos s˜ao as biomol´eculas de maior importˆancia do controle celular. Eles
s˜ao divididos em dois tipos principais, respons´aveis por carregar o c´odigo gen´etico de um in-
div´ıduo. Esses tipos s˜ao: ´acidos desoxirribonucl´eicos (DNA) e ´acidos ribonucl´eicos (RNA).
O c´odigo gen´etico corresponde a um conjunto de s´ımbolos (tabela do c´odigo gen´etico)
e a uma gram´atica que cont´em as propriedades de cada s´ımbolo.
´
E o c´odigo gen´etico que
configura as estruturas de DNA, RNA e prote´ınas. Este processo ´e realizado atrav´es de
duas etapas, a etapa de transcri¸c˜ao e a etapa de tradu¸c˜ao.
Na etapa de transcri¸c˜ao, a informa¸c˜ao do RNA ´e sintetizada a partir do DNA. A etapa
de tradu¸c˜ao, por sua vez, transforma a mensagem codificada do RNA em prote´ınas. Apesar
de resultar em uma mesma informa¸c˜ao, elas diferem entre si na linguagem utilizada. Os
´acidos nucl´eicos utilizam a linguagem dos nucleot´ıdeos enquanto que as prote´ınas utilizam
a linguagem dos amino´acidos.
Os nucleot´ıdeos s˜ao compostos por uma base nitrogenada, uma pentose e um grupo
fosfato. As bases nitrogenadas definem o nucleot´ıdeo e s˜ao divididas em duas classes: as
pirimidinas e as purinas. Tanto o DNA como o RNA tem duas bases p´uricas: a adenina e
a guanina. Eles possuem tamb´em uma pirimidina principal: a citosina. Por´em, existe uma
diferen¸ca entre as bases de DNA e RNA: a segunda base pirim´ıdica ´e a timina no DNA e
a uracila no RNA.
A representa¸c˜ao dessas bases ´e normalmente feita atrav´es dos s´ımbolos A (adenina), G
(guanina), C (citosina), T (timina) e U (uracila). Conseq
¨
uentemente, os nucleot´ıdeos que
comp˜oem a estrutura de um DNA s˜ao representados por A, G, C e T e os nucleot´ıdeos que
comp˜oem a estrutura de um RNA s˜ao representados por A, G, C e U.
Os amino´acidos, por sua vez, s˜ao obtidos a partir da convers˜ao de uma seq
¨
uˆencia de nu-
2.1 Gen´etica e bioinform´atica 22
cleot´ıdeos. Na cadeia polipept´ıdica, uma conjunto de 3 nucleot´ıdeos (c´odons) corresponde
a um amino´acido. Entretanto, sabemos de antem˜ao que s˜ao 20 os tipos de amino´acidos no
total. No c´odigo gen´etico existem tamb´em c´odons de finaliza¸c˜ao (UAA,UGA e UAG) que
indicam `a c´elula que a sequˆencia de amino´acidos destinada `aquela prote´ına acaba ali.
Como a combina¸c˜ao de todas as trincas de nucleot´ıdeos resulta em 64 tipos distintos,
mais de uma combina¸c˜ao acaba por representar um mesmo amino´acido. A tabela 2.1
mostra os amino´acidos resultantes das 64 combina¸c˜oes de nucleot´ıdeos.
Primeira Segunda Posi¸c˜ao Terceira
posi¸c˜ao U C A G posi¸c˜ao
U Phe (F) Ser (S) Tyr (Y) Cys (C) U
Phe (F) Ser (S) Tyr (Y) Cys (C) C
Leu (L) Ser (S) finaliza¸c˜ao finaliza¸c˜ao A
Leu (L) Ser (S) finaliza¸c˜ao Trp (W) G
C Leu (L) Pro (P) His (H) Arg (R) U
Leu (L) Pro (P) His (H) Arg (R) C
Leu (L) Pro (P) Gln (Q) Arg (R) A
Leu (L) Pro (P) Gln (Q) Arg (R) G
A Ile (I) Thr (T) Asn (N) Ser (S) U
Ile (I) Thr (T) Asn (N) Ser (S) C
Ile (I) Thr (T) Lys (K) Arg (R) A
Met (M) Thr (T) Lys (K) Arg (R) G
G Val (V) Ala (A) Asp (D) Gly (G) U
Val (V) Ala (A) Asp (D) Gly (G) C
Val (V) Ala (A) Glu (E) Gly (G) A
Val (V) Ala (A) Glu (E) Gly (G) G
Tabela 2.1: Tabela de amino´acidos
2.1.2 Compara¸c˜ao de seq
¨
uˆencias
Atrav´es da compara¸c˜ao de seq
¨
uˆencias ´e poss´ıvel ver os mecanismos da evolu¸c˜ao que as
caracter´ısticas morfol´ogicas n˜ao nos permitem. Quando olhamos para a imagem de dois
animais podemos dizer aparentemente o quanto eles se parecem e quais s˜ao suas diferen¸cas,
por´em n˜ao temos como saber exatamente quais as mudan¸cas que foram feitas. Ao olhar
para um grupo de seq
¨
uˆencias alinhadas podemos dizer que eles s˜ao diferentes devido a um
conjunto de amino´acidos diferentes em determinadas regi˜oes.
2.2 Alinhamento de seq
¨
uˆencias 23
A figura 2.1 mostra um conjunto de seq
¨
uˆencias alinhadas. A partir deste alinhamento,
pode-se ver as muta¸c˜oes ocorridas em indiv´ıduos que supostamente vieram de ancestrais
comuns. Essas muta¸c˜oes s˜ao vistas onde ocorrem substitui¸c˜oes ou remo¸c˜oes/inser¸c˜oes de
res´ıduos (caracteres). No caso das remo¸c˜oes/inser¸c˜oes, estas s˜ao representadas com lacunas
(gaps) no alinhamento. Com o alinhamento pode-se ver tamb´em as regi˜oes conservadas e
calcular o grau de similaridade existente entre as seq
¨
uˆencias.
33|1i21A|gi|28261215 -------VNVRGLEVTDLG-QLCQLLS--------------QLSTVGDVSH-----ESLM
1i21A --SLPDGFYIRRXEEGDLE-QVTETLKVLT-----------TVGTITPESFCKLIKYWNE
24|1i21A|gi|4115735 ---LPQGYTFRKLKLTDYDNQYLETLKVLT-----------TVGEISKEDF------TEL
1b87A -------MIISEFDRNN---PVLKD----------------QLSDLLRLTWPEEYGDSSA
4|1b87A|gi|78231 -------ANILTEAFNDLG----------------------------NNSWPDM--TSAT
6|1b87A|gi|1743004 ----LKK------SFLDAG----------------------------NESWGDI--KNAI
36|1i21A|gi|23473444 ---LQEGFVIRPVRPADNA-AVAEIIRSVS-----------QEHGLTAEAGYAVGDAAVD
9|1i21A|gi|6458376 -------MNIRLATSADAE-TIAQQRD--------------AMFVDMGEAAEKLARVHDS
25|1b87A|gi|23027249 ------------IEVDDLSRPAIAE----------------LLSDHMREMWEVSNPESCH
2|1b87A|gi|27376228 -------MQIRPGDTFDPR--VVAL-----------------LDHHVTAARAQTAPGSAH
Figura 2.1: Exemplo de um alinhamento m´ultiplo de seq
¨
uˆencias
2.2 Alinhamento de seq
¨
uˆencias
O alinhamento de seq
¨
uˆencias ´e um procedimento fundamental na biologia computaci-
onal.
´
E ele que nos mostra quais as regi˜oes que variam e quais s˜ao conservadas em um
conjunto de seq
¨
uˆencias.
Quando alinhamos um conjunto de seq
¨
uˆencias, fazemo-no, normalmente, por elas serem
hom´ologas. Na verdade, acreditamos que elas evolu´ıram de um ancestral comum. Neste
processo, as esp´ecies envolvidas sofreram muta¸c˜oes e suas biossequˆencias foram alteradas.
Estas altera¸c˜oes consistem de inser¸c˜oes, remo¸c˜oes e altera¸c˜oes de seus res´ıduos, como visto
na se¸c˜ao 2.1. Todas essas ocorrˆencias s˜ao demonstradas no alinhamento. No caso das
inser¸c˜oes e remo¸c˜oes, s˜ao inseridas lacunas no alinhamento. Estas lacunas, mais conhecidas
como gaps, s˜ao representadas por um conjunto de indels, termo utilizado para representar
uma lacuna em uma ´unica coluna.
O alinhamento ´e feito aos pares. Cada elemento do par pode ser uma seq
¨
uˆencia ou
um grupo de seq
¨
uˆencias alinhadas. O alinhamento par a par pode ser, portanto, entre
duas seq
¨
uˆencias, entre dois grupos ou entre um grupo e uma seq
¨
uˆencia. O princ´ıpio do
alinhamento par a par ´e considerar todas as formas poss´ıveis de alinhar esses pares. En-
tretanto, sempre buscamos encontrar o melhor alinhamento. Este alinhamento nos mostra
2.2 Alinhamento de seq
¨
uˆencias 24
as maiores similaridades e as menores diferen¸cas e tamb´em ´e conhecido por alinhamento
´otimo.
´
E este o alinhamento que nos mostra as mudan¸cas que achamos mais prov´aveis de
terem ocorrido durante a evolu¸c˜ao.
Para encontrarmos o alinhamento ´otimo ´e necess´ario adotarmos um sistema de pon-
tua¸c˜ao, a partir do qual, obt´em-se, para cada alinhamento, uma certa pontua¸c˜ao. Aquele
que no final do processo tiver a maior pontua¸c˜ao ´e o alinhamento ´otimo.
O primeiro passo para definir um sistema de pontua¸c˜ao ´e associar uma pontua¸c˜ao
para cada par de letras pertencente ao alfabeto das seq
¨
uˆencias envolvidas. Se estivermos
alinhando seq
¨
uˆencias de DNA, o alfabeto ´e apenas A, C, G e T. Para prote´ınas temos um
alfabeto de 20 letras, correspondente a todos os amino´acidos. Essas pontua¸c˜oes encontram-
se nas matrizes de substitui¸c˜ao e s˜ao baseadas em propriedades matem´aticas e modelos
estat´ısticos. Uma matriz de substitui¸c˜ao ´e uma tabela que descreve a probabilidade de um
par de res´ıduos (amino´acidos ou nucleot´ıdeos) ocorrer em um alinhamento [9].
O segundo passo para definirmos um sistema de pontua¸c˜ao ´e a penalidade de gaps. A
penalidade de um gap pode ser medida a partir de uma fun¸c˜ao W (s), que considera s como
sendo o tamanho do gap. Em sua forma mais simples, W (s) ´e uma fun¸c˜ao linear da forma
W (s) = gs, onde g ´e a penalidade de ocorrer um ´unico indel. Entretanto, como ´e mais
prov´avel que um ´unico evento crie um gap de v´arios indels, uma fun¸c˜ao linear n˜ao atribui
uma penalidade muito confi´avel.
Considerar uma fun¸c˜ao que atribua pesos diferentes de acordo com o tamanho do gap ´e
uma melhor solu¸c˜ao. Uma maneira ´e fazer com que o gap inicial apresente uma penalidade
maior. Neste modelo, trˆes indels isolados - trˆes gaps -, por exemplo, apresentam uma
penalidade maior do que trˆes indels consecutivos - um ´unico gap. Entretanto, n˜ao existe
um consenso sobre qual penalidade de gap utilizar. V´arias an´alises da distribui¸c˜ao emp´ırica
do tamanho dos gaps foram feitas, oferecendo diversas estimativas para diferentes sistemas
de pontua¸c˜ao.
Al´em de depender do sistema de pontua¸c˜ao utilizado, o alinhamento final tamb´em
depende de seu algoritmo, podendo este ser ´otimo ou n˜ao (sub-´otimo). Para o alinhamento
de duas seq
¨
uˆencias, utiliza-se, normalmente, m´etodos de programa¸c˜ao dinˆamica, como os
algoritmos de Needleman e Wunsch [10] e Smith e Waterman [11]. Esses algoritmos testam
2.2 Alinhamento de seq
¨
uˆencias 25
todas as solu¸c˜oes poss´ıveis e sempre encontram o alinhamento ´otimo. Apesar de ser um
problema de elevada complexidade computacional, o uso de um conjunto pequeno de dados
(apenas duas seq
¨
uˆencias, por exemplo) viabiliza sua execu¸c˜ao.
Para obter o alinhamento m´ultiplo ´otimo, uma poss´ıvel solu¸c˜ao ´e generalizar o algo-
ritmo de Needleman e Wunsch para o espa¸co multidimensional. Neste caso, uma matriz
N-dimensional ´e computada, onde cada dimens˜ao representa uma seq
¨
uˆencia. A complexi-
dade computacional deste algoritmo ´e O(2
N
L
N
), onde L ´e o tamanho m´edio das seq
¨
uˆencias
e N ´e o n´umero de seq
¨
uˆencias [12].
Devido `as limita¸c˜oes pr´aticas de tempo e mem´oria, a generaliza¸c˜ao do algoritmo de
Needleman e Wunsch ´e ineficiente para grandes quantidades de dados, limitando-se a pro-
blemas pequenos. Por esta raz˜ao, uma variedade de abordagens heur´ısticas foram propostas
na literatura. As principais delas se dividem em duas classes: a dos algoritmos progressivos
e dos algoritmos iterativos.
O algoritmo progressivo, explicado na se¸c˜ao 2.2.2, foi inicialmente proposto em [11]
e posteriormente melhorado em [13] e [14]. Ele ´e utilizado pela maioria das ferramentas
de alinhamento m´ultiplo de seq
¨
uˆencias atualmente, como o CLUSTALW, o MAFFT e o
MUSCLE. A abordagem iterativa, por sua vez, inicia com uma solu¸c˜ao sub-´otima, que
pode ser obtida atrav´es de um r´apido alinhamento m´ultiplo progressivo. Este alinhamento
sub-´otimo ´e melhorado a cada itera¸c˜ao. A ferramenta MUSCLE implementa uma etapa de
refinamento iterativo em sua ´ultima vers˜ao.
Por fim, tˆem-se tamb´em as abordagens paralelas. Como o universo de seq
¨
uˆencias para
compara¸c˜ao cresceu imensamente ao longo dos ´ultimos anos, paraleliza¸c˜oes dessas aborda-
gens tamb´em foram propostas na literatura. Esses algoritmos dividem o alinhamento em
sub-tarefas, permitindo que v´arias m´aquinas realizem opera¸c˜oes independentes simultane-
amente.
2.2.1 Alinhamento entre pares de perfis
Para o c´alculo de alinhamento m´ultiplo de seq
¨
uˆencias, os m´etodos heur´ısticos s˜ao mais
utilizados. Esses m´etodos normalmente realizam v´arias opera¸c˜oes de alinhamento aos pa-
2.2 Alinhamento de seq
¨
uˆencias 26
res, seguindo uma ordem espec´ıfica. A realiza¸c˜ao de v´arios alinhamentos aos pares, seja
progressivamente ou iterativamente, reduz a complexidade do algoritmo, uma vez que cada
opera¸c˜ao de alinhamento utiliza uma matriz bi-dimensional. Por outro lado, os m´etodos
exatos, em geral, realizam apenas uma ´unica opera¸c˜ao de alinhamento, por´em envolvendo
uma matriz N-dimensional. Esta ´unica opera¸c˜ao, embora seja ´otima, ou seja, teste todos
os casos e forne¸ca com garantia a melhor solu¸c˜ao, apresenta uma ordem de complexidade
muito elevada, inviabilizando sua execu¸c˜ao para alinhamentos com muitas seq
¨
uˆencias.
Os alinhamentos das abordagens heur´ısticas podem ser feitos entre duas seq
¨
uˆencias,
dois grupos de seq
¨
uˆencias ou entre um grupo e uma seq
¨
uˆencia. Para representar estatistica-
mente um elemento qualquer do par do alinhamento, seja ele grupo ou seq
¨
uˆencia, utiliza-se
o termo perfil. No MUSCLE, o perfil ´e armazenado computacionalmente em uma matriz
que informa a freq
¨
uˆencia relativa com que cada res´ıduo ou indel aparece em cada coluna
do alinhamento m´ultiplo (figura 2.2).
1
0
1
0
0
0
2
0.25
0
0.5
0.25
0
3
0.75
0
0
0
0.25
4
0
0.75
0
0
0.25
5
0.25
0
0
0.75
0
6
0
0.25
0
0.75
0
7
0
0
0
0.75
0.25
C A A C T T T
C G A - T T -
C G - C A T T
C T A C T C T
A
C
G
T
-
1
2
3
4
1234567
Seqüências
do Perfil
Colunas do Perfil
Figura 2.2: Armazenamento do perfil em uma matriz
O alinhamento m´ultiplo no MUSCLE ´e feito sempre entre dois perfis, tanto nas etapas
de alinhamento progressivo, em cada n´o da ´arvore filogen´etica, quanto em cada itera¸c˜ao
do est´agio iterativo. V´arios m´etodos de alinhamento perfil/perfil foram propostos na lite-
ratura. Melhorias na qualidade do resultado biol´ogico foram reportadas com o uso desses
m´etodos em rela¸c˜ao aos m´etodos de alinhamento seq
¨
uˆencia/seq
¨
uˆencia e grupo/seq
¨
uˆencia
(ver [15]).
2.2 Alinhamento de seq
¨
uˆencias 27
2.2.2 Algoritmo progressivo
O m´etodo de alinhamento progressivo consiste em alinhar fam´ılias de seq
¨
uˆencias que
est˜ao evolutivamente relacionadas, partindo do alinhamento das seq
¨
uˆencias mais pr´oxi-
mas. O princ´ıpio deste m´etodo ´e construir uma ´arvore com caracter´ısticas biol´ogicas e
ir construindo o alinhamento progressivamente de acordo com a ordem especificada por
esta ´arvore. Essa ´arvore, conhecida biologicamente por ´arvore filogen´etica, ´e percorrida
visitando sempre os n´os filhos antes dos n´os pais. Assim, os primeiros alinhamentos s˜ao
feitos entre os n´os folhas e o alinhamento m´ultiplo resultante ´e obtido na raiz da ´arvore.
A qualidade deste m´etodo depende de dois fatores principais: o sistema de pontua¸c˜ao
e a ´arvore filogen´etica utilizada. O sistema de pontua¸c˜ao ´e utilizado para definir qual o
melhor alinhamento entre dois perfis durante cada etapa. A ´arvore, por sua vez, define a
ordem dos alinhamentos. Esta abordagem, apesar de n˜ao produzir com garantia o melhor
alinhamento, produz ´otimos resultados, principalmente levando em considera¸c˜ao sua baixa
complexidade em rela¸c˜ao aos m´etodos exatos de programa¸c˜ao dinˆamica.
2.2.3 Algoritmo iterativo
Os m´etodos iterativos s˜ao muito utilizados como m´etodos de otimiza¸c˜ao para produ¸c˜ao
de alinhamento m´ultiplo de seq
¨
uˆencias. Eles s˜ao utilizados sozinhos ou combinados com
outros m´etodos. Esses algoritmos apresentam a vantagem de serem muito simples, tanto
na codifica¸c˜ao quanto na complexidade temporal e espacial. Eles recebem este nome pois
trabalham repetidamente, realinhando ou adicionando novas seq
¨
uˆencias ao alinhamento
m´ultiplo existente.
Embora os algoritmos de alinhamento mais utilizados sejam os progressivos, estes pro-
duzem uma s´erie de erros inerentes. Esses erros s˜ao reduzidos atrav´es de um est´agio de
refinamento, feito atrav´es de algoritmos iterativos, por exemplo. Diversas abordagens de
refinamento foram propostas na literatura [16]. As ferramentas de alinhamento mais pre-
cisas atualmente incluem um est´agio iterativo de refinamento.
Durante o refinamento, calcula-se a pontua¸c˜ao objetiva do novo alinhamento. Caso
obtenha-se uma pontua¸c˜ao maior, o novo alinhamento ´e mantido. Caso contr´ario, ele ´e
2.3 A metodologia da ferramenta MUSCLE 28
descartado. Este processo ´e feito at´e que uma condi¸c˜ao previamente estabelecida seja
atingida. Esta condi¸c˜ao define o n´umero de itera¸c˜oes do algoritmo.
2.3 A metodologia da ferramenta MUSCLE
Esta se¸c˜ao explica a metodologia da ferramenta MUSCLE, apresentando toda a rela¸c˜ao
existente entre as v´arias etapas de sua execu¸c˜ao. Uma descri¸c˜ao dessas etapas e dos m´etodos
aplicados ´e feita em detalhes na se¸c˜ao 2.4.
2.3.1 Funcionamento b´asico
A ferramenta MUSCLE ´e dividida em trˆes est´agios principais, que utilizam tanto a
abordagem progressiva quanto a abordagem iterativa. O alinhamento progressivo ´e uti-
lizada pelo MUSCLE em seus dois primeiro est´agios, e ´e dividido basicamente em trˆes
passos: calcular a distˆancia entre cada par de seq
¨
uˆencias, construir uma ´arvore filogen´e-
tica e realizar o alinhamento entre dois n´os irm˜aos, armazenando o resultado obtido no n´o
pai. Este ´ultimo passo ´e repetido progressivamente at´e atingir o n´o raiz, finalizando com o
alinhamento de todas as seq
¨
uˆencias.
Os algoritmos no primeiro e no segundo est´agio aplicam m´etodos diferentes, que variam
o n´ıvel de complexidade computacional e a precis˜ao do resultado. O primeiro est´agio
´e respons´avel pela obten¸c˜ao de um alinhamento bruto, utilizando-se m´etodos de baixo
custo computacional. O segundo est´agio aprimora o resultado do alinhamento do primeiro
est´agio, atrav´es de outros m´etodos.
As principais modifica¸c˜oes ocorrem na primeira e na terceira etapa. No primeiro est´a-
gio, a primeira etapa ´e calculada utilizando o algoritmo de contagem de k-mer, explicado
na se¸c˜ao 2.4.1. No segundo est´agio utiliza-se um algoritmo que calcula a identidade fraci-
onal entre todos os pares alinhados. A terceira etapa, por sua vez, ´e otimizada no segundo
est´agio, realizando o alinhamento apenas nos n´os que sofreram altera¸c˜oes, auxiliado por
um m´etodo de compara¸c˜ao de ´arvores. Na segunda etapa, de constru¸c˜ao de ´arvore, ambos
est´agios utilizam o algoritmo UPGMA, explicado na se¸c˜ao 2.4.2.
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE 29
O terceiro est´agio do MUSCLE apresenta uma abordagem iterativa e ´e conhecido como
est´agio de refinamento. Este est´agio recebe como entrada o resultado do segundo est´agio
e a ´arvore guia. Para cada itera¸c˜ao, o algoritmo primeiro elimina uma aresta da ´arvore,
dividindo as seq
¨
uˆencias em dois subconjuntos. Em seguida, um perfil ´e extra´ıdo de cada
subconjunto e as colunas que n˜ao cont´em elementos (apenas gaps) s˜ao eliminadas. Por
fim, ´e feito um novo alinhamento e sua pontua¸c˜ao objetiva ´e calculada. Se esta pontua¸c˜ao
aumentar, o novo alinhamento ´e mantido; caso contr´ario, ele ´e descartado. O processo
iterativo continua at´e que todas as arestas da ´arvore sejam visitadas sem que nenhuma
mudan¸ca seja mantida, ou at´e que um n´umero m´aximo de itera¸c˜oes seja atingido. As
arestas da ´arvore s˜ao visitadas em ordem decrescente de distˆancia at´e a raiz, realinhando
primeiro seq
¨
uˆencias individuais, portanto grupos fortemente relacionados.
A figura 2.3 apresenta a intera¸c˜ao entre esses trˆes est´agios e os m´etodos utilizados, por
padr˜ao, pela ferramenta.
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE
Nesta se¸c˜ao descreve-se as principais etapas do MUSCLE, bem como os m´etodos uti-
lizados em cada uma delas. Em algumas etapas ´e poss´ıvel utilizar m´etodos distintos, que
s˜ao selecionados atrav´es de passagem de parˆametros durante a chamada de execu¸c˜ao do
programa. Apesar de todos os m´etodos serem apresentados, s˜ao enfatizados os m´etodos
adotados como padr˜ao pela ferramenta. Estes m´etodos apresentam uma melhor eficiˆencia,
do ponto de vista de precis˜ao, velocidade e uso de mem´oria (ver [17]).
2.4.1 Medidas de similaridades e estimativas de distˆancia
Sempre que nos deparamos com duas seq
¨
uˆencias, ´e natural questionarmos qu˜ao simi-
lares elas s˜ao. Para isso, adotamos algumas medidas que permitem identificar quantas
substitui¸c˜oes ocorreram nessas seq
¨
uˆencias desde que elas divergiram. O termo similari-
dade ´e usado, portanto, como uma medida do grau de divergˆencia evolucion´aria entre duas
seq
¨
uˆencias. Obviamente, essas medidas apenas fazem sentido em seq
¨
uˆencias que possuem
um certo grau de rela¸c˜ao.
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE 30
sequências
desalinhadas
matriz de distância
de k-mer D1
árvore
filogenética 1
_______
____ __
_ _____
_______
alinhamento 1
matriz de distância
de Kimura D2
árvore
filogenética 2
_______
____ __
_ _____
_______
alinhamento 2
geração de
sub-árvores
_______
____ __
computa novos perfis
_ _____
_______
_______
____ __
_ _____
_______
alinhamento
_______
____ __
_ _____
_______
Não,
deleta
alinhamento 3
_______
____ __
_ _____
_______
Sim,
salva
Estágio 1: Alinhamento progressivo bruto
Estágio 3: Refinamento iterativo
Estágio 2: Alinhamento progressivo melhorado
contagem de
k-mer
UPGMA
alinhamento
progressivo
computa Ids
a partir de
alinhamento 1
UPGMA
alinhamento
progressivo
re-alinha
perfis
pontuação
melhora?
Figura 2.3: Diagrama de fluxo do algoritmo do MUSCLE
Este valor, entretanto, n˜ao deve ser usado diretamente como uma forma de medir
a distˆancia entre duas seq
¨
uˆencias. Para encontrar uma estimativa boa de distˆancia ´e
preciso saber mais que sua similaridade. Saber apenas a taxa de similaridade entre duas
seq
¨
uˆencias n˜ao nos d´a o conhecimento de todas as mudan¸cas ocorridas durante o processo
evolucion´ario. Sem este conhecimento, n˜ao ´e poss´ıvel estimar, com precis˜ao, a quantidade
m´edia de substitui¸c˜oes ocorridas de uma seq
¨
uˆencia para outra, a partir do ponto em que
houve a divergˆencia.
Quando realizamos o alinhamento n˜ao temos essas informa¸c˜oes. Tudo o que sabemos ´e
mostrado apenas nas seq
¨
uˆencias a serem alinhadas. O uso de boas medidas de similaridade,
aliadas as boas estimativas de distˆancia, nos fornece ´otimos valores aproximados. E s˜ao
com esses valores aproximados que criamos as ´arvores filogen´eticas, estruturas utilizadas
no alinhamento m´ultiplo progressivo.
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE 31
No MUSCLE, dois tipos de medidas de similaridade s˜ao utilizadas, cada um apre-
sentando suas vantagens e desvantagens: a identidade fracional e a contagem de k-mers.
Ambas as medidas, juntamente com suas respectivas estimativas de distˆancia, s˜ao mostra-
das a seguir.
Identidade Fracional
A forma mais simples de medirmos a similaridade entre duas seq
¨
uˆencias ´e colocando-as
alinhadas uma sobre a outra e contando o n´umero de posi¸c˜oes idˆenticas. Este n´umero em
rela¸c˜ao ao total de posi¸c˜oes das seq
¨
uˆencias ´e um valor fracional.
A obten¸c˜ao deste valor ´e feita da seguinte maneira: dado o alinhamento, ignora-se
todas as posi¸c˜oes com gaps e, nas demais, calcula-se a quantidade de posi¸c˜oes com res´ıduos
iguais em rela¸c˜ao a quantidade total de res´ıduos. A figura 2.4 apresenta um exemplo do
c´alculo da identidade fracional.
AC GATC AT
CC GCTC AC
T-
-T
* * ** *
ACTGATCAT
CCGCTCTAC
Seqüência 1
Seqüência 2
Alinhamento
Identidade
Fracional = 5/8
1 2 3 4 5 6 7 8 9 10
Figura 2.4: C´alculo da identidade fracional entre duas seq
¨
uˆencias
Nesta figura, o par de seq
¨
uˆencias alinhadas possui 10 posi¸c˜oes. Dessas, apenas as
posi¸c˜oes 1, 2, 4, 5, 6, 7, 9 e 10 n˜ao possuem gaps. As posi¸c˜oes 2, 4, 6, 7 e 9, por sua vez,
s˜ao as ´unicas que possuem res´ıduos iguais em ambas as seq
¨
uˆencias. Ou seja, 8 posi¸c˜oes
sem gaps e 5 posi¸c˜oes com res´ıduos iguais. A identidade fracional entre essas seq
¨
uˆencias ´e,
portanto, 5/8.
A partir da identidade fracional D, obt´em-se uma medida aproximada de distˆancia
atrav´es da corre¸c˜ao de Kimura [17]:
d
Kimura
= − log
e
(1 − D − D
2
/5)
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE 32
A ´arvore filogen´etica ´e ent˜ao constru´ıda a partir da matriz de distˆancia obtida.
Contagem de k-mers
O m´etodo de contagem de k-mers ´e um m´etodo de compara¸c˜ao de seq
¨
uˆencias livres de
alinhamento que calcula a similaridade entre pares de seq
¨
uˆencias atrav´es de contagem de
palavras de tamanho k.
Neste m´etodo, utiliza-se o termo k-mer para representar as palavras, ou k-tuplas.
Adotado como op¸c˜ao padr˜ao pela ferramenta MUSCLE, no seu primeiro est´agio de exe-
cu¸c˜ao, este m´etodo apresenta uma velocidade consideravelmente maior em rela¸c˜ao aos
m´etodos convencionais, que requerem alinhamento [18]. Seu algoritmo ´e de ordem O(L),
para seq
¨
uˆencias de tamanho L, diferente dos algoritmos que requerem alinhamento e que
apresentam ordem de complexidade O(L
2
).
Este algoritmo utiliza, em geral, um alfabeto um pouco diferente. Na maioria dos casos
o alfabeto utilizado ´e uma varia¸c˜ao do alfabeto padr˜ao. Esses alfabetos cont´em s´ımbolos
que denotam classes que correspondem a duas ou mais letras diferentes (tipos de res´ıduos).
Em [18] mostra-se como a escolha do alfabeto e do valor de k tem forte impacto no n´umero
de identidades conservadas. No MUSCLE essa escolha ´e feita com base em estat´ısticas.
O MUSCLE implementa a contagem de k-mers contando exatamente quantos k-mers
apareceram em cada uma das seq
¨
uˆencias. A f´ormula para o c´alculo da similaridade, entre
as seq
¨
uˆencias X e Y , ´e:
F =
∑
τ
min[n
X
(τ),n
Y
(τ)]/[min(L
X
,L
Y
) − k + 1]
Aqui τ ´e um k-mer, L
X
e L
Y
s˜ao os comprimentos das seq
¨
uˆencias, e n
X
(τ) e n
Y
(τ) s˜ao o
n´umero de vezes que τ aparece em X e Y , respectivamente.
Segundo [17], uma boa estimativa de distˆancia, empiricamente encontrada, ´e simples-
mente 1 − F. No entanto, cada alfabeto apresenta estimativas espec´ıficas de acordo com o
valor de k utilizado.
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE 33
2.4.2 Constru¸c˜ao da ´arvore
´
Arvores filogen´eticas s˜ao ´arvores bin´arias que representam o caminho evolucion´ario de
um conjunto de seq
¨
uˆencias e a rela¸c˜ao existente entre elas. Estas ´arvores s˜ao constru´ıdas a
partir de uma matriz que mostra a distˆancia entre todos os pares poss´ıveis de seq
¨
uˆencias,
que ´e previamente calculada.
A busca da melhor ´arvore ´e um processo bastante exaustivo. A maioria dos m´etodos
exige uma verifica¸c˜ao de todos os arranjos poss´ıveis para identificar a melhor solu¸c˜ao.
H´a, por´em, m´etodos exatos que n˜ao exigem a verifica¸c˜ao de todos os arranjos, como o
algoritmo Branch-and-Bound, primeiramente proposto por Land e Doig, em 1960 [19]. O
algoritmo Branch-and-Bound apresenta uma abordagem paralela proposta recentemente
na literatura [20] e ´e uma boa solu¸c˜ao para ´arvores n˜ao muito grandes. Entretanto, para
grandes quantidades de dados, o tempo computacional, qualquer que seja o m´etodo exato
utilizado, acaba sendo impratic´avel e portanto longe de ser uma boa solu¸c˜ao. Neste caso,
utiliza-se m´etodos heur´ısticos para buscar a melhor hip´otese para os dados atrav´es de um
tempo mais curto para sua an´alise.
O MUSCLE implementa, como padr˜ao, o m´etodo UPGMA. Este m´etodo ´e heur´ıstico
e segue um procedimento iterativo. Seus desempenhos est˜ao fortemente relacionados com
a matriz de distˆancia utilizada. A id´eia desses algoritmos ´e construir ´arvores agrupando
perfis de seq
¨
uˆencias similares. Este agrupamento ocorre entre sub-´arvores e parte da jun¸c˜ao
de duas seq
¨
uˆencias. Esta jun¸c˜ao resulta em pequenas sub-´arvores que, por sua vez, s˜ao
interligadas formando sub-´arvores maiores. Este processo ´e finalizado com a constru¸c˜ao de
uma ´arvore que interliga todas as seq
¨
uˆencias do conjunto.
As jun¸c˜oes s˜ao feitas da seguinte forma. Considere dois grupos (sub-´arvores) E e D
que ser˜ao unidas formando um novo grupo P. Este grupo P se torna o pai de E, que ´e
filho a esquerda, e D, que ´e filho a direita, em uma ´arvore bin´aria. Em seguida, obt´em-se a
distˆancia entre P e C, tal que C pertence ao conjunto de seq
¨
uˆencias. A ordem de conex˜ao
dos grupos ´e definida pela matriz de distˆancia, partindo da conex˜ao das duas seq
¨
uˆencias
mais pr´oximas.
A distˆancia entre P e C ´e utilizada para que o processo continue. Como os demais
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE 34
grupos s˜ao interligados por meio de P, e n˜ao mais por E e D, a ordem de jun¸c˜ao dos grupos
´e determinado com base na distˆancia de P com os demais grupos.
2.4.3 Compara¸c˜ao de ´arvores
No segundo est´agio da ferramenta MUSCLE, realiza-se um novo alinhamento pro-
gressivo visando-se um aprimoramento na qualidade do alinhamento final. Entretanto, a
entrada para este segundo est´agio ´e o alinhamento obtido no est´agio anterior juntamente
com a ´arvore guia.
O que acontece no segundo est´agio ´e uma identifica¸c˜ao dos pares alinhados que possuem
uma maior identidade fracional, seguida da constru¸c˜ao de uma nova ´arvore pela qual o novo
alinhamento ser´a guiado. Esta nova ´arvore, entretanto, pode ser muito similar `a primeira
(alguns ramos iguais). Conseq
¨
uentemente, o resultado do alinhamento de algumas sub-
´arvores acaba n˜ao sendo modificado. Para evitar desperd´ıcio de processamento durante o
alinhamento neste novo est´agio, indica-se na nova ´arvore o que deve ser refeito e o que n˜ao
´e necess´ario. Este procedimento ´e feito atrav´es do algoritmo de compara¸c˜ao de ´arvores.
A id´eia deste algoritmo ´e associar progressivamente identificadores aos n´os que possuem
os mesmos filhos, em ambas as ´arvores. Isto ´e feito atrav´es da avalia¸c˜ao de pares de n´os
(um de cada ´arvore), para todos os n´os das ´arvores, visitando sempre os n´os filhos antes
de seus pais. Como este algoritmo n˜ao foi selecionado para a paraleliza¸c˜ao devido a seu
baixo consumo de processamento (ver cap´ıtulo 3), o mesmo n˜ao ser´a descrito aqui. Maiores
detalhes, entretanto, s˜ao encontrados no artigo do MUSCLE [17].
2.4.4 Alinhamento entre perfis
O alinhamento de perfis ´e feito de modo similar ao alinhamento de duas seq
¨
uˆencias. A
diferen¸ca ´e que cada perfil pode representar mais do que uma ´unica seq
¨
uˆencia. O que se
faz neste caso ´e extrair informa¸c˜oes estat´ısticas do conjunto de seq
¨
uˆencias, reduzindo-o a
valores como freq
¨
uˆencia relativa de res´ıduos e grau de ocupa¸c˜ao, para cada uma de suas
colunas. Com esses valores calculados, inicia-se a busca do alinhamento ´otimo entre dois
perfis.
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE 35
Programa¸c˜ao dinˆamica
A literatura sugere alguns algoritmos de programa¸c˜ao dinˆamica para realizar este pro-
cedimento [21–23]. Com esses alinhamentos constr´oi-se uma matriz, tal que cada uma
de suas coordenadas corresponda a cada um dos perfis, e encontra-se, no final, a solu¸c˜ao
´otima, que corresponde ao alinhamento de maior pontua¸c˜ao. Este alinhamento ´e encon-
trado atrav´es da t´ecnica do traceback.
A id´eia desses algoritmos ´e encontrar o melhor alinhamento conforme os perfis v˜ao sendo
percorridos. Alinha-se os primeiros i caracteres do primeiro perfil (X
i
) com os primeiros j
caracteres do segundo perfil (Y
j
), por meio de dois la¸cos aninhados. Para cada alinhamento
obt´em-se a pontua¸c˜ao correspondente, atrav´es de um sistema de pontua¸c˜ao.
Apenas trˆes casos podem ocorrer no final do alinhamento parcial: ou X
i
e Y
j
estar˜ao
alinhados um com o outro, ou X
i
estar´a alinhado com um gap (remo¸c˜ao) ou Y
j
estar´a
alinhado com um gap (inser¸c˜ao). Para isto considere X
i
e Y
j
como sendo o ´ultimo caractere
de X
i
e Y
j
. Para demonstrar como a pontua¸c˜ao m´axima ´e encontrada, considere tamb´em:
S
i j
a fun¸c˜ao de pontua¸c˜ao para alinhar X
i
com Y
j
, b
X
i
a pontua¸c˜ao para uma abertura de
gap em Y que est´a alinhado com X
i
, t
X
i
a pontua¸c˜ao para um gap de fechamento alinhado
com X
i
, U
i j
o conjunto de todos os alinhamentos de X
i
com Y
j
, M
i j
a pontua¸c˜ao do melhor
alinhamento em U
i j
terminando com um casamento (X
i
e Y
j
alinhados), R
i j
a pontua¸c˜ao
do melhor alinhamento terminando em uma remo¸c˜ao (X
i
alinhado com um gap) e I
i j
a
pontua¸c˜ao do melhor alinhamento terminando em uma inser¸c˜ao (Y
j
alinhado com um gap).
Procuramos ent˜ao a m´axima pontua¸c˜ao do alinhamento de X
i
com Y
j
, correspondentes
as trˆes possibilidades: casamento, remo¸c˜ao ou inser¸c˜ao. No MUSCLE, a equa¸c˜ao que
encontra a pontua¸c˜ao para cada uma das possibilidade ´e dada a seguir:
M
i j
= S
i j
+ max{M
i−1 j−1
,R
i−1 j−1
+t
X
i−1
,I
i−1 j−1
+t
Y
j−1
}
R
i j
= max{R
i−1 j
,M
i−1 j
+ b
X
i
}
I
i j
= max{I
i j−1
,M
i j−1
+ b
Y
j
}
Durante o c´alculo das pontua¸c˜oes, o la¸co externo itera sobre i e o la¸co interno itera sobre
j. A fun¸c˜ao de pontua¸c˜ao ´e computada no la¸co interno e n˜ao ser´a descrita aqui uma vez que
2.4 Descri¸c˜ao das etapas e m´etodos do MUSCLE 36
o paralelismo n˜ao ocorre neste n´ıvel (ver cap´ıtulo 3). Quando a pontua¸c˜ao m´axima ´e obtida
com um casamento, faz-se um movimento diagonal na matriz. Movimentos verticais e
horizontais s˜ao feitos quando a melhor pontua¸c˜ao ´e obtida com uma inser¸c˜ao ou remo¸c˜ao. A
marca¸c˜ao desses movimentos possibilita, no final, encontrar o melhor alinhamento, atrav´es
da t´ecnica do traceback. Com esta t´ecnica, o melhor alinhamento final ´e designado pelo
percurso na matriz de acordo com esses movimentos.
2.4.5 Pontua¸c˜ao objetiva
A qualidade do alinhamento final ´e medida atrav´es de uma fun¸c˜ao de pontua¸c˜ao obje-
tiva. Esta fun¸c˜ao recebe como entrada um alinhamento e retorna sua pontua¸c˜ao.
O m´etodo utilizado pela ferramenta MUSCLE ´e a pontua¸c˜ao de soma de pares (SP).
Este m´etodo calcula a pontua¸c˜ao objetiva a partir de um somat´orio das pontua¸c˜oes de
todas as substitui¸c˜oes, inser¸c˜oes ou remo¸c˜oes ocorridas entre todos os pares poss´ıveis de
seq
¨
uˆencias alinhadas. Essas pontua¸c˜oes s˜ao computadas a partir de uma matriz de substi-
tui¸c˜ao mais a penalidade de gaps.
A matriz de substitui¸c˜ao ´e utilizada para calcular a pontua¸c˜ao para cada par alinhado
de res´ıduos. Como exemplo, considere que a posi¸c˜ao um, em uma primeira seq
¨
uˆencia,
cont´em o amino´acido M e a mesma posi¸c˜ao, em uma segunda seq
¨
uˆencia, cont´em o amino´a-
cido L. A matriz de substitui¸c˜ao retorna a pontua¸c˜ao desta substitui¸c˜ao espec´ıfica e esta ´e
utilizada no somat´orio que retorna a pontua¸c˜ao final do alinhamento.
A penalidade de gap, por sua vez, ´e computada descartando todas as colunas em que
ambas as seq
¨
uˆencias possuam um indel. Aplica-se, ent˜ao, a penalidade g + λ e para cada
gap, onde g ´e a penalidade por gap, λ ´e o comprimento do gap (n´umero de indels) e e ´e a
penalidade de extens˜ao.
No MUSCLE, utiliza-se a pontua¸c˜ao objetiva no est´agio de refinamento. Sempre que
um alinhamento ´e feito, este ´e comparado com o alinhamento anterior, prevalecendo apenas
aquele com uma maior pontua¸c˜ao.
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 37
2.5 Aspectos da programa¸c˜ao paralela e sistemas dis-
tribu´ıdos
O uso da computa¸c˜ao vem tornando-se cada vez mais intenso. Com a evolu¸c˜ao das
diversas ´areas da ciˆencia, o poder computacional exigido para a solu¸c˜ao de diversas classes
de problemas ´e crescente. A computa¸c˜ao, por sua vez, sofreu um estrondoso avan¸co nos
´ultimos anos. Hoje as esta¸c˜oes de trabalho chegam a ser at´e cem vezes mais r´apidas do
que aquelas de uma d´ecada atr´as. Entretanto, muitos problemas atuais s˜ao t˜ao complexos
de serem resolvidos que sua simula¸c˜ao num´erica requer um poder computacional extraor-
din´ario, muitas vezes invi´aveis de serem tratados com a tecnologia atual em uma simples
esta¸c˜ao de trabalho. Uma alternativa seria esperar um certo tempo - calcul´avel segundo a
Lei de Moore - para que o avan¸co tecnol´ogico viabilizasse a solu¸c˜ao desses problemas. No
entanto, ´e poss´ıvel trazer a solu¸c˜ao desses problemas para os dias atuais, atrav´es do uso da
computa¸c˜ao paralela.
A computa¸c˜ao paralela ´e a forma padr˜ao utilizada pelos cientistas e engenheiros para
resolver problemas da ciˆencia que demandam alto desempenho computacional. Para que
este tipo de computa¸c˜ao seja feito ´e necess´ario o uso de m´aquinas envolvendo m´ultiplas
unidades de processamento, atrav´es da computa¸c˜ao paralela. Os computadores paralelos,
entretanto, s˜ao divididos em duas classes principais: mem´oria compartilhada e mem´oria
distribu´ıda.
Os sistemas de mem´oria compartilhada s˜ao sistemas altamente integrados, no qual
as unidades de processamento compartilham o acesso a uma ´unica mem´oria global. Os
sistemas de mem´oria distribu´ıda, por sua vez, s˜ao constru´ıdos com m´ultiplos computadores
interconectados via rede. A intera¸c˜ao entre os processadores dos diferentes computadores
´e feito atrav´es de passagem de mensagens.
Um sistema de mem´oria distribu´ıda poderoso e economicamente vi´avel ´e o cluster Be-
owulf. Este projeto foi criado pela NASA em 1994 e ´e vastamente utilizado em laborat´orios
de pesquisa em todo o mundo. A constru¸c˜ao de um cluster Beowulf ´e feito a partir de
computadores pessoais, n˜ao especializados, portanto mais baratos. Eles s˜ao amplamente
utilizados na ciˆencia para atuarem, por exemplo, em projetos de desdobramento de prote´ı-
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 38
nas, an´alise gen´etica, dinˆamica de flu´ıdos, dentre outros.
Para o desenvolvimento de algoritmos capazes de executarem e usufru´ırem ao m´aximo
os recursos de tais m´aquinas paralelas, s˜ao necess´arios ambientes de desenvolvimento es-
pec´ıficos. Na maioria dos casos, esses ambientes s˜ao constru´ıdos sobre uma linguagem
seq
¨
uencial existente, como C e Fortran, por exemplo, adicionada de recursos para a comu-
nica¸c˜ao entre processos. Essa comunica¸c˜ao ´e feita atrav´es da troca de mensagens e suas
rotinas encontram-se em bibliotecas espec´ıficas.
Atualmente, a biblioteca de passagem de mensagens mais utilizada ´e o MPI. Al´em
de sua distribui¸c˜ao estar dispon´ıvel livremente pela internet, muitas s˜ao as vantagens de
utiliz´a-la. A maior delas ´e a portabilidade. Escrever programas paralelos utilizando MPI
permite porta-los para diferentes computadores paralelos, variando seu desempenho de
acordo com o hardware utilizado. Este ´e o padr˜ao utilizado para implementa¸c˜ao e execu¸c˜ao
de programas paralelos em clusters Beowulf e, portanto, foi a biblioteca padr˜ao escolhida
para a implementa¸c˜ao deste projeto.
2.5.1 O modelo tarefa/canal
A metodologia de programa¸c˜ao de algoritmos paralelos utilizada pelo MPI ´e baseada
no modelo tarefa/canal. Neste modelo, a computa¸c˜ao paralela ´e representada como um
conjunto de tarefas que interagem entre si atrav´es de canais de comunica¸c˜ao (figura 2.5).
Por estes canais s˜ao enviadas mensagens, possibilitando as tarefas trocarem dados locais
por meio de suas portas de entrada e sa´ıda. Um canal ´e uma fila de mensagens que conecta
a porta de sa´ıda de uma tarefa com a porta de entrada de outra tarefa.
Neste modelo h´a uma certa distin¸c˜ao entre os dados que cada tarefa pode acessar.
Existem os dados privados de cada tarefa, contidos inicialmente em suas mem´orias locais,
e os dados compartilhados, cujo acesso ocorre atrav´es dos canais de comunica¸c˜ao. Apesar
deste modelo permitir acesso a todos os dados do sistema, deve-se levar em considera¸c˜ao
que o tempo de acesso aos dados locais ´e muito mais r´apido quando comparado ao acesso
feito pelo canal.
O tempo de execu¸c˜ao de um programa paralelo ´e medido enquanto pelo menos uma
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 39
memória
programa
programa e memória local
encapsulados em uma tarefa
tarefas interligadas através de
canais de comunicação
porta de saída
porta de entrada
Figura 2.5: O modelo tarefa/canal
tarefa est´a ativa. Este tempo se inicia com a execu¸c˜ao das v´arias tarefas simultˆaneas e
finaliza quando a ´ultima tarefa deixa de executar.
2.5.2 Metodologia de projeto de programas paralelos
Segundo Ian Foster [8], quatro passos s˜ao importantes para o desenvolvimento de al-
goritmos paralelos. Esses passos s˜ao: particionamento, comunica¸c˜ao, aglomera¸c˜ao e es-
calonamento. Com esta metodologia ´e poss´ıvel desenvolver algoritmos paralelos para um
vasto conjunto de aplica¸c˜oes. Al´em disto, tal metodologia preza pela portabilidade dos
algoritmos, uma vez que n˜ao s˜ao consideradas caracter´ısticas dependentes de arquitetura.
Estas s˜ao, quando necess´arias, consideradas apenas em passos posteriores.
Particionamento
O particionamento consiste em dividir os dados e a computa¸c˜ao em v´arios peda¸cos.
Um bom particionamento efetua essa divis˜ao em pequenos peda¸cos. Essa divis˜ao ocorre
atrav´es de uma abordagem centrada nos dados ou de uma abordagem centrada na compu-
ta¸c˜ao. Independente da decomposi¸c˜ao escolhida, esses peda¸cos recebem o nome de tarefas
primitivas.
A abordagem centrada nos dados consiste em dividir os dados em partes e, em seguida,
determinar como associar o processamento com os dados. Ela tamb´em ´e conhecida como
decomposi¸c˜ao do dom´ınio. A abordagem centrada na computa¸c˜ao coloca a ˆenfase na divis˜ao
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 40
da computa¸c˜ao envolvida no problema, dividindo o processamento em v´arias partes e, em
seguida, determinando a associa¸c˜ao dos dados com o processamento. Esta abordagem ´e
tamb´em conhecida como decomposi¸c˜ao funcional.
Como um guia na decis˜ao de qual particionamento escolher, Foster propˆos uma lista
de verifica¸c˜ao capaz de medir a qualidade do particionamento. Essa lista ´e composta de
quatro atributos [8]:
• O n´umero de tarefas primitivas ´e pelo menos uma ordem maior que o n´umero de
processadores;
• Processamento e armazenamento de estrutura de dados redundantes s˜ao minimizados;
• Tarefas primitivas s˜ao do mesmo tamanho;
• O n´umero de tarefas aumenta conforme aumenta o problema.
Comunica¸c˜ao
Identificadas as parti¸c˜oes, o passo seguinte preocupa-se em definir a forma com a qual
essas partes trocam informa¸c˜oes. Foster define quatro categorias de comunica¸c˜oes poss´ıveis
de serem adotadas na implementa¸c˜ao de um algoritmo paralelo. A comunica¸c˜ao pode ser
local ou global, dependendo do n´umero de tarefas envolvidas na comunica¸c˜ao, estruturada
ou n˜ao-estruturada, dependendo da forma como elas interagem entre si, est´atica ou dinˆa-
mica, dependendo se a defini¸c˜ao das tarefas envolvidas ´e feita ou n˜ao em tempo de execu¸c˜ao
e, por fim, s´ıncrona ou ass´ıncrona, dependendo da existˆencia ou n˜ao de coordena¸c˜ao entre
as tarefas comunicantes.
Na comunica¸c˜ao local, cria-se um canal quando uma tarefa necessita de dados de tarefas
vizinhas, pertencentes a um determinado grupo. A comunica¸c˜ao global, por´em, n˜ao possui
limites na troca de dados, podendo cada tarefa se comunicar arbitrariamente.
A estrutura¸c˜ao, por sua vez, depende de uma ordem na intera¸c˜ao entre as tarefas. Caso
as tarefas formem uma estrutura regular, como uma ´arvore, por exemplo, e a comunica¸c˜ao
seja estabelecida respeitando tal estrutura, dizemos que a comunica¸c˜ao ´e estruturada. Por
outro lado, o modelo n˜ao-estruturado permite que as tarefas formem grafos arbitr´arios.
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 41
Na comunica¸c˜ao est´atica, a identidade dos parceiros comunicantes ´e fixa, ou seja, a
comunica¸c˜ao ocorre sempre entre as mesmas tarefas. J´a na comunica¸c˜ao dinˆamica, os
parceiros comunicantes n˜ao s˜ao previamente definidos, dependendo dos valores calculados
em tempo de execu¸c˜ao.
Por fim, a comunica¸c˜ao considera o sincronismo entre as tarefas comunicantes. Caso
a comunica¸c˜ao entre as tarefas seja feita coordenadamente a comunica¸c˜ao ´e s´ıncrona. Em
contrapartida, a comunica¸c˜ao ´e ass´ıncrona quando n˜ao existe nenhum tipo de coordena¸c˜ao.
Em projeto de algoritmos paralelos, define-se abordagens de comunica¸c˜ao de modo a
manter o menor overhead poss´ıvel. Para isto, Foster sugere a seguinte lista de verifica¸c˜ao
[8]:
• As opera¸c˜oes de comunica¸c˜ao est˜ao balanceadas entre as tarefas;
• Cada tarefa se comunica apenas com um pequeno n´umero de vizinhos;
• Tarefas podem realizar sua comunica¸c˜ao concorrentemente;
• Tarefas podem realizar seu processamento concorrentemente.
Aglomera¸c˜ao
Nesta etapa definimos a forma pela qual as tarefas primitivas encontradas devem ser
agrupadas. Para isto, trˆes pontos conflituosos devem ser considerados.
O primeiro deles ´e o aumento da granularidade. Quanto maior a granularidade obtida,
menor o custo com a comunica¸c˜ao. Conseq
¨
uentemente, menor o overhead gerado com a
troca de mensagens. Obviamente, uma forma de diminuir a comunica¸c˜ao, ´e agrupando ao
m´aximo as tarefas primitivas que se comunicam. Isto pode ser feito atrav´es da combina¸c˜ao
de grupos de tarefas emissoras e receptoras. Outra forma, entretanto, considera o tamanho
da mensagem. O envio de menos mensagens, por´em mais longas, demanda menos tempo
do que o envio de mais mensagens, por´em mais curtas, com o mesmo comprimento total.
O segundo ponto ´e manter a escalabilidade do algoritmo. Aqui, considera-se que o
programa possa ser portado para um sistema que possua um n´umero maior ou menor de
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 42
processadores. Se a aglomera¸c˜ao combinar muitas tarefas primitivas, o n´umero de tarefas
distribu´ıdas entre os processadores pode n˜ao atingir uma boa eficiˆencia quando o programa
for executado em um sistema com um conjunto muito grande de processadores. Portanto,
a aglomera¸c˜ao deve ser feita de tal forma que a granularidade seja controlada por um
parˆametro em tempo de execu¸c˜ao ou compila¸c˜ao. Dessa forma, o n´umero de tarefas pode
ser adaptado ao n´umero de processadores dispon´ıveis.
Por fim, busca-se obter uma redu¸c˜ao de custos de engenharia de software. Enquanto um
n´umero baixo de aglomerados pode ser ineficiente em sistemas com um grande n´umero de
processadores, o tempo e os gastos envolvidos com o desenvolvimento do programa paralelo
s˜ao minimizados. Um n´umero baixo de aglomerados utiliza muito c´odigo seq
¨
uencial. Em
contrapartida, muitos aglomerados implicam em grandes altera¸c˜oes no c´odigo, aumentando
o tempo e os custos para sua confec¸c˜ao.
A qualidade de uma aglomera¸c˜ao pode ser medida atrav´es de uma lista de verifica¸c˜ao
proposta por Foster. Esta lista constitui-se de sete itens [8]:
• A aglomera¸c˜ao aumentou a localidade da comunica¸c˜ao;
• Processamento replicado toma menos tempo do que a comunica¸c˜ao que substituiu;
• A quantidade de dados replicados ´e pequeno o suficiente para permitir o aumento de
escala do algoritmo;
• Tarefas aglomeradas tˆem custos de processamento e comunica¸c˜ao similares;
• O n´umero de tarefas ´e uma fun¸c˜ao do tamanho do problema;
• O n´umero de tarefas ´e o menor poss´ıvel mas pelo menos t˜ao grande quanto o n´umero
de processadores;
• O custo representado pela escolha de uma certa aglomera¸c˜ao para economizar com o
uso de um algoritmo seq
¨
uencial existente ´e compensador.
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 43
Escalonamento
O escalonamento ´e o processo de atribuir tarefas aos processadores. Para isto, dois s˜ao
os objetivos a serem alcan¸cados: maximizar a utiliza¸c˜ao dos processadores e minimizar a
comunica¸c˜ao entre eles.
Por utiliza¸c˜ao de processadores entende-se o tempo que estes se mant´em ativos em
rela¸c˜ao ao tempo total de execu¸c˜ao do programa. Ela ´e maximizada quando a computa¸c˜ao
´e igualmente balanceada, ou seja, quando as tarefas em todos os processadores iniciam
e terminam ao mesmo tempo. Portanto, ocorre uma queda no desempenho sempre que
alguns processadores estiverem ociosos enquanto outros estiverem ocupados.
A comunica¸c˜ao entre os processadores ´e minimizada quando duas tarefas conectadas
por um canal s˜ao escalonadas para o mesmo processador. Quando isto ocorre o acesso aos
dados ´e mais r´apido, pois estes se encontram na mem´oria local do sistema.
Ambos os objetivos, entretanto, conflitam entre si. Como exemplo, suponha que p pro-
cessadores encontram-se dispon´ıveis. Ao mapear todas as tarefas para um ´unico processa-
dor, o custo de comunica¸c˜ao entre os processadores ´e zero. A utiliza¸c˜ao dos processadores,
por´em, ´e reduzida a 1/p. Neste caso, recomenda-se encontrar um ponto de equil´ıbrio.
A lista de verifica¸c˜ao a seguir, proposta por Foster, ajuda na obten¸c˜ao de um bom
escalonamento [8]:
• Projetos baseados em uma tarefa por processador e m´ultiplas tarefas por processador
foram considerados;
• Aloca¸c˜oes est´atica e dinˆamica das tarefas aos processadores foram avaliadas;
• Se a aloca¸c˜ao dinˆamica de tarefas for escolhida, o controlador n˜ao ´e um gargalo de
desempenho;
• Se a aloca¸c˜ao est´atica de tarefas for escolhida, o n´umero de tarefas ´e pelo menos 10
vezes o n´umero de processadores.
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 44
2.5.3 MPI - Message Passage Interface
Muitas linguagens paralelas foram propostas nos ´ultimos 40 anos. Entre elas encon-
tramos muitas de alto-n´ıvel, simplificando a forma de controlar o paralelismo. Nenhuma
delas, por´em, foi escolhida como de uso padr˜ao para um caso geral. Conseq
¨
uentemente,
muitas linguagens de alto-n´ıvel continuam sendo desenvolvidas, com fun¸c˜oes que realizam
passagem de mensagens entre processos.
O MPI ´e a especifica¸c˜ao de passagem de mensagem mais popular, que suporta progra-
ma¸c˜ao paralela, e que executa em sistemas de mem´oria distribu´ıda. Ele cont´em uma s´erie
de rotinas que definem a forma como os computadores devem se comunicar para que o
paralelismo seja feito. Essas rotinas podem ser utilizadas em Fortran, C, C++ ou qualquer
outra linguagem que seja capaz de fazer uma interface com a biblioteca MPI.
Nesta se¸c˜ao ´e apresentada o modelo de passagem de mensagem, mostrando de forma
breve como os processos s˜ao tratados e como a comunica¸c˜ao ´e estabelecida. Tamb´em ´e
apresentada a implementa¸c˜ao do MPI utilizada neste projeto.
O modelo de passagem de mensagens
Este modelo ´e similar ao modelo tarefa/canal. Neste modelo, o hardware assume
a forma ilustrada na figura 2.6. Como pode ser visto, cada esta¸c˜ao possui seu pr´oprio
processador e mem´oria, sendo que cada processador tem acesso direto apenas as instru¸c˜oes
e dados de sua pr´opria mem´oria. A interconex˜ao de rede ´e utilizada para que seja poss´ıvel
a troca de mensagens entre os processadores. Assim, o processador A pode enviar uma
mensagem contendo alguns de seus valores de dados locais para um processador B, dando
a ele acesso indireto a esses valores.
Esta comunica¸c˜ao na verdade ´e feita entre processos. O que ´e uma tarefa no modelo
tarefa/canal ´e um processo neste modelo. Um processador pode ter mais de um processo
e a comunica¸c˜ao ´e estabelecida com o processo com o qual ele deseja se comunicar. A
informa¸c˜ao ´e ent˜ao passada ao processo do processador correspondente, em um ambiente
transparente ao programador. Dessa forma, cada processo pode se comunicar com todos os
outros processos. Estes processos possuem um identificador ´unico. Eles realizam diferentes
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 45
Processador
Processador
Processador
Processador
Processador
Processador
Processador
Processador
Memória
Memória
Memória
Memória
Memória
Memória
Memória
Memória
Interconexão
de rede
Figura 2.6: O modelo de passagem de mensagens
opera¸c˜oes, de acordo com as especifica¸c˜oes, ao longo da execu¸c˜ao do programa.
A comunica¸c˜ao, por sua vez, ´e feita atrav´es de um canal virtual.
´
E nele que todas as
mensagens s˜ao enviadas, de um processo para outro. Essas mensagens podem ser anˆoni-
mas, podendo ser recebidas por qualquer processo, ou nomeadas, sendo enviadas apenas
ao processo que possua um determinado identificador. Elas, entretanto, n˜ao s˜ao apenas
utilizadas para troca de dados. Mecanismos de sincroniza¸c˜ao tamb´em s˜ao implementados
neste modelo. Durante a transferˆencia s´ıncrona, nem o processo emissor nem o receptor
continuam seu processamento at´e que a mensagem seja totalmente transferida. Por este
motivo, at´e mesmo mensagens sem conte´udo possuem um significado.
Open MPI
O OpenMPI [25] ´e uma implementa¸c˜ao do MPI que implementa as especifica¸c˜oes do
MPI-1.2 [26] e MPI-2 [27] e suporta aplica¸c˜oes multithreads. Outras vers˜oes do MPI como
o LAM/MPI n˜ao oferecem este suporte.
O MPICH2 ´e uma outra implementa¸c˜ao do MPI-2 e que tamb´em suporta aplica¸c˜oes
multithreads. Entretanto, o Open MPI apresenta uma menor latˆencia e utiliza melhor a
largura de banda dispon´ıvel [28].
Uma vez que utilizamos threads em algumas estrat´egias definidas e devido `as vantagens
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 46
de desempenho apresentadas, optamos por adotar o Open MPI como a implementa¸c˜ao
utilizada para testes. Outras implementa¸c˜oes, entretanto, podem ser utilizadas, desde que
satisfa¸cam os requisitos de execu¸c˜ao do algoritmo quanto ao uso ou n˜ao de threads.
2.5.4 Medidas de desempenho
A medi¸c˜ao de desempenho utilizada nesse trabalho pretende quantificar o trabalho que
um computador consegue realizar por unidade de tempo. Essa tarefa exige um planeja-
mento que considere n˜ao apenas a t´ecnica em si, mas tamb´em outros fatores, como:
• qual est´agio do ciclo de vida do desenvolvimento da aplica¸c˜ao deve se aplicar a me-
di¸c˜ao e qual t´ecnica deve ser utilizada;
• qual a capacidade da t´ecnica em prover as m´etricas desejadas;
• qual a validade e a confiabilidade dos resultados obtidos com a t´ecnica;
• qual o custo e o esfor¸co investido para cada estrat´egia no contexto de recursos com-
putacionais e humanos.
De antem˜ao, sabemos que a computa¸c˜ao paralela apresenta duas vantagens principais.
Primeiro, com mais mem´orias e recursos de armazenamento do que os dispon´ıveis em uma
´unica m´aquina, um computador paralelo pode resolver instˆancias maiores de um mesmo
problema. Segundo, com mais processadores agregados a sub-conjuntos de mem´orias, um
computador paralelo pode resolver problemas mais rapidamente.
Em geral, as m´etricas aplicadas em algoritmos paralelos visam medir os ganhos de
desempenho sob o ponto de vista de tempo de execu¸c˜ao. Entretanto, tais medi¸c˜oes, de uma
forma indireta, acabam por mostrar o impacto do paralelismo na capacidade de resolver
instˆancias maiores de um problema. Ao medir-se a escalabilidade de um algoritmo, por
exemplo, utiliza-se entradas de dados de diferentes tamanhos. Dependendo da estrat´egia
adotada para verificar-se a escalabilidade, pode-se ver claramente como o aumento do
n´umero de n´os habilita a execu¸c˜ao de instˆancias maiores.
2.5 Aspectos da programa¸c˜ao paralela e sistemas distribu´ıdos 47
Na computa¸c˜ao paralela, portanto, o foco n˜ao est´a apenas no tempo de execu¸c˜ao.
Tamb´em devem ser considerados a forma como recursos adicionais (tipicamente processa-
dores) afetam o tempo de execu¸c˜ao e a capacidade de solu¸c˜ao de problemas maiores. Dessa
forma, perguntas freq
¨
uentes como ’utilizar duas vezes mais processadores reduz na metade
o tempo de execu¸c˜ao?’ ou ’qual o n´umero de processadores m´aximo para que a computa¸c˜ao
use os recursos eficientemente?’ podem ser facilmente respondidas. Para tal, utiliza-se em
geral as medidas de speedup.
Speedup
Geralmente o speedup ´e definido como o tempo necess´ario para resolver o problema em
um ´unico processador sobre o tempo requerido para resolver o mesmo problema em um
sistema paralelo, com p processadores. Dependendo da forma que este tempo seq
¨
uencial
´e medido, podemos distinguir speedups absoluto, real e relativo [29]. No speedup real, o
tempo seq
¨
uencial ´e obtido pela execu¸c˜ao do programa seq
¨
uencial mais eficiente em um ´unico
processador do computador paralelo. No speedup absoluto, o tempo seq
¨
uencial ´e obtido
pela execu¸c˜ao do programa seq
¨
uencial mais eficiente no computador seq
¨
uencial mais r´apido
existente. No speedup relativo, o tempo seq
¨
uencial ´e obtido pela execu¸c˜ao do programa
paralelo em um ´unico processador do computador paralelo.
O speedup absoluto ´e uma medida pouco utilizada devido a dificuldade de utilizar o
computador seq
¨
uencial mais r´apido existente. A evolu¸c˜ao r´apida de novos processadores
dificulta tamb´em esta compara¸c˜ao. O speedup real e o relativo, por outro lado, apresentam
o problema de limita¸c˜ao de mem´oria. Sem o uso de computadores extremamente potentes,
pode-se tornar invi´avel a obten¸c˜ao do tempo de execu¸c˜ao em um ´unico processador.
Nos algoritmos implementados, foram feitas an´alises de benchmarks (n˜ao anal´ıticas)
atrav´es do speedup real e relativo. A medida utilizada ´e indicada em cada teste. Nos
casos em que instˆancias muito grandes s˜ao utilizadas e que n˜ao podem ser executadas em
um ´unico processador, uma alternativa foi calcular o ganho de desempenho do algoritmo
paralelo a partir do menor n´umero de n´os que habilita a execu¸c˜ao do problema. Dessa forma
mant´em-se a caracter´ıstica do speedup relativo, provendo informa¸c˜oes sobre a eficiˆencia do
algoritmo paralelo em solucionar o problema [30] e possibilitando que certas degrada¸c˜oes
2.6 Abordagens paralelas de alinhamento 48
e varia¸c˜oes do desempenho do algoritmo sejam reveladas.
Degrada¸c˜ao do paralelismo
Dois importantes motivos para a degrada¸c˜ao do paralelismo durante a sua execu¸c˜ao
s˜ao o desbalanceamento de carga e os custos com a comunica¸c˜ao. Enquanto o desba-
lanceamento de carga depende apenas da aplica¸c˜ao, o custo de comunica¸c˜ao depende do
processo de comunica¸c˜ao, da latˆencia, da aplica¸c˜ao e do hardware que est´a sendo utilizado.
Entende-se pela aplica¸c˜ao uma fun¸c˜ao que considera o algoritmo, a instˆancia do problema
e o n´umero de processadores.
A fim de obter uma medi¸c˜ao precisa sobre a degrada¸c˜ao do paralelismo, ambos os parˆa-
metros foram medidos durante a fase de testes. Para medir os custos com a comunica¸c˜ao,
realizou-se uma instrumenta¸c˜ao no c´odigo atrav´es do MPE2, um pacote de software do
MPI para programadores que cont´em uma API para an´alise de desempenho [31] e uma
poderosa ferramenta de visualiza¸c˜ao gr´afica, o Jumpshot [32–35]. Com o MPE2 ´e poss´ıvel
realizar medi¸c˜oes de tempo em todas as fun¸c˜oes do MPI, sejam fun¸c˜oes de comunica¸c˜ao
ou sincronismo. Dessa forma, obteve-se claramente o tempo gasto com comunica¸c˜ao e a
latˆencia em cada n´o utilizado.
Para medir o desbalanceamento de carga, definiu-se um parˆametro adotado como n´ıvel
de paralelismo e que ´e explicado na se¸c˜ao 4.3.2. Este parˆametro, junto com os gr´aficos
de comunica¸c˜ao e sincronismo em cada n´o, possibilita ver o que, no desbalanceamento da
carga, ´e inerente ao problema, e o que ´e devido `a estrat´egia de escalonamento adotada.
O n´ıvel de paralelismo foi obtido atrav´es de uma instrumenta¸c˜ao manual implementada
durante a fase de testes do projeto.
2.6 Abordagens paralelas de alinhamento
Com o crescimento da ´area de tecnologia da informa¸c˜ao, m´etodos digitais, cada vez
mais eficientes, vˆem se tornando indispens´aveis para a solu¸c˜ao de diversas classes de pro-
blemas. S˜ao v´arios os campos da ciˆencia que lidam com problemas de gerenciamento e
armazenamento de grandes quantidades de dados e os recursos de inform´atica viabilizam a
2.6 Abordagens paralelas de alinhamento 49
extra¸c˜ao de informa¸c˜oes ´uteis desses dados. O campo da genˆomica ´e um deles, onde os da-
dos tomam a forma de biossequˆencias, estruturas tridimensionais, motifs, etc. O problema
´e que enquanto a quantidade de dados de projetos genˆomicos cresce de forma constante e
exponencial, nossa habilidade de absorver e processar essas informa¸c˜oes permanece prati-
camente constante [36].
Existem v´arias formas de ultrapassar esses limites da computa¸c˜ao. Uma maneira ´e
a cria¸c˜ao de algoritmos heur´ısticos, onde busca-se uma solu¸c˜ao aproximada ao inv´es da
melhor solu¸c˜ao. Entretanto, a forma mais promissora ´e a computa¸c˜ao paralela. Na com-
puta¸c˜ao paralela v´arios processadores s˜ao utilizados no processamento de uma tarefa que
´e invi´avel de ser resolvida em um simples processador.
Os algoritmos paralelos habilitam a computa¸c˜ao massiva de dados dividindo a tarefa
em v´arios processos que podem ser executados concorrentemente. Levando-se em conta
as caracter´ısticas apresentadas pela metodologia de Ian Foster [8], v´arias estrat´egias de
paralelismo foram definidas para os v´arios problemas de bioinform´atica.
Dentre os problemas da bioinform´atica, encontram-se os problemas de alinhamento
m´ultiplo de seq
¨
uˆencias. Um algoritmo de alinhamento m´ultiplo pode ser feito seguindo
v´arias abordagens, produzindo resultados ´otimos ou n˜ao. Uma ferramenta de alinha-
mento, por sua vez, pode misturar as abordagens existentes, como ´e o caso da ferramenta
MUSCLE.
As abordagens paralelas propostas s˜ao in´umeras. Alguns trabalhos prop˜oem ferra-
mentas inteiras paralelizadas, como a vers˜ao do CLUSTALW para sistemas distribu´ıdos,
utilizando o MPI [37]. Outros trabalhos prop˜oem o paralelismo apenas de etapas espec´ıfi-
cas.
Muitas pesquisas envolvendo o paralelismo de t´ecnicas de alinhamentos de seq
¨
uˆencias
vˆem sendo feitas, tanto no Brasil [38, 39] quanto em outras partes do mundo [40, 41]. O
levantamento bibliogr´afico aqui apresentado, entretanto, tem seu foco apenas no que h´a
de mais relevante nas pesquisas que envolvem a paraleliza¸c˜ao de m´etodos similares aos da
ferramenta MUSCLE. Uma an´alise aprofundada ´e feita nesses m´etodos, visando auxiliar
no desenvolvimento de novas estrat´egias paralelas.
2.6 Abordagens paralelas de alinhamento 50
2.6.1 CLUSTALW-MPI
O CLUSTALW realiza o alinhamento progressivo em trˆes etapas: c´alculo das distˆancias,
constru¸c˜ao da ´arvore filogen´etica e o alinhamento de perfis, seguindo a ordem especificada
pela ´arvore. No CLUSTALW-MPI [37], todas essas etapas foram paralelizadas, reduzindo
o tempo de execu¸c˜ao da ferramenta. A ferramenta utiliza a biblioteca MPI e executa em
sistemas de mem´oria distribu´ıda.
No CLUSTALW, o c´alculo da matriz de distˆancia ´e feito utilizando-se a identidade fra-
cional. Realiza-se nesta etapa o alinhamento par a par entre todas as seq
¨
uˆencias. Uma vez
que esses alinhamentos s˜ao independentes entre si, a implementa¸c˜ao paralela da identidade
fracional ´e bastante simples. O algoritmo proposto considera cada alinhamento como uma
´unica tarefa. As tarefas ent˜ao s˜ao aglomeradas em blocos maiores, formando p processos
distintos, cada um executando em uma m´aquina do cluster.
Com a matriz de distˆancia calculada, constr´oi-se a ´arvore filogen´etica. O m´etodo
utilizado no CLUSTALW ´e neighbor-joining. No artigo publicado da ferramenta [4], nada
est´a descrito sobre sua implementa¸c˜ao paralela. Entretanto, uma publica¸c˜ao mais recente
[42] sugere uma implementa¸c˜ao paralela mais eficiente deste m´etodo.
Por fim, a etapa de alinhamento mistura uma abordagem de paralelismo que, segundo
Li [37], est´a em duas granularidades. O paralelismo em maior granularidade ´e feito em
todos os n´os folhas da ´arvore. A eficiˆencia obviamente depende da topologia da ´arvore. O
paralelismo do alinhamento nos n´os intermedi´arios ´e um paralelismo de menor granulari-
dade uma vez que esses n´os dependem dos resultados de seus n´os filhos.
2.6.2 MUSCLE-SMP
O MUSCLE-SMP [3] ´e a primeira implementa¸c˜ao paralela da ferramenta MUSCLE
e foi desenvolvida para executar em um sistema multiprocessado de mem´oria comparti-
lhada. Essa paraleliza¸c˜ao foi feita atrav´es da biblioteca OpenMP e considera apenas os
dois est´agios progressivos da ferramenta. O est´agio iterativo n˜ao ´e paralelizado.
O primeiro est´agio progressivo ´e relativamente r´apido de executar. Como visto na se¸c˜ao
2.3.1, ele utiliza um m´etodo de baixa complexidade para construir a matriz de distˆancia. O
2.6 Abordagens paralelas de alinhamento 51
alinhamento ´e ent˜ao feito de baixo para cima, seguindo uma ´arvore previamente constru´ıda.
Este alinhamento implica na dependˆencia entre um n´o pai e seus n´os filhos, de tal forma
que um n´o s´o possa ser alinhado quando seus dois n´os filhos estiverem alinhados. Esta
dependˆencia impede que seja feito um paralelismo em gr˜ao grosso no c´odigo fonte. No
MUSCLE-SMP utiliza-se um modelo que considera uma fila de tarefas. Essas tarefas s˜ao
os alinhamentos e a tarefa do alinhamento de um n´o pai s´o ´e habilitada quando a tarefa de
alinhamento de seus n´os filhos for finalizada. Dessa forma, as tarefas habilitadas n˜ao tˆem
nenhuma dependˆencia entre si, podendo executar paralelamente.
O segundo est´agio, por sua vez, concentra quase toda a sua computa¸c˜ao na constru¸c˜ao
de uma nova matriz de distˆancia. O m´etodo utilizado neste est´agio ´e o da identidade
fracional. O alinhamento, por sua vez, ´e menos intenso. Ele ´e feito apenas nos n´os da
´arvore que foram modificados. Uma vez que quase toda a computa¸c˜ao est´a na constru¸c˜ao
da matriz de distˆancia, optou-se em paralelizar, neste est´agio, apenas este m´etodo. Este
m´etodo realiza um conjunto de opera¸c˜oes em todos os pares de seq
¨
uˆencias, atrav´es de dois
la¸cos aninhados, como apresentado no pseudo-c´odigo seguinte:
for ( i = 1 ; i < num_seq ; ++i)
for ( j = 0 ; j < i ; ++i)
Calcula_elemento_da_Matriz(i,j)
Neste c´odigo, as vari´aveis do la¸co interno dependem das vari´aveis do la¸co externo. Esta
dependˆencia acarretaria em um paralelismo com forte desbalanceamento de carga, caso um
algoritmo de balanceamento de carga est´atico fosse utilizado. O que o MUSCLE-SMP faz,
neste caso, ´e atribuir dinamicamente cada par de la¸cos a seu processador correspondente.
Deng [3] omite detalhes dessa paraleliza¸c˜ao, dizendo apenas que a mesma ´e feita atrav´es
da diretiva task do OpenMP.
2.6.3 T´ecnicas paralelas do alinhamento progressivo
As estrat´egias de alinhamento paralelo mais adotadas utilizam uma abordagem que
considera o alinhamento de cada n´o da ´arvore como uma tarefa primitiva, utiliza o modelo
de comunica¸c˜ao mestre-escravo e utiliza uma estrat´egia de escalonamento dinˆamico. Nesta
2.6 Abordagens paralelas de alinhamento 52
abordagem conforme as tarefas v˜ao se tornando prontas para o processamento - ou seja,
quando seus dados dependentes est˜ao dispon´ıveis - e conforme os processadores se tornam
dispon´ıveis, novos escalonamentos s˜ao realizados. O fluxograma da figura 2.7 mostra, de
forma geral, como ´e feito este escalonamento no processador mestre.
Identificar as
primeiras tarefas
prontas
Enfileirar tarefas
prontas
Escalona primeiras
tarefas enfileiradas
aos escravos ociosos
Há escravo
ocioso?
Sim
Não
Início
É última
tarefa?
Enviar mensagens aos
escravos para enviar e
receber dados dependentes
Fim
Esperar ACK
de um escravo
Dado necessário
está em outro
escravo?
Não
Sim
Sim
Não
Enviar mensagens aos
escravos para executar
tarefas escalonadas
Figura 2.7: Fluxograma do algoritmo do processo mestre do alinhamento progressivo para-
lelo com escalonamento dinˆamico
Cada processador escravo, por sua vez, executa a tarefa a ele associada e armazena
o alinhamento parcial em sua mem´oria local. Caso uma tarefa requisite como entrada
alinhamentos que residem em outros escravos, o mestre envia comandos para estes escravos
solicitando a transferˆencia de seus alinhamentos para o escravo que est´a necessitando.
O fluxograma do algoritmo que ´e executado nos processadores escravos, por sua vez, ´e
ilustrado na figura 2.8.
Algumas estrat´egias prop˜oem, sobre esta abordagem, a manuten¸c˜ao das tarefas ativas
em listas que s˜ao mapeadas de acordo com sua prioridade. A estrat´egia proposta em [12]
´e um exemplo. Nela, utiliza-se uma lista com todas as tarefas ativas em um certo instante
e cujas prioridades s˜ao definidas a partir das informa¸c˜oes de todas as tarefas com as quais
uma certa tarefa est´a relacionada.
O relacionamento das tarefas ´e obtido no processo mestre atrav´es de uma ´arvore de
2.6 Abordagens paralelas de alinhamento 53
Verificar
mensagem
Execução
da tarefa
É comando de
término?
Qual é a TAG?
Não
Dado necessário
está disponível?
Sim
Executar a
tarefa
Armazenar o resultado
em memória local
Enviar dados ao
escravo requisitante
Armazenar dados
em memória
local
Sair
Sim
Requisição
de dados
Não
Recebimento
de dados
Início
Figura 2.8: Fluxograma do algoritmo do processo escravo do alinhamento progressivo pa-
ralelo com escalonamento dinˆamico
tarefas. Esta ´arvore ´e baseada na ´arvore filogen´etica, onde cada n´o interno dessa ´arvore
´e uma tarefa na ´arvore de tarefas. A rela¸c˜ao de dependˆencia entre as tarefas corresponde
aos galhos da ´arvore. N´os que residem em diferentes galhos s˜ao independentes. A figura
2.9 ilustra uma ´arvore filogen´etica e a ´arvore de tarefas obtida.
a b c d e f g h
Árvore filogenética
Árvore de tarefas
7
4
1
2
3
5
6
Figura 2.9: Mapeamento da ´arvore filogen´etica para a ´arvore de tarefas
A partir da ´arvore de tarefas e dos ´ındices das tarefas finalizadas, mant´em-se uma
2.6 Abordagens paralelas de alinhamento 54
lista de tarefas prontas (L
R
) no n´o mestre. Uma tarefa pronta ´e uma tarefa folha ou uma
tarefa com todas as tarefas filhas finalizadas. A estrat´egia proposta em [12] define as
prioridades dessas tarefas segundo uma equa¸c˜ao que considera o seu custo de execu¸c˜ao e
de comunica¸c˜ao e de todas suas tarefas ascendentes. Estes custos s˜ao calculados segundo
uma f´ormula que considera o comprimento das seq
¨
uˆencias e o n´umero de seq
¨
uˆencias da
tarefa.
Nesta estrat´egia, quando uma tarefa ´e finalizada, o processador mestre atualiza a lista
de tarefas prontas com as prioridades. A tarefa de maior prioridade ´e escalonada a um
escravo ocioso.
2.6.4 T´ecnicas paralelas do alinhamento par-a-par
As t´ecnicas paralelas do alinhamento par-a-par realizam um particionamento em n´ıvel
de matriz de programa¸c˜ao dinˆamica. A abordagem de particionamento utilizada nessas t´ec-
nicas ´e a de decomposi¸c˜ao do dom´ınio. A decomposi¸c˜ao funcional n˜ao ´e utilizada uma vez
que para cada elemento da matriz o mesmo processamento ´e realizado e este processamento
´e muito r´apido, portanto invi´avel de ser paralelizado.
A constru¸c˜ao de uma matriz de programa¸c˜ao dinˆamica ´e feita atrav´es de um processo
recursivo, n˜ao sendo poss´ıvel paraleliza-la a grosso modo. Entretanto, em uma menor
granularidade, a decomposi¸c˜ao dos dados pode ser feita. Essa decomposi¸c˜ao deve levar em
conta como os elementos da matriz se relacionam.
Lopes e Moritz [43] investigam essa rela¸c˜ao e mostram que uma matriz pode ser partici-
onada em trˆes regi˜oes principais. Essas regi˜oes, entretanto, s˜ao quase totalmente indepen-
dentes. Uma delas deve ser parcialmente computada para que as demais sejam computadas.
A figura 2.10 mostra esse particionamento.
1
3
2
Figura 2.10: Particionamento da matriz de programa¸c˜ao dinˆamica em trˆes regi˜oes
2.6 Abordagens paralelas de alinhamento 55
Seguindo esta estrat´egia ´e poss´ıvel dividir o processo de constru¸c˜ao dessa matriz em
at´e trˆes processos. A regi˜ao 1 (c´elulas em branco) ´e a que deve ser parcialmente computada
antes das demais. Primeiro computa-se todas as c´elulas desta regi˜ao que s˜ao bordas da
matriz. Em seguida, computa-se a c´elula M(2,2). Neste ponto ´e poss´ıvel iniciar dois
processos paralelos para computar as regi˜oes 2 e 3 ao mesmo tempo. O primeiro processo,
ent˜ao, toma o controle da divis˜ao das tarefas, atribui a dois outros processos a computa¸c˜ao
das c´elulas das regi˜oes 2 e 3 e termina de computar as c´elulas da regi˜ao 1.
Uma t´ecnica mais recente ´e a block-based wavefront [44]. Essa t´ecnica foi utilizada
como base na defini¸c˜ao da estrat´egia de paralelismo do alinhamento par-a-par do MUSCLE,
aplic´avel tanto no est´agio progressivo quanto no est´agio iterativo.
O princ´ıpio desta t´ecnica ´e dividir a matriz de programa¸c˜ao dinˆamica verticalmente
em p grupos, onde p ´e o n´umero de processadores, e associar cada processador `a cada
grupo. Cada grupo cont´em em m´edia o mesmo n´umero de colunas da matriz. As colunas
em cada processador s˜ao ent˜ao agrupadas em blocos de altura a. Este valor deve ser
ajustado de acordo com o n´umero de linhas da matriz. Portanto, a computa¸c˜ao de um
dado bloco requer apenas a ´ultima coluna do bloco imediatamente `a esquerda e o elemento
da diagonal principal - o ´ultimo elemento da ´ultima coluna do bloco da diagonal superior
esquerda -, totalizando a + 1 elementos. O alinhamento paralelo ent˜ao ´e feito calculando-
se os blocos na ordem anti-diagonal, partindo-se do bloco superior esquerdo at´e o bloco
inferior direito. A figura 2.11 mostra um exemplo para uma matriz 16x16 distribu´ıda em
quatro processadores.
1
Processadores
2
23
3
3
4
4
4
4
P4P3P2P1
Figura 2.11: Estrat´egia block-based wavefront
56
3 Detalhamento e
desenvolvimento do projeto
A paraleliza¸c˜ao da ferramenta MUSCLE consiste na paraleliza¸c˜ao de um conjunto de
m´etodos que a comp˜oem e na interliga¸c˜ao desses m´etodos. Cada m´etodo ´e empregado em
uma etapa espec´ıfica do MUSCLE.
Em est´agios distintos do MUSCLE, uma mesma etapa pode se repetir. Entretanto,
m´etodos alternativos podem ser empregados.
´
E o que ocorre na primeira etapa do primeiro
e do segundo est´agio do MUSCLE, respons´avel pelo c´alculo da matriz de distˆancia. Para a
constru¸c˜ao da matriz de distˆancia, utiliza-se o m´etodo de contagem de k-mers no primeiro
est´agio e o m´etodo da identidade fracional no segundo est´agio. As demais etapas, apesar
de contemplarem pequenas altera¸c˜oes em suas implementa¸c˜oes, adaptando o algoritmo ao
tipo de entrada e sa´ıda em cada est´agio, utilizam basicamente o mesmo m´etodo.
Nem todos os m´etodos do MUSCLE, entretanto, foram paralelizados. Para decidir em
quais o paralelismo ´e vantajoso, aplicou-se, inicialmente, testes para verificar a viabilidade
de paralelizar cada um deles. O m´etodo UPGMA, utilizado para a constru¸c˜ao de ´arvo-
res, foi um dos n˜ao paralelizados. Mesmo existindo referˆencias sobre poss´ıveis formas de
paraleliza-lo, este m´etodo apresenta uma complexidade espacial e temporal muito redu-
zida, sendo, portanto, extremamente r´apido. Para entradas com milhares de seq
¨
uˆencias,
o algoritmo seq
¨
uencial do UPGMA levou apenas alguns milisegundos para executar. Pelo
mesmo motivo, o algoritmo de compara¸c˜ao de ´arvores n˜ao foi paralelizado.
Embora todos os m´etodos apresentem uma abordagem mestre-escravo, que contempla
a caracter´ıstica de reunir no mestre os dados gerados em todas as m´aquinas, procurou-
se maximizar o uso da mem´oria distribu´ıda, descentralizando os dados na mem´oria do
3.1 Paraleliza¸c˜ao do m´etodo de contagem de k-mers 57
sistema. Dessa forma, a menor quantidade poss´ıvel de dados foi coletada, mantendo uma
menor quantidade de estruturas no mestre e possibilitando a execu¸c˜ao de problemas muito
grandes sem a exigˆencia de front-ends extremamente potentes em recursos de mem´oria.
Para isto, as entradas e sa´ıdas s˜ao interligadas atrav´es de uma estrutura que armazena a
posi¸c˜ao de todos os dados no sistema distribu´ıdo.
Essa interliga¸c˜ao proporciona al´em de um bom uso da mem´oria dispon´ıvel um melhor
tempo de processamento, uma vez que reduz-se o custo com a comunica¸c˜ao. Adicional-
mente, todos os m´etodos adotam t´ecnicas dinˆamicas de escalonamento, tomando decis˜oes
em tempo de execu¸c˜ao que consideram medidas como custos de comunica¸c˜ao, balancea-
mento de carga, dependˆencia dos dados e ocupa¸c˜ao de processadores. V´arias abordagens
s˜ao propostas e implementadas, e as vantagens e desvantagens, assim como uma descri¸c˜ao
em alto n´ıvel da implementa¸c˜ao de cada uma delas, s˜ao apresentadas nas se¸c˜oes seguintes.
3.1 Paraleliza¸c˜ao do m´etodo de contagem de k-mers
O algoritmo de contagem de k-mers ´e dividido em duas etapas pelo MUSCLE. A
primeira consiste em encontrar a quantidade de tuplas comuns entre todos os pares de
seq
¨
uˆencias, atrav´es da qual mede-se a similaridade entre as seq
¨
uˆencias. A segunda consiste
em encontrar a distˆancia entre essas seq
¨
uˆencias atrav´es de transformadas espec´ıficas. As
distˆancias entre as seq
¨
uˆencias s˜ao encontradas na segunda etapa a partir das medidas de
similaridades encontradas na primeira etapa.
A quantidade de c´alculo realizado na segunda etapa, entretanto, ´e m´ınima quando com-
parada ao c´alculo da primeira etapa. Enquanto que na primeira etapa, verifica-se todos
os caracteres de todos os pares de seq
¨
uˆencias para encontrar as medidas de similaridades
entre as seq
¨
uˆencias, na segunda etapa estima-se a distˆancia apenas com poucas opera¸c˜oes
sobre o valor calculado na primeira etapa. No entanto, uma paraleliza¸c˜ao apenas da pri-
meira etapa exige que quantidades enormes de dados sejam coletados e armazenados no
n´o front-end, prejudicando a escalabilidade do algoritmo. Por este motivo paralelizou-se
ambas as etapas. A figura 3.1 mostra o fluxograma do algoritmo paralelo. Este algoritmo
utiliza o modelo mestre-escravo de distribui¸c˜ao de tarefas e o balanceamento de carga ´e
feito dividindo-se dinamicamente a computa¸c˜ao entre os processos existentes.
3.1 Paraleliza¸c˜ao do m´etodo de contagem de k-mers 58
Envia todas as
para todos os processos
via broadcast
seqüências
Recebe vetor resultante
do processo P
P é maior
que o número de
processos?
Inicio
Sim
Não
Fim
P = 1
P=P+1
Monta, a partir do vetor recebido
parte da matriz de distância *
Recebe todas as
do processo
mestre
seqüências
Inicio
Fim
Obtém a distância entre pares
de seqüências e monta um vetor que
será enviado ao processo mestre **
Envia o vetor ao
processo mestre
* matriz de distância é uma matriz
triangular que contém a distância
entre todos os pares de seqüências
** cada processo é responsável
por calcular linhas específicas da
matriz de distância, definidas a partir
de seu identificador.
Escravos
Mestre
método da
contagem de k-mers
Figura 3.1: Fluxograma do algoritmo paralelo do m´etodo de contagem de k-mers
Inicialmente, todas as seq
¨
uˆencias s˜ao enviadas por broadcast para todos os processos
escravos. O envio por broadcast reduz o overhead com a troca de mensagens, diminuindo o
tempo de comunica¸c˜ao entre os processos. Durante os testes verificou-se que o tempo gasto
com este envio ´e insignificante em rela¸c˜ao ao tempo gasto com a execu¸c˜ao das tarefas.
A distribui¸c˜ao das tarefas ´e feita com base no identificador do processo, atribuindo
a cada processo o c´alculo de linhas espec´ıficas da matriz de distˆancia. Essa matriz ´e
triangular e a forma como ela ´e obtida est´a exemplificada na figura 3.2. Cada processo
calcula inicialmente a linha correspondente ao seu identificador, em um la¸co de passo p,
onde p ´e o n´umero de processos. No exemplo, tem-se sete seq
¨
uˆencias, totalizando sete
linhas na matriz. O primeiro processo ´e respons´avel pelo c´alculo das linhas 1, 4 e 7. O
segundo pelas linhas 2 e 5 e o terceiro pelas linhas 3 e 6. Os valores em cinza s˜ao os
3.2 Paraleliza¸c˜ao do m´etodo da identidade fracional 59
resultados obtidos nos outros escravos e que se juntar˜ao apenas no processo mestre para a
cria¸c˜ao da matriz final de similaridades. Nota-se, neste exemplo, que este escalonamento
tende a uma boa distribui¸c˜ao, para qualquer quantidade de seq
¨
uˆencias envolvidas.
80
92
89
84
90
14
18 59 33
21 39 39 32
21 34 52 71 12 43
25 77
42 14 61 26 35
91
92
1
2
3
4
5
6
7
1234567
Processo 1:
Linhas 1, 4 e 7
Vetor de envio = {80, 18, 59, 33, 89, 21, 34, 52, 71, 12,
43, 90}
80
91
89
92
90
25 77
18 59 33
42 14 61 26 35
21 34 52 71 12 43
14
21 39 39 32
92
84
1
2
3
4
5
6
7
1234567
80
89
90
18 59 33
21 34 52 71 12 43
14
25 77
21 39 39 32
42 14 61 26 35
92
91
84
92
1
2
3
4
5
6
7
1234567
Processo 2:
Linhas 2 e 5
Vetor de envio = {14, 92, 21, 39, 39, 32, 84}
Processo 3:
Linhas 3 e 6
Vetor de envio = {25, 77, 91, 42, 14, 61, 26, 35, 92}
Figura 3.2: Exemplo de como o c´alculo da matriz de similaridades ´e distribu´ıdo entre os
processos
Durante o c´alculo das linhas da matriz de distˆancia, cada processo escravo armazena
os resultados de todas as linhas em um ´unico vetor. Este vetor armazena as distˆancias
calculadas em cada processo e, ao final de todos os c´alculos, ele ´e enviado ao processo
mestre. O processo mestre recebe os vetores de todos os processos e, a partir do vetor e
do identificador do processo remetente, constr´oi a matriz de distˆancia.
3.2 Paraleliza¸c˜ao do m´etodo da identidade fracional
O m´etodo da identidade fracional ´e empregado pelo MUSCLE em seu segundo est´agio,
utilizando como entrada apenas o alinhamento resultante do primeiro est´agio. A execu¸c˜ao
do m´etodo consiste basicamente de dois la¸cos aninhados, que calculam a distˆancia entre
todos os pares de seq
¨
uˆencias.
A vers˜ao paralela deste m´etodo ´e muito similar `a vers˜ao paralela do m´etodo de contagem
de k-mers. Todos os processos recebem inicialmente o alinhamento resultante do primeiro
est´agio via broadcast e iniciam a execu¸c˜ao da tarefa. Cada processo identifica as linhas por
quais ele ´e respons´avel e calcula a distˆancia entre os pares. Os resultados s˜ao armazenados
em um ´unico vetor que ´e enviado ao processo mestre. O processo mestre recebe este vetor
e, a partir do identificador do processo emissor, armazena os valores recebidos nas posi¸c˜oes
3.3 Paraleliza¸c˜ao do alinhamento progressivo 60
corretas da matriz. O fluxograma deste algoritmo ´e bastante similar ao fluxograma do
algoritmo paralelo da contagem de k-mers e ´e mostrado na figura 3.3.
Envia
para todos os processos
via broadcast
alinhamento inicial
Recebe vetor resultante
do processo P
P é maior
que o número de
processos?
Inicio
Sim
Não
Fim
P = 1
P=P+1
Monta, a partir do vetor recebido
parte da matriz de distância *
Recebe
do processo
mestre
alinhamento
inicial
Inicio
Fim
Obtém a distância entre pares
de seqüências alinhadas e monta um
vetor que será enviado ao
processo mestre **
Envia vetor ao
processo mestre
* matriz de distância é uma matriz
triangular que contém a distância
entre todos os pares de seqüências
** cada processo é responsável
por calcular linhas específicas da
matriz de distância, definidas a partir
de seu identificador.
Escravos
Mestre
método da
identidade fracional
Figura 3.3: Fluxograma do algoritmo paralelo do m´etodo da identidade fracional
3.3 Paraleliza¸c˜ao do alinhamento progressivo
Como explicado no cap´ıtulo 2, o alinhamento progressivo consiste em alinhar pares de
perfis, progressivamente, atrav´es de uma ´arvore previamente constru´ıda. O paralelismo de
um problema com essas caracter´ısticas pode ocorrer, fundamentalmente, em dois n´ıveis,
variando a granularidade do paralelismo. O primeiro n´ıvel considera cada n´o da ´arvore como
um ´unico problema, onde cada n´o da ´arvore tem seus dados decompostos e distribu´ıdos.
O segundo n´ıvel escalona n´os inteiros de uma ´arvore.
3.3 Paraleliza¸c˜ao do alinhamento progressivo 61
Ambas as abordagens apresentam suas vantagens e desvantagens. Estrat´egias que
atuam no primeiro n´ıvel, por exemplo, possuem um maior overhead de comunica¸c˜ao, devido
a sua maior granularidade. Entretanto, apresentam um menor overhead de sincronismo,
devido a uma menor dependˆencia dos dados.
Estrat´egias em ambos os n´ıveis foram desenvolvidas neste projeto. Como o paralelismo
no primeiro n´ıvel tamb´em ´e utilizado no est´agio iterativo, este ´e apresentado na se¸c˜ao 3.4.
Esta se¸c˜ao, portanto, exibe apenas as estrat´egias desenvolvidas sobre o segundo n´ıvel, que
considera todo o alinhamento progressivo como um ´unico problema.
3.3.1 Abordagem com gargalo e solu¸c˜oes
Inicialmente s˜ao apresentados os problemas de eficiˆencia encontrados em alguns algo-
ritmos de paraleliza¸c˜ao do alinhamento progressivo. Esses algoritmos, em geral, utilizam
uma abordagem que ´e apresentada em detalhes no artigo [12].
Para diminuir ou eliminar este problema, quatro solu¸c˜oes foram desenvolvidas e imple-
mentadas. Essas solu¸c˜oes apresentam vantagens e desvantagens em diferentes aspectos, e
s˜ao mostradas atrav´es de uma an´alise conceitual.
Os testes de desempenho s˜ao feitos em seguida e s˜ao apresentados no cap´ıtulo 4. Como ´e
feita uma compara¸c˜ao entre as quatro solu¸c˜oes e a abordagem com gargalo, implementou-se
ao todo cinco estrat´egias. Todas essas estrat´egias realizam o escalonamento dinamicamente
e empregam o modelo mestre-escravo de distribui¸c˜ao de tarefas.
3.3.2 O problema da abordagem existente
O mecanismo de escalonamento dinˆamico utilizado por v´arias estrat´egias paralelas
do alinhamento progressivo apresenta um gargalo respons´avel por bloquear a execu¸c˜ao
imediata de tarefas prontas. Este gargalo torna processos dispon´ıveis desnecessariamente
ociosos, e est´a, especificamente, na abordagem de troca de dados adotada. Como pode ser
visto no fluxograma da figura 2.7, sempre que um processo escravo A precisa de dados que
est˜ao armazenados em um processo escravo B, o processo mestre solicita a B o envio desses
dados. Entretanto, B pode estar executando uma tarefa de alinhamento. Neste caso, A
3.3 Paraleliza¸c˜ao do alinhamento progressivo 62
fica ocioso esperando receber de B os dados de entrada necess´arios para processar a nova
tarefa.
Esta espera pode ocorrer freq
¨
uentemente, independente do n´umero de tarefas de ali-
nhamento e do n´umero de processos. A figura 3.4 mostra uma situa¸c˜ao em que pode
ocorrer esta espera. Neste exemplo, apenas o processo D est´a processando uma tarefa de
alinhamento. Os processos A, B e C est˜ao ociosos, esperando dados que est˜ao em D e que
apenas ser˜ao enviados quando o mesmo terminar de processar a tarefa em andamento.
Escravo A
Escravo B
Escravo C
Escravo D
Solicitação de dado dependente ao escravo D
1
3
5
7
12
10
Ocupado
Escravo A Escravo B Escravo C Escravo D
Envio dos dados dependentes aos escravos solicitantes
1
3
5
7
12
10
Ocioso
3
12
5
Figura 3.4: Exemplo de caso da espera pela execu¸c˜ao de processo de escravo vizinho para
envio de dados dependentes
3.3 Paraleliza¸c˜ao do alinhamento progressivo 63
3.3.3 Estrat´egia baseada na abordagem com gargalo
A primeira estrat´egia implementa a abordagem de troca de dados com gargalo. Sua
implementa¸c˜ao foi feita com o intuito de comparar a abordagem existente com as novas
abordagens propostas. Embora Luo [12] proponha o uso de uma lista de prioridades para
reduzir custos de comunica¸c˜ao, seu modelo n˜ao foi implementado. Este modelo define a
ordem de execu¸c˜ao das tarefas com base nos seus custos de execu¸c˜ao e comunica¸c˜ao e,
portanto, n˜ao considera a dependˆencia entre as tarefas. Um modelo de prioridade com o
foco na dependˆencia entre as tarefas considera, por exemplo, a localiza¸c˜ao distribu´ıda dos
dados, administrada atrav´es de uma estrutura no n´o front-end. Este modelo pode diminuir
a latˆencia e os custos com a comunica¸c˜ao e foi utilizado nas novas abordagens definidas.
Dessa forma, a estrat´egia baseada na abordagem com gargalo apenas realiza um esca-
lonamento dinˆamico atrav´es de um modelo de filas sem prioridades.
Implementa¸c˜ao de um modelo de filas sem prioridades
O modelo de filas sem prioridades ´e implementado da seguinte forma. O processo
mestre, inicialmente, distribui todas as tarefas dos n´os folhas entre os processos escravos
dispon´ıveis, atrav´es de um algoritmo de balanceamento de carga. Em seguida, ele espera
pela confirma¸c˜ao de t´ermino de alguma tarefa, seja ela tarefa de n´o folha ou tarefa de
n´o intermedi´ario. Obviamente, as primeiras tarefas finalizadas s˜ao as tarefas de n´o folha.
Ao recebe-las, ele verifica se sua tarefa irm˜a tamb´em est´a finalizada. Caso positivo, a
tarefa de alinhamento do n´o pai do n´o da tarefa finalizada se torna ativa e ´e imediatamente
escalonada. O fluxograma da figura 3.5 mostra o algoritmo do processo mestre. O algoritmo
do processo escravo ´e o mesmo mostrado na figura 2.8.
3.3.4 Novas abordagens paralelas
Visando eliminar ou diminuir o gargalo de troca de dados existente na primeira estrat´e-
gia, quatro poss´ıveis solu¸c˜oes foram definidas. As duas primeiras solu¸c˜oes apresentam uma
abordagem semelhante e s˜ao apresentadas juntas em 3.3.5. As demais solu¸c˜oes apresentam
abordagens pr´oprias e, portanto, s˜ao apresentadas separadamente em 3.3.6 e 3.3.7.
3.3 Paraleliza¸c˜ao do alinhamento progressivo 64
Escalona tarefa do próximo nó
folha para próximo escravo
Escalonar nova tarefa para
o escravo que armazena
a tarefa finalizada
É última
tarefa?
Fim
Sim
Enviar msg ao escravo p/
executar tarefa mapeada
É último
folha?
Espere ACK dos
escravos
Tarefa do nó
irmão também
terminou?
Não
Inicio
Sim
Não
Não
Sim
Enviar mensagens aos
escravos para enviar e
receber dados dependentes
Dado necessário
está em outro
escravo?
Sim
Não
Enviar mensagem ao
escravo para executar
tarefa escalonada
Figura 3.5: Fluxograma do algoritmo do processo mestre da primeira estrat´egia
Todas essas abordagens, entretanto, utilizam uma lista de tarefas ativas e identificam,
dentre essas tarefas, quais podem ser distribu´ıdas para o c´alculo em um determinado ins-
tante, levando-se em conta a localiza¸c˜ao dos dados dependentes e a ociosidade dos proces-
sos. Durante essa identifica¸c˜ao, as tarefas ativas recebem n´ıveis distintos de prioridades,
a partir das quais definem-se os escalonamentos. No entanto, todas as trocas de dados
necess´arias s˜ao feitas entre os processos escravos antes das tarefas serem processadas.
Da mesma forma que na estrat´egia com gargalo, dispensou-se no desenvolvimento das
demais a cria¸c˜ao de uma ´arvore de tarefas. As tarefas ativas s˜ao definidas seguindo a ordem
de t´ermino de suas tarefas filhas, como explicado em 3.3.3. A diferen¸ca ´e que na estrat´egia
com gargalo uma tarefa ativa ´e imediatamente escalonada. Por este motivo, nenhuma lista
´e mantida em mem´oria. Aqui, as tarefas ativas n˜ao s˜ao alocadas ao primeiro processo
ocioso e, portanto, s˜ao armazenadas em uma lista.
3.3 Paraleliza¸c˜ao do alinhamento progressivo 65
3.3.5 Solu¸c˜oes 1 e 2: Escalonar apenas tarefas com dependˆencias
em processos ociosos
Para diminuir a ociosidade com a espera da execu¸c˜ao do processo dependente, identificam-
se nessa abordagem as tarefas da lista de tarefas ativas que n˜ao dependem de dados de
processos ocupados. Ou seja, apenas tarefas em que os resultados das tarefas de ambos os
n´os filhos estejam em processos ociosos. Sobre essas tarefas define-se uma prioridade de
dois n´ıveis: alto e baixo.
Uma tarefa de prioridade baixa ´e uma tarefa que possui dados dependentes em pro-
cessos distintos. Neste caso, ´e necess´ario, no m´ınimo, uma troca de dados. Uma tarefa de
prioridade alta, por sua vez, ´e uma tarefa que possui dados dependentes em um mesmo
processo. Sua prioridade ´e alta pois o n´umero de troca de dados pode ser nulo. Neste caso,
a tarefa pai deve ser escalonada ao mesmo processo de seus dados dependentes.
Quem define o escalonamento com base nessas prioridades ´e a pr´oxima etapa do al-
goritmo. O ponto aqui ´e encontrar os melhores mapeamentos tarefa/processo tais que o
n´umero de troca de dados entre os processos seja minimizado. Este procedimento ´e feito
pelo processo mestre, mapeando primeiramente as tarefas mais priorit´arias e finalizando
quando todos os processos ociosos tiverem sido mapeados ou n˜ao existirem mais tarefas
ativas.
H´a casos, entretanto, em que duas tarefas de prioridade alta cont´em dados dependentes
no mesmo processo. Neste caso, uma tarefa ´e escolhida para o mapeamento e a outra tem
sua prioridade modificada para baixa. Sua prioridade ´e baixa pois, caso esta tarefa seja
mapeada em seguida, todos os seus dados dependentes, que pertencem ao processo mapeado
`a outra tarefa, precisar˜ao ser enviados.
J´a entre duas tarefas de prioridade baixa, o crit´erio que decide o mapeamento ´e a
posi¸c˜ao de um de seus dados dependentes. Se existirem processos que ainda n˜ao foram
mapeados e que cont´em um dos dados dependentes de uma tarefa de prioridade baixa,
um mapeamento ´e feito entre a tarefa e o processo em que encontra-se um de seus dados
dependentes. Dessa forma, apenas uma troca de dados precisa ser feita. Caso isto n˜ao
ocorra para nenhuma das tarefas restantes, o mapeamento ´e escolhido aleatoriamente.
3.3 Paraleliza¸c˜ao do alinhamento progressivo 66
Identificados os melhores mapeamentos, as tarefas s˜ao escalonadas. Entretanto, antes
que o processo mestre envie mensagens de execu¸c˜ao das tarefas aos processos escravos, todas
as trocas de dados s˜ao feitas. Isto impede que ocorra o gargalo existente na abordagem
anterior. Com todas as trocas de dados feitas inicialmente, evita-se que um processo espere
um dado que se encontra em outro processo e que apenas ser´a enviado quando este terminar
de fazer o que est´a fazendo.
Ap´os os dados serem trocados e armazenados localmente, o processo mestre envia as
mensagens de execu¸c˜ao e os processos escravos iniciam o processamento. Em seguida, o
processo mestre espera por mensagens de t´ermino dessas tarefas.
As duas primeiras solu¸c˜oes seguem esta abordagem, por´em diferem na forma em que
esperam as mensagens de t´ermino dessas tarefas. Enquanto a primeira espera por todas as
tarefas que est˜ao em processamento, a segunda espera que apenas uma delas seja finalizada.
Essas solu¸c˜oes levaram ao desenvolvimento das estrat´egias waitall (primeira solu¸c˜ao) e
waitany (segunda solu¸c˜ao).
A vantagem da estrat´egia waitall ´e que no momento de fazer os pr´oximos escalona-
mentos, todos os processos escravos est˜ao dispon´ıveis. Assim, ´e prov´avel que uma maior
quantidade de tarefas seja escalonada simultaneamente, uma vez que n˜ao existe a barreira
de obter um dado necess´ario em um processo ocupado.
A vantagem da estrat´egia waitany, por outro lado, ´e que ap´os uma tarefa ser finalizada,
o processo mestre tenta imediatamente escalonar uma tarefa pronta, sem que seja necess´ario
esperar pelo t´ermino das tarefas dos demais processos escravos. Enquanto uma abordagem
apresenta a vantagem de ter uma quantidade maior de escalonamentos simultˆaneos, a outra
apresenta a vantagem de eliminar a espera do processamento das demais tarefas.
O fluxograma do processo mestre ´e mostrado atrav´es da figura 3.6 e o fluxograma do
processo escravo atrav´es da figura 3.7. A parte do algoritmo em que as estrat´egias waitall
e waitany diferem entre si ´e mostrada atrav´es da condicional em negrito no fluxograma do
processo mestre.
Essa abordagem n˜ao elimina completamente o gargalo pois considera apenas tarefas cu-
jos dados dependentes est˜ao em processos ociosos. Caso, em um instante de escalonamento,
3.3 Paraleliza¸c˜ao do alinhamento progressivo 67
Escalonar as tarefas de nó
folha aos escravos ociosos
Enviar mensagens aos escravos
para executar tarefas escalonadas
Enviar mensagens para esses escravo
executarem as tarefas escalonadas
Esperar ACK de TODAS
tarefas dos escravos
Início
Construir lista de tarefas
prontas ( )L
R
Construir lista de próximas
tarefas a partir de ,
considerando a ociosidade
dos processos escravos*
L
R
Fazer os mapeamentos
tarefa/processo de forma a
minimizar o número de trocas
de dados entre os escravos
* A lista de próximas tarefas apenas contém tarefas que
utilizam dados que estão localizados em escravos ociosos.
Enviar mensagens aos
escravos para enviar e
receber dados dependentes
Esperar pelo ACK de
TODAS tarefas
dos escravos
Atualizar a lista de
tarefas prontas ( )L
R
Qual método?
Esperar ACK de
QUALQUER tarefa
dos escravos
Wait_All Wait_Any
É última
tarefa?
Fim
Sim
Não
Figura 3.6: Fluxograma do processo mestre das estrat´egias waitall e waitany
existam apenas tarefas ativas que cont´em dados que est˜ao em processos ocupados, os pro-
cessos ociosos continuar˜ao ociosos e nenhuma tarefa ser´a escalonada. Ou seja, o gargalo
nesta abordagem existe, por´em de forma reduzida em rela¸c˜ao `a abordagem existente.
3.3.6 Solu¸c˜ao 3: Fazer c´opia de todos os dados no processo mes-
tre
A terceira solu¸c˜ao elimina o gargalo na troca de dados. A id´eia desta solu¸c˜ao ´e copiar
o resultado de um alinhamento ao processo mestre sempre que um alinhamento ´e finali-
zado. Assim, sempre que um processo se torna ocioso, qualquer tarefa da lista de tarefas
3.3 Paraleliza¸c˜ao do alinhamento progressivo 68
Verificar
mensagem
Execução
da tarefa
É comando de
término?
Qual é a TAG?
Não
Executar a
tarefa
Armazenar o resultado
em memória local
Enviar dados ao
escravo requisitante
Armazenar
dados em
memória local
Sair
Sim
Requisição
de dados
Recebimento
de dados
Início
Figura 3.7: Fluxograma do processo escravo das estrat´egias waitall e waitany
ativas pode ser escalonada, independente da posi¸c˜ao de seus dados dependentes. Caso esta
tarefa necessite de um dado, uma mensagem ´e enviada ao processo mestre que o envia
imediatamente.
O processo mestre, portanto, al´em de coordenar a execu¸c˜ao das tarefas, tamb´em ´e
respons´avel por manter c´opias e enviar dependˆencias, quando necess´ario. A opera¸c˜ao de
c´opia de dados ´e feita sempre, pois n˜ao h´a como saber no futuro se aquele dado necessitar´a
ou n˜ao ser enviado. J´a a opera¸c˜ao de envio de dados ´e feita apenas quando uma tarefa ´e
executada em um processo que n˜ao cont´em todos os seus dados dependentes.
Caso uma tarefa seja escalonada a um processo que cont´em em mem´oria local todas as
suas dependˆencias, nenhuma troca de dados ´e feita. Caso este processo contenha apenas
uma dependˆencia, apenas uma troca de dados ´e feita. Se ambas as dependˆencias n˜ao est˜ao
em mem´oria local, ´e necess´ario duas trocas de dados.
Para minimizar o n´umero de troca de dados em um certo instante de escalonamento,
trˆes n´ıveis de prioridades s˜ao utilizados: alto, quando ambos os dados dependentes est˜ao
no mesmo processo ocioso; m´edio, quando ambos os dados dependentes est˜ao em processos
distintos, por´em um deles est´a em um processo ocioso; e baixo, quando ambos os dados
dependentes est˜ao em processos ocupados.
3.3 Paraleliza¸c˜ao do alinhamento progressivo 69
Ap´os a prioridade ser atribu´ıda `as tarefas, definem-se os mapeamentos tarefa/processo
que minimizam o n´umero de trocas de dados. Inicialmente mapeiam-se as tarefas de prio-
ridade alta, em seguida as tarefas de prioridade m´edia e, por fim, as tarefas de prioridade
baixa. Este procedimento finaliza quando todos os processos ociosos tiverem sido mapeados
ou n˜ao existirem mais tarefas ativas.
Quando duas tarefas de prioridade alta cont´em dados dependentes no mesmo processo,
uma tarefa ´e escolhida para o escalonamento e a outra tem sua prioridade modificada para
baixa. Sua prioridade ´e baixa pois, caso esta tarefa seja escalonada a outro processo, todos
os seus dados dependentes precisar˜ao ser enviados.
Uma tarefa de prioridade m´edia, por sua vez, pode conter dados em processos que j´a
foram mapeados. Neste caso, a prioridade desta tarefa ´e modificada para baixa. Caso
contr´ario, ´e feito um mapeamento tarefa/processo tal que o processo contenha um dos
dados dependentes da tarefa. Por fim, s˜ao feitos os mapeamentos das tarefas de prioridade
baixa. Como todos os processos restantes n˜ao cont´em dados das tarefas restantes, sendo
sempre necess´ario duas trocas de dados, esses mapeamentos s˜ao feitos aleat´oriamente.
Da mesma forma que na solu¸c˜ao 1 e 2, todas as trocas de dados s˜ao feitas inicialmente.
Em seguida, mensagens de execu¸c˜ao s˜ao enviadas `as tarefas mapeadas. Ap´os a execu¸c˜ao,
todos os dados dependentes s˜ao dinamicamente eliminados da mem´oria.
A estrat´egia sendmaster foi criada contemplando as caracter´ısticas dessa solu¸c˜ao. O
algoritmo do processo mestre desta estrat´egia ´e mostrada pelo fluxograma da figura 3.8.
O fluxograma do algoritmo do processo escravo, por sua vez, ´e visto na figura 3.9.
Esta estrat´egia elimina completamente o gargalo de dependˆencia na troca de dados
pois permite que qualquer tarefa ativa seja escalonada no momento em que um processo
se torna ocioso. Entretanto, o custo com a comunica¸c˜ao ´e muito elevado, piorando, por
outro lado, o desempenho do algoritmo. Adicionalmente, a mem´oria do n´o front-end deve
ser capaz de suportar todas as c´opias de dados, caso contr´ario ela ´e um grande gargalo.
3.3 Paraleliza¸c˜ao do alinhamento progressivo 70
Escalonar próxima tarefa
pronta para o próximo escravo
Enviar mensagem para o
escravo executar tarefa escalonada
Tarefa é último
nó folha?
Esperar ACK de
TODAS tarefas
Início
Sim
Não
Construir lista de tarefas prontas ( )L
R
Define as prioridades das tarefas
Faz mapeamento das tarefas mais prioritárias*
* Se necessário, após cada mapeamento tarefa/processo,
as prioridades de outras tarefas são redefinidas.
Atualizar lista de tarefas
prontas ( )L
R
Esperar ACK de
QUALQUER tarefa
Esta tarefa é
a última?
Fim
Sim
Não
Há escravo
ocioso?
Sim
Não
Enviar dados
dependentes
Algum dado
requerido se encontra
em outro escravo?
Sim
Não
Enviar mensagens para
os escravos executarem
as tarefas escalonadas
Receber resultado e
armazenar localmente
Figura 3.8: Fluxograma do algoritmo do processo mestre da estrat´egia sendmaster
3.3.7 Solu¸c˜ao 4: Criar threads exclusivos para a troca de dados
A ´ultima solu¸c˜ao tamb´em elimina o gargalo na troca de dados. Sempre que um processo
se torna ocioso e existem tarefas ativas, um escalonamento ´e realizado. Este escalonamento
´e feito independente da posi¸c˜ao dos dados dependentes e ´e obtido diretamente do processo
escravo que o cont´em, reduzindo o custo de comunica¸c˜ao em rela¸c˜ao `a solu¸c˜ao anterior e
a prov´avel ocorrˆencia de um gargalo de mem´oria. Para isso, um thread exclusivo para a
troca de dados ´e disparado em cada processo escravo.
Com o uso de threads, processos ocupados compartilham seus recursos para que o dado
seja enviado imediatamente, evitando a espera com o t´ermino de execu¸c˜ao do processo. A
3.3 Paraleliza¸c˜ao do alinhamento progressivo 71
Verificar
mensagem
Execução
da tarefa
É comando de
término?
Qual é a TAG?
Não
Executar a
tarefa
Armazenar o resultado
em memória local
Enviar dados ao
processo mestre
Armazenar
dados em
memória local
Sair
Sim
Recebimento
de dados
Início
Figura 3.9: Fluxograma do algoritmo do processo escravo da estrat´egia sendmaster
desvantagem ´e que nem todas as implementa¸c˜oes do MPI contemplam o uso de threads,
impossibilitando a execu¸c˜ao de tal estrat´egia.
As prioridades e o mecanismo de escalonamento desta abordagem s˜ao semelhantes aos
da solu¸c˜ao anterior. Trˆes n´ıveis de prioridades s˜ao definidos e os mapeamentos s˜ao feitos
de modo a minimizar o n´umero de troca de dados.
Definidos todos os mapeamentos tarefa/processo, as trocas de dados s˜ao feitas e, em
seguida, todas as mensagens de execu¸c˜ao s˜ao enviadas. Este procedimento continua at´e que
todas as tarefas sejam finalizadas e os escalonamentos s˜ao feitos ap´os cada processador se
tornar ocioso. As figuras 3.10 e 3.11 mostram os fluxogramas no processo mestre e escravo,
respectivamente, da estrat´egia implementada sobre esta abordagem.
3.3.8 Considera¸c˜oes sobre as implementa¸c˜oes no segundo est´agio
No segundo est´agio de execu¸c˜ao do MUSCLE, o alinhamento progressivo ´e feito se-
guindo uma nova ´arvore guia. Para evitar redundˆancia de c´alculo, faz-se inicialmente uma
compara¸c˜ao da nova ´arvore com a ´arvore constru´ıda no primeiro est´agio e realizam-se novos
alinhamentos par-a-par apenas nos n´os que sofreram modifica¸c˜oes.
3.3 Paraleliza¸c˜ao do alinhamento progressivo 72
Escalonar próxima tarefa
pronta para o próximo escravo
Enviar mensagem para o
escravo executar tarefa escalonada
Tarefa é último
nó folha?
Esperar ACK de
TODAS tarefas
Início
Sim
Não
Construir lista de tarefas prontas ( )L
R
Define as prioridades das tarefas
Faz mapeamento das tarefas mais prioritárias*
* Se necessário, após cada mapeamento tarefa/processo,
as prioridades de outras tarefas são redefinidas.
Atualizar lista de tarefas
prontas ( )L
R
Enviar mensagens de “Fim
de Thread” para TODOS escravos
Esperar ACK de
QUALQUER tarefa
Esta tarefa é
a última?
Fim
Sim
Não
Enviar mensagens de “Criação de
Threads” para TODOS escravos
Há escravo
ocioso?
Sim
Não
Enviar mensagens para os
escravos enviarem e rece-
berem os dados dependentes
Algum dado
requerido se encontra
em outro escravo?
Sim
Não
Enviar mensagens para
os escravos executarem
as tarefas escalonadas
Figura 3.10: Fluxograma do algoritmo do processo mestre da estrat´egia com threads
As estrat´egias utilizadas s˜ao as mesmas descritas anteriormente, a diferen¸ca ocorre ape-
nas na implementa¸c˜ao, que contempla caracter´ısticas espec´ıficas deste est´agio. Um exemplo
´e o tipo de dado de entrada utilizado e a disposi¸c˜ao desses dados no sistema. Enquanto no
primeiro est´agio, os dados de entrada encontram-se no processo mestre e estes s˜ao enviados
aos processos escravos, no segundo est´agio, os dados de entrada est˜ao distribu´ıdos entre os
v´arios processos escravos. No segundo est´agio, utiliza-se tamb´em uma estrutura adicional
para evitar os c´alculos redundantes na etapa do alinhamento progressivo.
3.4 Paraleliza¸c˜ao do alinhamento par-a-par 73
Verificar
Mensagem
Fim
Início
Qual é a TAG?
Criar thread
Verificar
mensagem
Início thread
Enviar dado para
o escravo requisitante
Qual é a TAG?
Fim
Armazenar dado
em memória local
Fim
Criação de Thead
Fim de
thread
Recebimento
de dado
Envio de
dado
Execução
de tarefa
Dado requerido
está disponível?
Sim
Executar a
tarefa
Armazenar o resultado
em memória local
Não
Figura 3.11: Fluxograma do algoritmo do processo escravo da estrat´egia com threads
3.4 Paraleliza¸c˜ao do alinhamento par-a-par
O paralelismo do alinhamento par-a-par ´e utilizado no est´agio iterativo e progressivo
do MUSCLE. No est´agio iterativo, este paralelismo ocorre na fun¸c˜ao que demanda o maior
3.4 Paraleliza¸c˜ao do alinhamento par-a-par 74
custo computacional dentro de cada itera¸c˜ao. Nos est´agios progressivos, este paralelismo
substitui o paralelismo feito em fun¸c˜ao da ´arvore filogen´etica. Com esta abordagem, cada
n´o da ´arvore ´e paralelizado.
As implementa¸c˜oes das estrat´egias de alinhamento par-a-par sofrem pequenas varia¸c˜oes
de acordo com o est´agio. No est´agio iterativo, o alinhamento ´e feito sobre um conjunto de
seq
¨
uˆencias alinhadas enquanto que no est´agio progressivo o alinhamento ´e feito sobre dois
perfis de alinhamento.
No est´agio iterativo as seq
¨
uˆencias s˜ao dividas em dois sub-conjuntos. Esses sub-
conjuntos s˜ao alinhados atrav´es da matriz de programa¸c˜ao dinˆamica. Inicialmente, obt´em-
se um caminho a ser percorrido na matriz para a constru¸c˜ao do alinhamento. Em seguida,
utilizando uma t´ecnica conhecida por tracebak, obt´em-se o alinhamento resultante.
No est´agio progressivo, o alinhamento de dois perfis tamb´em ´e feito atrav´es de uma
matriz de programa¸c˜ao dinˆamica obtendo-se inicialmente um caminho. Este caminho,
entretanto, ´e utilizado na constru¸c˜ao de um novo perfil. Apenas no n´o raiz da ´arvore o
perfil resultante ´e convertido em um alinhamento.
Para decidir qual estrat´egia paralela adotar em cada caso, estudou-se, primeiramente,
o custo com a comunica¸c˜ao. Dependendo da quantidade dos dados trocados, o overhead
com a comunica¸c˜ao pode inviabilizar o uso de estrat´egias paralelas. Esta an´alise respeita
as caracter´ısticas especificas da implementa¸c˜ao do alinhamento par-a-par em cada est´agio.
No est´agio progressivo, os dados de entrada e sa´ıda s˜ao perfis de alinhamento. No est´a-
gio iterativo, esses dados s˜ao os pr´oprios alinhamentos, representados atrav´es de conjuntos
alinhados de seq
¨
uˆencias. Uma solu¸c˜ao consiste em obter o resultado no front-end (um
novo perfil ou um novo alinhamento) e enviar esses dados para todos os processos escravos
para que o processamento paralelo da pr´oxima etapa seja feito. Uma an´alise te´orica da
transmiss˜ao foi feita para ambos os est´agios, atrav´es de uma investiga¸c˜ao no c´odigo-fonte
do MUSCLE. No est´agio iterativo, para alinhamentos de n seq
¨
uˆencias de tamanho L, o
custo com a comunica¸c˜ao ´e O(nL). No est´agio progressivo, considerando que cada coluna
de um perfil possui um conjunto de vari´aveis que totalizam 467 bytes, identificado atrav´es
de uma inspe¸c˜ao em seu c´odigo fonte, a transmiss˜ao de um ´unico perfil de tamanho L tem
um custo de comunica¸c˜ao de O(467L), independente da quantidade de seq
¨
uˆencias que cada
3.4 Paraleliza¸c˜ao do alinhamento par-a-par 75
perfil representa.
Para reduzir o overhead com a comunica¸c˜ao, uma solu¸c˜ao foi enviar os dados necess´arios
para o c´alculo de cada perfil/alinhamento e replicar o c´alculo em todas as m´aquinas. Esta
solu¸c˜ao ´e poss´ıvel desde que todos os n´os contenham os perfis dos n´os filhos (no est´agio
progressivo) ou o alinhamento imediatamente anterior (no est´agio iterativo). A fun¸c˜ao que
calcula o perfil/alinhamento resultante utiliza os perfis filhos ou o alinhamento anterior
junto com o caminho. Esta solu¸c˜ao ´e vi´avel pois este c´alculo ´e relativamente mais r´apido
que a comunica¸c˜ao e ´e feito simultaneamente em todos os processos. Os dados de um
caminho de alinhamento s˜ao sempre 9 bytes para cada coluna do perfil, acrescentados de
8 bytes de vari´aveis de controle. Neste caso, o custo de comunica¸c˜ao ´e 8 + 9L para perfis
de tamanho L, reduzindo em aproximadamente 52 vezes a quantidade de dados enviados
em rela¸c˜ao ao envio do perfil, e n/9, desde que n > 9, em rela¸c˜ao ao envio do alinhamento.
Enquanto por um lado esta ´ultima solu¸c˜ao apresenta a vantagem de gerar um menor
overhead de comunica¸c˜ao, o processamento do sistema ´e totalmente utilizado. A solu¸c˜ao
que envia o caminho e replica o processamento ´e mais vantajosa em sistemas dedicados ou
em casos onde a rede do sistema ´e relativamente lenta. Por´em, analisando apenas o tempo
de execu¸c˜ao do algoritmo, ela ´e prefer´ıvel em rela¸c˜ao a solu¸c˜ao que envia o alinhamento j´a
pronto. Ambas, portanto, foram implementadas no MUSCLE.
No est´agio progressivo, as redundˆancias dos perfis filhos s˜ao eliminadas conforme os
perfis pais s˜ao calculados ou caso este seja o perfil do n´o raiz. Caso o algoritmo seja
executado no primeiro est´agio, apenas um processo o mant´em armazenado, atrav´es de um
algoritmo que mant´em uma boa distribui¸c˜ao dos dados entre os processos. Uma c´opia
´e mantida pois ela ´e utilizada no segundo est´agio progressivo. Caso o algoritmo seja
executado no segundo est´agio, todos as c´opias s˜ao eliminadas, mantendo em todos os
processos apenas os perfis recentemente calculados, que s˜ao utilizados para o c´alculo de
novos perfis.
Seguindo as caracter´ısticas de cada est´agio, trˆes estrat´egias de paralelismo foram desen-
volvidas. Todas utilizam a t´ecnica block-based wavefront [44], explicada em 2.11, atrav´es de
um modelo mestre/escravo. Entretanto, ao contr´ario do proposto em [44], implementou-
se um algoritmo que possibilita o ajuste do tamanho dos blocos da matriz em ambas as
3.4 Paraleliza¸c˜ao do alinhamento par-a-par 76
dimens˜oes, como explicado em 3.4.2.
3.4.1 Estrat´egias implementadas sobre ambas as solu¸c˜oes
As duas primeiras estrat´egias enviam os dados da matriz de programa¸c˜ao dinˆamica
para o processo mestre, calculando o caminho no processo mestre de forma seq
¨
uencial.
A t´ecnica traceback pode ent˜ao ser executada de duas formas. Ou ela ´e executada no
processo mestre, e o perfil/alinhamento resultante propagado em todos os processos, ou
ela ´e executada em todos os processos, obtendo-se os resultados localmente. Uma an´alise
te´orica dessas abordagens ´e feita na se¸c˜ao 3.4.
Essas duas estrat´egias diferem, entretanto, na forma como os dados s˜ao enviados. En-
quanto uma delas envia todos os dados de uma s´o vez ap´os todo o processamento, a outra
envia os dados em partes, em momentos distintos da execu¸c˜ao do algoritmo.
A vantagem da primeira estrat´egia ´e que uma ´unica mensagem ´e enviada por processo,
e portanto h´a um menor custo de comunica¸c˜ao. A segunda estrat´egia, por outro lado,
diminui o overhead de sincronismo, pois enquanto h´a processos se comunicando tamb´em
h´a processos trabalhando. Em ambos os casos, o overhead com a comunica¸c˜ao ´e muito alto
e s˜ao estrat´egias praticamente invi´aveis.
Para minimizar o overhead exagerado de comunica¸c˜ao dessas estrat´egias, uma terceira
foi definida. A terceira estrat´egia realiza o c´alculo do caminho de forma distribu´ıda. Esta
estrat´egia, al´em de diminuir o overhead de comunica¸c˜ao, evita que uma quantidade enorme
de dados, que est˜ao distribu´ıdos, se reunam em um ´unico ponto (front-end), potencializando
a ocorrˆencia de um gargalo.
A distribui¸c˜ao do c´alculo do caminho ´e feito da seguinte forma. Ao terminar o c´alculo
da matriz de programa¸c˜ao dinˆamica, o ´ultimo processo escravo inicia a t´ecnica traceback.
Esta t´ecnica parte do ´ultimo elemento da matriz e vai at´e o primeiro, verificando em cada
elemento qual o tipo de opera¸c˜ao que est´a a ele associado, a partir do qual identifica-se
o pr´oximo elemento da matriz que ser´a examinado. Quando um certo elemento deve ser
verificado e este encontra-se em outro processo, uma mensagem ´e enviada solicitando a
continua¸c˜ao da opera¸c˜ao.
3.5 Paraleliza¸c˜ao do c´alculo da pontua¸c˜ao objetiva 77
3.4.2 O tamanho dos blocos da matriz
A t´ecnica block-based wavefront divide a matriz em p colunas, onde p ´e o n´umero de
processadores. As colunas, por sua vez, s˜ao dividas em b blocos, de acordo com o n´umero
de linhas da matriz. Ao inv´es de definir estaticamente a quantidade de blocos por coluna
(b) e definir o n´umero de colunas (p) apenas com base no n´umero de processadores, esta
t´ecnica recebe como entrada os valores do tamanho horizontal e vertical m´ınimo de cada
bloco. A partir desses valores define-se, ent˜ao, o n´umero de blocos.
Com esta estrat´egia, a quantidade de colunas pode variar de 2 a p blocos, enquanto
que em linhas este valor ´e limitado pelo tamanho do perfil/alinhamento. Isto permite
que uma quantidade vari´avel de processos sejam utilizados para cada opera¸c˜ao, de acordo
com o volume de dados. Este ajuste autom´atico no n´umero de processadores impede que
seq
¨
uˆencias pequenas sejam distribu´ıdas em muitos processadores, impedindo a gera¸c˜ao de
um overhead de comunica¸c˜ao que degrade o desempenho do algoritmo.
O tamanho m´ınimo ideal de um bloco depende de fatores como velocidade de proces-
samento e comunica¸c˜ao de um sistema. Por este motivo, este valor n˜ao ´e fixo e deve ser
ajustado de acordo com as caracter´ısticas de cada sistema. Como um futuro trabalho esses
ajustes podem ser feitos dinamicamente, definindo-se parˆametros de desempenho cr´ıticos
e obtendo-os atrav´es de testes r´apidos no in´ıcio da execu¸c˜ao do algoritmo. No algoritmo
desenvolvido, entretanto, a op¸c˜ao autom´atica atua como a estrat´egia proposta em [44].
Esta op¸c˜ao divide a matriz em p linhas e p colunas e ´e executada caso nenhuma medida
de tamanho de bloco seja informada na chamada de execu¸c˜ao. Esta op¸c˜ao foi utilizada nos
testes comparativos das trˆes estrat´egias, como mostrado na se¸c˜ao 4.4.1, e, apesar de n˜ao
ser a melhor op¸c˜ao, apresenta, em geral, um bom comportamento.
3.5 Paraleliza¸c˜ao do c´alculo da pontua¸c˜ao objetiva
A paraleliza¸c˜ao deste m´etodo ´e semelhante a do m´etodo da contagem de k-mers e do
m´etodo da identidade fracional. A diferen¸ca ´e que aqui calcula-se pontua¸c˜oes de colunas
espec´ıficas de um alinhamento.
3.5 Paraleliza¸c˜ao do c´alculo da pontua¸c˜ao objetiva 78
A distribui¸c˜ao das colunas aqui tamb´em ´e feita com base no identificador do processo.
Cada processo calcula inicialmente a coluna correspondente ao seu identificador, e percorre
o alinhamento calculando pontua¸c˜oes de colunas espec´ıficas dentro de um la¸co de passo p,
onde p ´e o n´umero de processos.
A pontua¸c˜ao das colunas ´e somada em cada processo e o resultado final enviado ao
processo mestre. O processo mestre recebe todos os valores e soma-os, obtendo a pontua¸c˜ao
resultante.
79
4 Testes e Resultados
Muitos experimentos foram realizados para testar o desempenho dos algoritmos pa-
ralelos propostos. As seq
¨
uˆencias utilizadas foram extra´ıdas da base de dados do NCBI
(www.ncbi.nlm.nih.gov) com o foco apenas no n´umero de seq
¨
uˆencias e no n´umero de res´ı-
duos em cada seq
¨
uˆencia. Para cada teste feito, descreve-se as informa¸c˜oes espec´ıficas da
instˆancia do problema utilizada, como o n´umero de seq
¨
uˆencias e o comprimento m´edio das
seq
¨
uˆencias.
Os testes foram executados em um cluster Beowulf constitu´ıdo de 16 m´aquinas, cada
uma com um processador Intel(R) Pentium(R) 4 CPU 2.80GHz e 1GB de mem´oria. Estas
m´aquinas est˜ao conectadas atrav´es de um switch dedicado de 100 Mb/s. Os testes foram
executados no cluster com um n´umero crescente de processadores, permitindo-nos analisar
a escalabilidade do algoritmo. Os tempos de execu¸c˜ao do algoritmo foram calculados
executando-os em modo stand-alone, para garantir o uso exclusivo de comunica¸c˜ao, CPU
e mem´oria.
Cada t´opico deste cap´ıtulo refere-se a um m´etodo do MUSCLE paralelizado, e cuja
descri¸c˜ao encontra-se no cap´ıtulo 3. Todas as informa¸c˜oes de cada teste, bem como seus
respectivos resultados, s˜ao apresentadas a seguir.
4.1 Contagem de k-mers
Para verificar a eficiˆencia deste m´etodo, realizou-se testes com v´arias entradas distintas.
Para cada arquivo de entrada, verificou-se como o algoritmo se comporta quando executado
em um n´umero crescente de m´aquinas. Deve-se notar, por´em, que um sistema m´ınimo para
4.1 Contagem de k-mers 80
a execu¸c˜ao do algoritmo paralelo consiste de dois processos, pois tal algoritmo ´e do tipo
mestre-escravo. Ou seja, um processo ´e respons´avel apenas pelo gerenciamento dos dados.
Dessa forma, os resultados da execu¸c˜ao em apenas um n´o podem ser obtidos com a vers˜ao
seq
¨
uencial do algoritmo ou com a execu¸c˜ao de dois processos em uma ´unica m´aquina. Como
optou-se por calcular o speedup real a primeira alternativa foi adotada.
A primeira classe de entradas mant´em constante o comprimento m´edio (n´umero m´e-
dio de res´ıduos) das seq
¨
uˆencias, variando apenas o n´umero de seq
¨
uˆencias envolvidas. O
comprimento de cada seq
¨
uˆencia, nessas entradas, ´e de aproximadamente 1000. Ao todo,
quatro entradas distintas foram utilizadas. Essas entradas cont´em 500, 1000, 2000 e 4000
seq
¨
uˆencias.
As figuras 4.1 e 4.2 mostram o comportamento do algoritmo para essa primeira classe de
entrada. Para cada uma das quatro entradas, essas figuras mostram o tempo de execu¸c˜ao
e o speedup real do algoritmo.
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
número de processadores
tempo de execução (s)
Figura 4.1: Gr´afico de tempo de execu¸c˜ao do algoritmo paralelo de contagem de k-mers
para entradas com seq
¨
uˆencias de aproximadamente 1000 res´ıduos
A segunda classe de testes tamb´em mant´em constante o comprimento das seq
¨
uˆencias,
por´em cada seq
¨
uˆencia possui um tamanho consideravelmente menor em rela¸c˜ao ao tamanho
das seq
¨
uˆencias da primeira classe de entradas. Aqui, cada seq
¨
uˆencia possui em m´edia 50
res´ıduos. O n´umero de seq
¨
uˆencias, por outro lado, ´e variado. Utilizou-se, ao todo, trˆes
4.1 Contagem de k-mers 81
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
número de processadores
speedup real
Figura 4.2: Gr´afico de speedup real do algoritmo paralelo de contagem de k-mers para
entradas com seq
¨
uˆencias de aproximadamente 1000 res´ıduos
entradas, com 3000, 4000 e 5000 seq
¨
uˆencias. Para cada entrada, as figuras 4.3 e 4.4
mostram, respectivamente, o tempo de execu¸c˜ao e o speedup real do algoritmo para um
n´umero crescente de processadores.
3000 seqüências
4000 seqüências
5000 seqüências
número de processadores
tempo de execução (s)
Figura 4.3: Gr´afico de tempo de execu¸c˜ao do algoritmo paralelo de contagem de k-mers
para entradas com seq
¨
uˆencias de aproximadamente 50 res´ıduos
4.1 Contagem de k-mers 82
3000 seqüências
4000 seqüências
5000 seqüências
número de processadores
speedup real
Figura 4.4: Gr´afico de speedup real do algoritmo paralelo de contagem de k-mers para
entradas com seq
¨
uˆencias de aproximadamente 50 res´ıduos
A partir dos testes anteriores, ´e poss´ıvel comparar o ganho de desempenho do algoritmo
para entradas com o mesmo n´umero de seq
¨
uˆencias, por´em de comprimentos diferentes.
Para isso, obteve-se o comportamento das entradas com 4000 seq
¨
uˆencias da primeira e
da segunda classe. A figura 4.5 mostra uma compara¸c˜ao do speedup real nos dois casos.
Note que a execu¸c˜ao do programa com uma entrada com seq
¨
uˆencias de maior comprimento
apresenta um maior ganho de desempenho com um n´umero maior de n´os, confirmando a
caracter´ıstica de escalabilidade do algoritmo.
Para visualizarmos a quantidade de overhead de comunica¸c˜ao e sincronismo neste algo-
ritmo, extraiu-se, por fim, o perfil de execu¸c˜ao de uma das entradas. A entrada escolhida
foi a de 500 seq
¨
uˆencias com aproximadamente 1000 res´ıduos cada. O algoritmo, por sua
vez, foi executado utilizando-se apenas quatro n´os do cluster. Essa escolha foi feita de
forma a manter um overhead m´ınimo gerado pela instrumenta¸c˜ao do c´odigo, ao mesmo
tempo em que testou-se um caso com uma quantidade consider´avel de dados de entrada.
A figura 4.6 mostra o tempo gasto com o overhead de comunica¸c˜ao e sincronismo obtido a
partir do perfil dessa execu¸c˜ao.
Nesta figura, as barras indicam o percentual de tempo gasto com as fun¸c˜oes de comu-
nica¸c˜ao e sincronismo do MPI. Essas fun¸c˜oes podem estar trocando dados, esperando um
4.1 Contagem de k-mers 83
Comprimento médio: 50
Comprimento médio: 1000
número de processadores
speedup real
Figura 4.5: Gr´afico de compara¸c˜ao do speedup real do algoritmo paralelo de contagem de
k-mers para entradas com 4000 seq
¨
uˆencias de aproximadamente 50 e 1000 res´ıduos
= 1,95s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.6: Percentual de tempo gasto com comunica¸c˜ao e sincronismo do algoritmo de
contagem de k-mers para a entrada com 500 seq
¨
uˆencias de aproximadamente 1000 res´ıduos
momento para o recebimento ou envio de dados (comunica¸c˜ao s´ıncrona) ou simplesmente
esperando outros processos atrav´es de fun¸c˜oes de sincronismo. Em todos esses casos, o
uso de processador ´e m´ınimo. O percentual de tempo em que o processador fica de fato
ocupado ´e representado pelo espa¸co ap´os as barras. Essa informa¸c˜ao ´e mostrada para cada
processo.
4.2 Identidade fracional 84
O processador com identificador zero ´e o processador mestre. Sua fun¸c˜ao ´e de apenas
distribuir os dados, receber os resultados e junta-los para formar o resultado final. Neste
processo, a maior parte do tempo ´e gasto com a espera dos dados, atrav´es de uma fun¸c˜ao
de recebimento s´ıncrono do MPI (fun¸c˜ao MPI_Recv). Os processos escravos, por outro
lado, passam a maior parte do tempo trabalhando, mas tamb´em possuem um overhead de
comunica¸c˜ao e sincronismo que ocorre no in´ıcio e no final da execu¸c˜ao do algoritmo. No
exemplo da figura 4.6, uma parte consider´avel do tempo ´e gasta com o overhead. Por´em,
este tempo tende a diminuir com o aumento do problema, como ´e visto implicitamente nas
figuras 4.1 e 4.2.
4.2 Identidade fracional
A abordagem deste m´etodo ´e semelhante a abordagem do algoritmo paralelo da conta-
gem de k-mers, tanto na forma como os dados s˜ao divididos entre os processos quanto na
abordagem de gerenciamento dos mesmos. Todos os testes realizados com o algoritmo pa-
ralelo partiram da execu¸c˜ao do algoritmo com no m´ınimo dois processadores at´e o n´umero
m´aximo de processadores do cluster. A obten¸c˜ao do ganho de desempenho seq
¨
uencial foi
obtida com a execu¸c˜ao do algoritmo seq
¨
uencial. Entretanto, devido `as limita¸c˜oes de me-
m´oria, n˜ao foi poss´ıvel executar algumas entradas tanto com o algoritmo seq
¨
uencial quanto
com o algoritmo paralelo em poucos n´os. Neste caso, o tempo de execu¸c˜ao n˜ao foi medido
e o ganho de desempenho foi calculado em rela¸c˜ao ao tempo de execu¸c˜ao do algoritmo
paralelo com o n´umero m´ınimo de n´os que habilita a execu¸c˜ao.
Devido a semelhan¸ca com a abordagem paralela da contagem de k-mers, o algoritmo
paralelo da identidade fracional apresentou caracter´ısticas semelhantes de escalabilidade
quando executado sobre os mesmos conjuntos de entrada. Os primeiros testes s˜ao mos-
trados na figura 4.7. Utilizou-se aqui as entradas com 500, 1000, 2000 e 4000 seq
¨
uˆencias
com aproximadamente 1000 res´ıduos cada e mediu-se o tempo de execu¸c˜ao do algoritmo
utilizando-se um n´umero crescente de n´os de execu¸c˜ao. Entretanto, para as entradas com
1000, 2000 e 4000 seq
¨
uˆencias n˜ao foi poss´ıvel medir o tempo de execu¸c˜ao do algoritmo
seq
¨
uencial. Tamb´em n˜ao foi poss´ıvel medir, para a entrada de 2000 e 4000 seq
¨
uˆencias, o
tempo de execu¸c˜ao do algoritmo paralelo utilizando-se poucos n´os.
4.2 Identidade fracional 85
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
número de processadores
tempo de execução (s)
Figura 4.7: Gr´afico de tempo de execu¸c˜ao do algoritmo paralelo da identidade fracional
para entradas com seq
¨
uˆencias de aproximadamente 1000 res´ıduos
A inviabilidade da execu¸c˜ao do algoritmo nesses casos se deve `as limita¸c˜oes de mem´oria
do sistema. Conforme aumenta-se o problema, aumenta-se o uso de mem´oria. A mem´oria
dispon´ıvel, por sua vez, ´e expandida com o aumento do n´umero de n´os utilizados. Como
o algoritmo da identidade fracional no MUSCLE ´e executado apenas no segundo est´agio,
utilizando como entrada o resultado do primeiro est´agio, a mem´oria dispon´ıvel deve ser
suficiente para que todos os m´etodos do primeiro est´agio sejam executados, caso contr´ario
o algoritmo da identidade fracional n˜ao ´e executado. Neste teste, houve insuficiˆencia de
mem´oria para as entradas com 1000, 2000 e 4000 seq
¨
uˆencias com o algoritmo seq
¨
uencial.
Para a entrada com 2000 seq
¨
uˆencias, a execu¸c˜ao do algoritmo paralelo em dois n´os tamb´em
n˜ao pˆode ser realizada. Para a entrada com 4000 seq
¨
uˆencias, a execu¸c˜ao em paralelo s´o foi
poss´ıvel a partir de cinco n´os.
A segunda classe de testes realizada utiliza entradas menores, ocupando menos mem´oria
do sistema. Dessa forma, pˆode se executar as entradas tamb´em em 1 ´unico n´o, atrav´es
do algoritmo seq
¨
uencial, possibilitando a medi¸c˜ao do speedup real. As entradas utilizadas
possuem 3000, 4000 e 5000 seq
¨
uˆencias com aproximadamente 50 res´ıduos cada. As figuras
4.8 e 4.9 mostram o tempo de execu¸c˜ao e o speedup real respectivamente.
A figura 4.10 mostra, por sua vez, o ganho de desempenho obtido variando-se o com-
4.2 Identidade fracional 86
3000 seqüências
4000 seqüências
5000 seqüências
número de processadores
tempo de execução (s)
Figura 4.8: Gr´afico de tempo de execu¸c˜ao do algoritmo paralelo da identidade fracional
para entradas com seq
¨
uˆencias de aproximadamente 50 res´ıduos
3000 seqüências
4000 seqüências
5000 seqüências
número de processadores
speedup real
Figura 4.9: Gr´afico de speedup real do algoritmo paralelo da identidade fracional para
entradas com seq
¨
uˆencias de aproximadamente 50 res´ıduos
primento m´edio das seq
¨
uˆencias. Ambas entradas deste teste possuem 4000 seq
¨
uˆencias,
por´em o n´umero de res´ıduos m´edio por seq
¨
uˆencia em cada entrada ´e 50 e 1000. Como a
execu¸c˜ao da entrada com comprimento m´edio de 1000 res´ıduos s´o pˆode ser realizada com
o algoritmo paralelo em cinco n´os, o ganho de desempenho foi calculado a partir do tempo
4.3 Alinhamento progressivo 87
desta execu¸c˜ao. A partir dessa figura vemos que tal algoritmo paralelo apresenta uma boa
escalabilidade.
Comprimento médio: 50
Comprimento médio: 1000
número de processadores
ganho de desempenho
Figura 4.10: Gr´afico de ganho de desempenho do algoritmo paralelo da identidade fracional
para entradas com 4000 seq
¨
uˆencias de aproximadamente 50 e 1000 res´ıduos
Para mostrar o impacto do overhead de comunica¸c˜ao e sincronismo neste algoritmo,
extraiu-se tamb´em o perfil de execu¸c˜ao para o mesmo caso de teste do algoritmo da conta-
gem de k-mers: 500 seq
¨
uˆencias de aproximadamente 1000 res´ıduos. Em ambos algoritmos,
o tempo gasto com overhead e com a execu¸c˜ao s˜ao bem semelhantes. A figura 4.11 mostra
essa informa¸c˜ao para o algoritmo da identidade fracional.
4.3 Alinhamento progressivo
Os testes a seguir mostram o tempo de execu¸c˜ao das abordagens paralelas do alinha-
mento progressivo. Como a etapa do alinhamento progressivo ´e realizada no primeiro e no
segundo est´agio do MUSCLE, seu algoritmo possui algumas diferen¸cas de implementa¸c˜ao.
Essas diferen¸cas n˜ao afetam o desempenho do algoritmo pois a abordagem em ambos os
est´agios ´e a mesma. Como a inten¸c˜ao ´e avaliar o desempenho de cada estrat´egia, os testes
aqui apresentados foram todos realizados no primeiro est´agio.
Dentre essas estrat´egias incluem-se a estrat´egia com gargalo e as quatro solu¸c˜oes im-
4.3 Alinhamento progressivo 88
mestre escravo 1 escravo 2 escravo 3
= 2,3s
Tempo percentual
Figura 4.11: Percentual de tempo gasto com comunica¸c˜ao e sincronismo do algoritmo
paralelo da identidade fracional para a entrada com 500 seq
¨
uˆencias de aproximadamente
1000 res´ıduos
plementadas. Para cada algoritmo, os testes foram feitos com v´arias entradas distintas,
variando-se o n´umero de processadores a partir do n´umero m´ınimo poss´ıvel para a sua
execu¸c˜ao, que satisfaz as restri¸c˜oes de mem´oria, at´e 16 processadores.
Para qualquer solu¸c˜ao adotada, o desempenho do paralelismo ´e sempre dependente
da estrutura da ´arvore filogen´etica, obtida a partir do conjunto de seq
¨
uˆencias de entrada.
Dessa forma, a escolha do arquivo de entrada influencia fortemente o desempenho do
algoritmo. Para mostrar como o mesmo se comporta em v´arios tipos de casos, optou-
se, primeiramente, por realizar testes com o uso de entradas normais, compostas por um
conjunto de seq
¨
uˆencias aleat´orias e por uma ´arvore filogen´etica v´alida, constru´ıda, a partir
das distˆancias entre essas seq
¨
uˆencias, por algum m´etodo v´alido de constru¸c˜ao de ´arvores.
Entretanto, o melhor caso ocorre quando a ´arvore filogen´etica est´a balanceada, o que ´e raro
de acontecer com o uso de entradas normais. Para analisar este caso, implementou-se um
algoritmo modificado do m´etodo de constru¸c˜ao de ´arvore que, independente das seq
¨
uˆencias
utilizadas, sempre produz uma ´arvore balanceada. Este algoritmo ´e chamado atrav´es do
uso da flag balance, na passagem de parˆametros durante a chamada de execu¸c˜ao do
MUSCLE. Por produzir um resultado de alinhamento inv´alido, ele ´e utilizado apenas para
medir o desempenho do algoritmo no melhor caso e n˜ao como uma op¸c˜ao de uso normal
da ferramenta.
4.3 Alinhamento progressivo 89
Al´em do desempenho em casos aleat´orios e no melhor caso, tamb´em ´e poss´ıvel ver nos
testes a escalabilidade do algoritmo, variando-se o n´umero de processadores e o conjunto
de seq
¨
uˆencias utilizadas.
4.3.1 Compara¸c˜ao entre as estrat´egias
O primeiro teste realizado mostra o desempenho da estrat´egia com gargalo. Apesar
de habilitar a execu¸c˜ao de problemas maiores com o paralelismo, o ganho de desempenho
obtido ´e relativamente pequeno quando o algoritmo paralelo ´e executado. A figura 4.12
mostra o tempo de execu¸c˜ao deste algoritmo para quatro entradas distintas. Essas entradas
contˆem 500, 1000, 2000 e 4000 seq
¨
uˆencias de aproximadamente 1000 res´ıduos cada.
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
número de processadores
tempo de execução (s)
Figura 4.12: Gr´afico de tempo de execu¸c˜ao da estrat´egia com gargalo do alinhamento pro-
gressivo
Note que este algoritmo apenas consegue executar o teste com a maior entrada a partir
de nove n´os de execu¸c˜ao. Como ser´a mostrado adiante, este mesmo teste pode ser executado
a partir de cinco n´os de execu¸c˜ao nas demais estrat´egias. Isto ocorre pois tal algoritmo n˜ao
realiza uma boa distribui¸c˜ao dos dados entre os n´os. A figura 4.13 mostra o percentual de
tempo gasto com a comunica¸c˜ao e sincronismo, para o teste com 500 seq
¨
uˆencias. Nesta
figura vemos como o n´o 2 ´e sobrecarregado enquanto os demais ficam ociosos a maior parte
4.3 Alinhamento progressivo 90
do tempo. Este desbalanceamento, al´em de diminuir o ganho de desempenho tamb´em
diminui a capacidade de mem´oria do sistema.
= 110s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.13: Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia do
alinhamento progressivo com gargalo para a entrada com 500 seq
¨
uˆencias
O segundo teste mostra que o paralelismo com a solu¸c˜ao sendmaster tamb´em n˜ao ´e
eficiente. A figura 4.14 mostra os resultados obtidos com a execu¸c˜ao das mesmas entradas
do teste anterior.
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
número de processadores
tempo de execução (s)
Figura 4.14: Gr´afico de tempo de execu¸c˜ao da estrat´egia sendmaster
Neste gr´afico vemos que a estrat´egia sendmaster n˜ao ´e uma boa estrat´egia. O tempo
4.3 Alinhamento progressivo 91
de execu¸c˜ao cresce absurdamente quando o algoritmo ´e executado em poucos n´os e o
overhead com a comunica¸c˜ao sobrep˜oe o ganho de desempenho com a divis˜ao das tarefas.
J´a com o aumento do n´umero de n´os, o ganho de desempenho mant´em-se constante. Neste
caso, o ganho de desempenho com a divis˜ao das tarefas ´e anulado pelo overhead com a
comunica¸c˜ao. A ´unica vantagem nesta estrat´egia ´e o melhor balanceamento de carga, como
mostrado na figura 4.15. Esta caracter´ıstica possibilita a execu¸c˜ao de problemas grandes
em clusters de tamanho menor. Por exemplo, a execu¸c˜ao da entrada de 4000 seq
¨
uˆencias em
um cluster com mesma capacidade de mem´oria, por´em com apenas cinco n´os de execu¸c˜ao,
ao inv´es dos nove exigidos na estrat´egia com gargalo.
= 235s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.15: Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
sendmaster para a entrada com 500 seq
¨
uˆencias
As estrat´egias waitall e waitany foram testadas em seguida. Apesar delas n˜ao elimina-
rem totalmente o gargalo com a latˆencia, elas apresentam resultados melhores que as duas
primeiras estrat´egias. Em testes realizados com os mesmos conjuntos de entrada dos testes
anteriores, ambas as estrat´egias apresentaram um melhor desempenho, com destaque para
a estrat´egia waitany. As figuras 4.16 (waitall) e 4.17 (waitany) mostram os tempos de
execu¸c˜ao dessas estrat´egias para todas as entradas.
Como pode ser visto, o ganho de desempenho obtido com a diminui¸c˜ao do gargalo ´e
consider´avel. O overhead de comunica¸c˜ao ´e praticamente o mesmo da estrat´egia existente,
por´em com uma redu¸c˜ao no gargalo e um melhor balanceamento de carga. As figuras
4.18 e 4.19 mostram o percentual de tempo gasto com overhead de comunica¸c˜ao e sincro-
4.3 Alinhamento progressivo 92
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
número de processadores
tempo de execução (s)
Figura 4.16: Gr´afico de tempo de execu¸c˜ao da estrat´egia waitall
número de processadores
tempo de execução (s)
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
Figura 4.17: Gr´afico de tempo de execu¸c˜ao da estrat´egia waitany
nismo para o teste com 500 seq
¨
uˆencias. Atrav´es desses gr´aficos tamb´em ´e poss´ıvel ver o
balanceamento de carga destes algoritmos.
A ´ultima solu¸c˜ao implementada foi a estrat´egia com threads. Essa estrat´egia, apesar
de estar restrita `a execu¸c˜ao apenas com algumas implementa¸c˜oes do MPI, ´e a melhor das
quatro estrat´egias. A figura 4.20 mostra os tempos de execu¸c˜ao com as entradas dos testes
4.3 Alinhamento progressivo 93
= 98s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.18: Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
waitall para a entrada com 500 seq
¨
uˆencias
= 89s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.19: Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
waitany para a entrada com 500 seq
¨
uˆencias
anteriores. Aqui o gargalo da latˆencia ´e totalmente eliminado e a comunica¸c˜ao entre os
processos ´e m´ınima.
Para esta estrat´egia tamb´em foi feita uma extra¸c˜ao do perfil de execu¸c˜ao. A figura 4.21
mostra o percentual de tempo gasto com o overhead de comunica¸c˜ao e sincronismo apenas
para o processo principal. O processo principal ´e aquele que realiza o processamento de
fato. O thread, por ficar a maior parte do tempo ocioso, esperando o recebimento de uma
solicita¸c˜ao de envio de dados, n˜ao ´e mostrado aqui. A etapa em que o thread realmente
4.3 Alinhamento progressivo 94
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
número de processadores
tempo de execução (s)
Figura 4.20: Gr´afico de tempo de execu¸c˜ao da estrat´egia com threads
trabalha ´e quando este envia os dados aos escravos dependentes. Para isto, o tempo gasto
com processamento ´e m´ınimo, pois este ´e necess´ario apenas para o encapsulamento dos
dados para envio.
= 92s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.21: Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia com
threads para a entrada com 500 seq
¨
uˆencias
Para compara¸c˜ao, ´e mostrado na figura 4.22 o tempo de execu¸c˜ao de todas as estrat´egias
para a entrada com 500 seq
¨
uˆencias. A figura 4.23, por sua vez, coloca lado a lado os speedups
reais de todas as estrat´egias.
4.3 Alinhamento progressivo 95
Threads
Waitany
Waitall
Sendmaster
Com gargalo
número de processadores
tempo de execução (s)
Figura 4.22: Compara¸c˜ao do tempo de execu¸c˜ao das estrat´egias paralelas do alinhamento
progressivo para a entrada com 500 seq
¨
uˆencias
Threads
Waitany
Waitall
Sendmaster
Com gargalo
número de processadores
speedup real
Figura 4.23: Compara¸c˜ao dos speedups reais das estrat´egias paralelas do alinhamento pro-
gressivo para a entrada com 500 seq
¨
uˆencias
Esses algoritmos melhoram o ganho de desempenho conforme aumenta-se o n´umero de
seq
¨
uˆencias. Com o aumento do n´umero de seq
¨
uˆencias, por outro lado, aumenta-se o uso de
mem´oria. Este aumento de mem´oria faz com que o algoritmo torne-se execut´avel apenas
em m´ultiplos n´os. Para visualizarmos a escalabilidade atrav´es de uma entrada maior do
4.3 Alinhamento progressivo 96
que a entrada da figura anterior, calculou-se o ganho de desempenho em rela¸c˜ao ao tempo
de execu¸c˜ao do algoritmo paralelo com o menor n´umero de n´os que habilita a execu¸c˜ao. A
figura 4.24 mostra o ganho de desempenho para uma entrada com 2000 seq
¨
uˆencias, cujo
sistema m´ınimo ´e de trˆes n´os.
Threads
Waitany
Waitall
Sendmaster
Com gargalo
número de processadores
ganho de desempenho
Figura 4.24: Compara¸c˜ao do ganho de desempenho das estrat´egias paralelas do alinhamento
progressivo para a entrada com 2000 seq
¨
uˆencias
Para mostrar tamb´em como o ganho de desempenho varia com a entrada utilizada,
selecionamos a melhor estrat´egia (com threads) e calculamos o ganho de desempenho para
as quatro entradas. Novamente, o ganho de desempenho ´e obtido em rela¸c˜ao ao tempo de
execu¸c˜ao do algoritmo em um sistema maior que um n´o. Como o maior sistema m´ınimo
para este conjunto de entrada ´e de cinco n´os - execu¸c˜ao da entrada com 4000 seq
¨
uˆencias -, o
ganho de desempenho, variando-se a quantidade de n´os e a entrada utilizada, ´e calculado em
rela¸c˜ao ao tempo de execu¸c˜ao em cinco n´os. O gr´afico da figura 4.25 mostra os resultados
obtidos.
Para mostrar que o algoritmo apresenta um certo grau de escalabilidade, o ganho de
desempenho deve aumentar com o aumento da entrada utilizada, o que ´e visto na figura
anterior para as entradas com 2000 e 4000 seq
¨
uˆencias. Entretanto, o ganho de desempenho
n˜ao est´a unicamente vinculado com o tamanho da entrada utilizada. A dependˆencia entre as
tarefas tamb´em afeta o paralelismo, e, dependendo do problema, a eficiˆencia do paralelismo
4.3 Alinhamento progressivo 97
4000 seqüências
2000 seqüências
1000 seqüências
500 seqüências
árvore filogenética com forte dependência
número de processadores
ganho de desempenho
Figura 4.25: Compara¸c˜ao do ganho de desempenho da estrat´egia com threads para as
entradas com 500, 1000, 2000 e 4000 seq
¨
uˆencias
pode variar, aumentando ou diminuindo o ganho de desempenho do algoritmo.
´
E o que
acontece com as entradas com 500 e 1000 seq
¨
uˆencias. Apesar da entrada aumentar, o ganho
de desempenho diminui. Dessa forma, a escalabilidade com a entrada de 1000 seq
¨
uˆencias,
que deveria ser superior, ´e inferior.
Essa mesma an´alise pode ser feita atrav´es de uma outra perspectiva, utilizando-se o
gr´afico de tempo de execu¸c˜ao da mesma estrat´egia (figura 4.20). Com ele ´e poss´ıvel ver que
a entrada com 500 seq
¨
uˆencias apresenta um tempo de execu¸c˜ao mais que duas vezes menor
do que o tempo de execu¸c˜ao com a entrada com 1000 seq
¨
uˆencias. Por este mesmo gr´afico
tamb´em vemos que a entrada com 2000 seq
¨
uˆencias apresenta um tempo de execu¸c˜ao bem
pr´oximo do tempo de execu¸c˜ao da entrada com 1000 seq
¨
uˆencias. Neste caso, dobrou-se
a quantidade de dados de entrada, por´em manteve-se pr´oximo o tempo de execu¸c˜ao do
algoritmo. Como ser´a visto adiante, este comportamento ´e justificado pelo fato do n´ıvel de
paralelismo da aplica¸c˜ao, em geral, ser aproximadamente o dobro com a entrada de 2000
seq
¨
uˆencias. Entende-se pela aplica¸c˜ao uma fun¸c˜ao que considera o algoritmo, a entrada
utilizada (instˆancia do problema) e o n´umero de processadores.
4.3 Alinhamento progressivo 98
4.3.2 O n´ıvel de paralelismo
O n´ıvel de paralelismo depende do algoritmo, da entrada utilizada e da quantidade
de processadores. Para o mesmo algoritmo e mesmo n´umero de processadores, o n´ıvel
de paralelismo pode mudar de acordo com a instˆancia do problema. O motivo ´e que a
defini¸c˜ao de v´arios est´agios de um algoritmo paralelo ´e, em geral, feita dinamicamente.
Por exemplo, a maioria dos algoritmos paralelos de alinhamento progressivo definem o
particionamento em n´ıvel de n´o de ´arvore e, portanto, este est´agio ´e est´atico. Entretanto,
utilizando-se este particionamento, a comunica¸c˜ao e o escalonamento podem variar, uma
vez que a dependˆencia das tarefas primitivas ´e definida por uma estrutura intr´ınseca ao
problema. No caso do alinhamento progressivo com particionamento em n´ıvel de n´o de
´arvore, quem define a dependˆencia das tarefas ´e a ´arvore filogen´etica, que ´e dependente
das seq
¨
uˆencias de entrada (ver se¸c˜ao 2.6.3). Essa dependˆencia pode variar desde o caso
em que todos os n´os da ´arvore possuem apenas um ´unico filho (exceto os n´os folhas) at´e o
caso em que a ´arvore se encontra balanceada.
Uma maior quantidade de processadores, por sua vez, possibilita uma menor aglomera-
¸c˜ao das tarefas que, em um certo instante, est˜ao prontas para o processamento. Entretanto,
dependendo da granularidade atingida, o aumento de processadores pode n˜ao proporcionar
melhoras de desempenho. Em piores casos, este aumento pode degradar o desempenho. A
defini¸c˜ao de uma boa estrat´egia de aglomera¸c˜ao sempre ´e feita dinamicamente e associada
com boas estrat´egias de comunica¸c˜ao e escalonamento.
Portanto, dos quatro est´agios definido por Foster [8], apenas o particionamento ´e em
geral definido como est´atico na maioria dos algoritmos paralelos. Todos os outros est´agios
s˜ao definidos dinamicamente e, portanto, variam de acordo com a instˆancia do problema e
com o n´umero de processadores.
O n´ıvel de paralelismo ent˜ao foi definido como uma medida que nos mostra qu˜ao perto
de um paralelismo ´otimo um algoritmo paralelo, que calcule estaticamente o particiona-
mento, pode chegar, utilizando-se uma instˆancia espec´ıfica do problema e um n´umero espe-
c´ıfico de processadores. Esta medida ´e obtida considerando um ambiente paralelo perfeito,
em que n˜ao existam custos com a comunica¸c˜ao e a carga esteja sempre balanceada. Ou
seja, um algoritmo com estrat´egias ´otimas de comunica¸c˜ao, aglomera¸c˜ao e escalonamento.
4.3 Alinhamento progressivo 99
Neste caso o desempenho ´e unicamente afetado por caracter´ısticas intr´ınsecas ao problema
e pela varia¸c˜ao no n´umero de processadores.
A tabela 4.1 mostra como o aumento do n´umero de processadores aumenta o n´ıvel de
paralelismo para o problema do alinhamento progressivo do MUSCLE com particionamento
em n´ıvel de n´o de ´arvore. Este n´umero, por´em, tende a se estabilizar em um certo ponto.
´
E neste ponto que a entrada utilizada passa a ser o gargalo do paralelismo, impossibili-
tando que o aumento do n´umero de processadores traga algum benef´ıcio no desempenho.
Como explicado, este gargalo se deve `a limita¸c˜ao na quantidade de tarefas que podem ser
escalonadas simultaneamente, limita¸c˜ao esta inerente ao m´odulo do problema que define
as dependˆencias entre as tarefas. No alinhamento progressivo do MUSCLE, este m´odulo ´e
o de constru¸c˜ao da ´arvore filogen´etica.
N´umero N´ıvel de paralelismo
de escravos 500 seq 1000 seq 2000 seq 4000 seq
1 1 1 x x
2 1.92 1.75 1.99 x
3 2.71 2.35 2.95 x
4 3.28 2.78 3.87 3.79
5 3.75 3.15 4.66 4.61
6 4.09 3.42 5.33 5.41
7 4.34 3.61 6.04 6.12
8 4.5 3.78 6.55 6.8
9 4.58 3.89 7.04 7.46
10 4.66 4 7.43 8.08
11 4.75 4.08 7.84 8.62
12 4.8 4.13 8.13 9.15
13 4.84 4.18 8.33 9.64
14 4.89 4.23 8.58 10.05
15 4.89 4.27 8.77 10.47
Tabela 4.1: N´ıvel de paralelismo com o uso da ´arvore normal produzida pelo MUSCLE para
as entradas com 500, 1000, 2000 e 4000 seq
¨
uˆencias
4.3.3 A ´arvore filogen´etica e a escalabilidade do algoritmo
A ´arvore de dependˆencia de tarefas no alinhamento progressivo ´e baseada na ´arvore
filogen´etica previamente constru´ıda. Dependendo de sua estrutura, uma maior quantidade
4.3 Alinhamento progressivo 100
de tarefas pode ou n˜ao ser executada em paralelo. Uma ´arvore que apresenta a melhor
estrutura para o paralelismo ´e a ´arvore balanceada. Esta ´arvore representa o melhor caso
pois ela apresenta uma maior quantidade de n´os independentes uns dos outros em rela¸c˜ao `as
demais ´arvores. Entretanto, uma ´arvore filogen´etica tem um significado biol´ogico, e ´e cons-
tru´ıda a partir de um m´etodo espec´ıfico. Quanto mais pr´oxima de uma ´arvore balanceada
estiver a arvore gerada, maior ser´a o n´ıvel de paralelismo no alinhamento progressivo.
Para mostrarmos como o desempenho de um algoritmo varia com a estrutura da ´arvore
gerada, escolhemos primeiro uma instˆancia do problema. Sobre esta instˆancia, comparamos
o n´ıvel de paralelismo obtido com o uso de uma ´arvore balanceada, obtida a partir da vers˜ao
modificada do algoritmo, e com o uso de uma ´arvore normal. Neste caso, a ´arvore normal
´e a arvore gerada pelo m´etodo UPGMA do MUSCLE. Realizamos testes com estrat´egia
com threads e uma entrada de 1000 seq
¨
uˆencias, variando-se o numero de processadores. O
tempo de execu¸c˜ao de ambas as ´arvores ´e mostrado na figura 4.26. Calculamos tamb´em o
speedup real, mostrado na figura 4.27.
Árvore normal
Árvore balanceada
número de processadores
tempo de execução (s)
Figura 4.26: Compara¸c˜ao do tempo de execu¸c˜ao da estrat´egia com threads com a ´arvore
balanceada e a ´arvore normal para a entrada com 1000 seq
¨
uˆencias
Atrav´es da figura 4.27 pode-se ver como o algoritmo torna-se mais escal´avel com o uso
da ´arvore balanceada. Essa escalabilidade ´e maior devido ao maior n´umero de tarefas exe-
cutadas simultaneamente. A tabela 4.2 mostra uma compara¸c˜ao dos n´ıveis de paralelismo
4.3 Alinhamento progressivo 101
Árvore normal
Árvore balanceada
número de processadores
speedup real
Figura 4.27: Compara¸c˜ao do speedup real da estrat´egia com threads com a ´arvore balan-
ceada e a ´arvore normal para a entradas com 1000 seq
¨
uˆencias
obtidos com o uso da ´arvore normal e com o uso da ´arvore balanceada.
N´umero N´ıvel de paralelismo
de escravos Balanceada N˜ao balanceada
1 1 1
2 2 1.75
3 2.99 2.35
4 3.98 2.78
5 4.95 3.15
6 5.91 3.42
7 6.89 3.61
8 7.87 3.78
9 8.76 3.89
10 9.7 4
11 10.63 4.08
12 11.62 4.13
13 12.49 4.18
14 13.32 4.23
15 14.27 4.27
Tabela 4.2: Compara¸c˜ao do n´ıvel de paralelismo com o uso da ´arvore normal produzida
pelo MUSCLE e da ´arvore balanceada para a entrada com 1000 seq
¨
uˆencias
Al´em do aumento do n´ıvel de paralelismo, realizar o alinhamento em uma ´arvore ba-
4.4 Alinhamento par-a-par 102
lanceada ´e uma opera¸c˜ao menos custosa. Isto ´e notado observando o gr´afico de tempo de
execu¸c˜ao do alinhamento com apenas dois processadores (figura 4.26). Para dois processa-
dores, a quantidade de tarefas independentes n˜ao influencia no tempo de execu¸c˜ao, pois as
tarefas s˜ao executadas no ´unico processador escravo dispon´ıvel. Al´em disso, a quantidade
de tarefas de alinhamento ´e a mesma independentemente da ´arvore gerada. Realizar o
alinhamento em uma ´arvore balanceada ´e uma opera¸c˜ao menos custosa devido a existˆencia
de um maior n´umero de tarefas de alinhamento envolvendo perfis menores. Esses perfis
menores cont´em uma menor quantidade de dados a serem processados.
Consequentemente, o uso de mem´oria ´e reduzido, possibilitando sua execu¸c˜ao em clus-
ters menores. Na figura 4.26 vemos que a entrada com 1000 seq
¨
uˆencias s´o pode ser exe-
cutada a partir de dois n´os com uma ´arvore normal. J´a o sistema m´ınimo para executar
a mesma entrada, por´em com uma ´arvore balanceada, ´e de apenas um n´o, habilitando a
execu¸c˜ao do algoritmo seq
¨
uencial.
Portanto, a topologia da ´arvore filogen´etica afeta o desempenho do algoritmo em di-
ferentes maneiras. Quanto mais perto a ´arvore est´a de uma condi¸c˜ao balanceada, maior
´e o n´ıvel de paralelismo, menor ´e o esfor¸co computacional e menores s˜ao os requisitos de
mem´oria.
4.4 Alinhamento par-a-par
Os testes a seguir mostram o tempo de execu¸c˜ao das abordagens paralelas do alinha-
mento par-a-par. Como a etapa do alinhamento par-a-par ´e realizada nos dois est´agios
progressivos e no est´agio iterativo do MUSCLE, seu algoritmo possui algumas diferen¸cas
de implementa¸c˜ao. Essas diferen¸cas n˜ao afetam o desempenho do algoritmo pois a abor-
dagem em todos os est´agios ´e a mesma. Como a inten¸c˜ao ´e avaliar o desempenho das
estrat´egias paralelas constru´ıdas sobre a abordagem de alinhamento par-a-par da ferra-
menta MUSCLE, os testes aqui apresentados foram todos realizados no primeiro est´agio
progressivo. O comportamento da execu¸c˜ao paralela no segundo est´agio progressivo e no
est´agio iterativo ´e o mesmo e, portanto, n˜ao ser´a mostrado.
Ao todo trˆes estrat´egias foram definidas. Para cada algoritmo, os testes foram realiza-
4.4 Alinhamento par-a-par 103
dos com v´arias entradas distintas, variando-se o n´umero de processadores.
4.4.1 Compara¸c˜ao entre as estrat´egias
O desenvolvimento das trˆes estrat´egias implementadas foi baseado no algoritmo block-
based wavefront, proposto em [44]. Este algoritmo divide a computa¸c˜ao da matriz dinˆamica,
por´em n˜ao apresenta uma t´ecnica para coletar os resultados da execu¸c˜ao e gerar o resul-
tado final, que ´e o caminho do alinhamento. Neste projeto, trˆes poss´ıveis t´ecnicas foram
implementadas.
A primeira delas faz a coleta de todos os dados de uma s´o vez no final da execu-
¸c˜ao do algoritmo block-based wavefront. Esses dados s˜ao todos os elementos da matriz de
programa¸c˜ao dinˆamica. A figura 4.28 mostra o perfil de execu¸c˜ao desta t´ecnica para o ali-
nhamento de duas seq
¨
uˆencias de aproximadamente 1000 res´ıduos em trˆes n´os de execu¸c˜ao.
Essa extra¸c˜ao de perfil foi feita atrav´es da ferramenta Jumpshot [35]. Atrav´es dessa figura
´e poss´ıvel ver como ´e grande o overhead de comunica¸c˜ao e sincronismo. Como v´arios es-
cravos tentam quase que ao mesmo tempo enviar dados ao processo mestre, estes escravos
mant´em-se esperando, em uma fun¸c˜ao de envio de dados, at´e que o processo mestre atenda
todas as requisi¸c˜oes de envio. A espera ´e relativamente longa pois a quantidade de dados
enviados ´e O(NxM), onde N e M s˜ao os tamanhos das seq
¨
uˆencias.
A figura 4.29 mostra o percentual de tempo gasto com a comunica¸c˜ao e sincronismo
para uma entrada com cinco seq
¨
uˆencias de aproximadamente 3000 res´ıduos cada. Utilizou-
se quatro n´os de execu¸c˜ao neste teste. Note que apenas uma pequena parte do tempo ´e
destinado ao processamento. A maior parte corresponde ao overhead com o sincronismo e
a comunica¸c˜ao.
Visando minimizar o tempo gasto com este sincronismo, implementou-se uma segunda
estrat´egia em que os dados dos processos escravos s˜ao enviados em partes para o processo
mestre. Esta t´ecnica utiliza melhor a rede, por´em aumenta-se o custo com a comunica-
¸c˜ao. A figura 4.30 mostra o perfil de execu¸c˜ao desta t´ecnica para o alinhamento de duas
seq
¨
uˆencias de aproximadamente 1000 res´ıduos em apenas trˆes n´os de execu¸c˜ao. Em rela¸c˜ao
a primeira t´ecnica, o tempo total da execu¸c˜ao desta entrada foi ligeiramente menor.
4.4 Alinhamento par-a-par 104
Tempo
Escravo 1 Escravo 2 Mestre
Send Síncrono
utilizado para
sincronização
com o mestre
Send Síncrono
utilizado para
sincronização
com o mestre
Receive Síncrono
Send Síncrono
Send Assíncrono
Figura 4.28: Perfil da execu¸c˜ao em trˆes n´os da estrat´egia que envia os dados ap´os todos
serem computados para uma entrada de duas seq
¨
uˆencias de aproximadamente 1000 res´ıduos
= 5,3s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.29: Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia
que envia dados ap´os todos serem computados para uma entrada de cinco seq
¨
uˆencias de
aproximadamente 3000 res´ıduos
A figura 4.31, por sua vez, mostra o percentual de tempo gasto com a comunica¸c˜ao e
sincronismo. Utilizou-se neste teste quatro n´os de execu¸c˜ao e a entrada de cinco seq
¨
uˆencias
de aproximadamente 3000 res´ıduos. As caracter´ısticas apresentadas s˜ao semelhantes `as da
t´ecnica anterior (figura 4.29), n˜ao apresentando, portanto, uma melhora significante no
4.4 Alinhamento par-a-par 105
Tempo
Escravo 1 Escravo 2 Mestre
Send Síncrono
utilizado para
sincronização
com o mestre
Send Síncrono
utilizado para
sincronização
com o mestre
Receive Síncrono
Send Síncrono
Send Assíncrono
Figura 4.30: Perfil da execu¸c˜ao em trˆes n´os da estrat´egia que envia dados em partes para
uma entrada de duas seq
¨
uˆencias de aproximadamente 1000 res´ıduos
tempo de execu¸c˜ao total do alinhamento.
= 4,6s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.31: Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia que
envia dados em peda¸cos para uma entrada de cinco seq
¨
uˆencias de aproximadamente 3000
res´ıduos
A terceira e ´ultima t´ecnica, ao inv´es de apresentar uma forma alternativa de reunir os
dados da matriz, que est˜ao distribu´ıdos, calcula o caminho do alinhamento nessa matriz
sobre os dados distribu´ıdos, realizando uma parte do processamento em cada processo,
4.4 Alinhamento par-a-par 106
de acordo com a disponibilidade dos dados. Este caminho, ent˜ao, ´e enviado ao processo
mestre que o utiliza para o c´alculo do novo alinhamento (est´agio iterativo) ou perfil do
alinhamento (est´agio progressivo). A figura 4.32 mostra o perfil de execu¸c˜ao desta t´ecnica
para o alinhamento de duas seq
¨
uˆencias de 1000 res´ıduos em trˆes n´os de execu¸c˜ao. Al´em
de eliminar os custos com sincronismo e comunica¸c˜ao, o c´alculo distribu´ıdo do caminho de
alinhamento mostrou-se extremamente r´apido.
Tempo
Escravo 1 Escravo 2 Mestre
Send Síncrono
utilizado para
sincronização
com o mestre
Send Síncrono
utilizado para
sincronização
com o mestre
Send Síncrono
utilizado para
sincronização
com o escravo 1
Receive Síncrono
Send Síncrono
Figura 4.32: Perfil da execu¸c˜ao em trˆes n´os da estrat´egia que paraleliza o m´etodo de constru-
¸c˜ao do caminho de alinhamento para uma entrada de duas seq
¨
uˆencias de aproximadamente
1000 res´ıduos
A figura 4.33 mostra o percentual de tempo gasto com a comunica¸c˜ao e o sincronismo,
alinhando-se cinco seq
¨
uˆencias de aproximadamente 3000 res´ıduos em quatro n´os de execu-
¸c˜ao. Como pode ser visto, aqui a maior parte do tempo ´e gasto com a execu¸c˜ao e n˜ao com
a espera por sincronismo/comunica¸c˜ao.
Em seguida, foram feitos testes com o intuito de comparar o tempo de execu¸c˜ao dos trˆes
algoritmos. Para isso, utilizou-se duas entradas de 100 seq
¨
uˆencias: uma de comprimento
m´edio igual a 1000 e outra de comprimento m´edio igual a 5000. As figuras 4.34 e 4.35
mostram os resultados obtidos.
Percebe-se que a execu¸c˜ao em paralelo das duas primeiras estrat´egias n˜ao ´e vantajosa
4.4 Alinhamento par-a-par 107
= 1,8s
mestre escravo 1 escravo 2 escravo 3
Tempo percentual
Figura 4.33: Percentual de tempo gasto com comunica¸c˜ao e sincronismo da estrat´egia que
paraleliza o m´etodo de constru¸c˜ao do caminho de alinhamento para uma entrada de cinco
seq
¨
uˆencias de aproximadamente 3000 res´ıduos
Envia tudo no final
Envia pedaços
Paralelização completa
número de processadores
tempo de execução (s)
Figura 4.34: Compara¸c˜ao do tempo de execu¸c˜ao das trˆes estrat´egias paralelas do alinha-
mento par-a-par para entradas com sequencias de aproximadamente 1000 res´ıduos
com seq
¨
uˆencias de poucos res´ıduos. O overhead gerado por elas sobrep˜oe o ganho com
a divis˜ao do processamento e este comportamento piora conforme aumenta-se o n´umero
de n´os. J´a para a terceira estrat´egia, o overhead ´e pequeno e, apesar do paralelismo ser
melhor com seq
¨
uˆencias de maior tamanho, utilizar o algoritmo paralelo para seq
¨
uˆencias
pequenas tamb´em pode trazer uma melhora significante. Entretanto, em qualquer um dos
4.4 Alinhamento par-a-par 108
Envia tudo no final
Envia pedaços
Paralelização completa
número de processadores
tempo de execução (s)
Figura 4.35: Compara¸c˜ao do tempo de execu¸c˜ao das trˆes estrat´egias paralelas do alinha-
mento par-a-par para entradas com seq
¨
uˆencias de aproximadamente 5000 res´ıduos
casos, o tempo de execu¸c˜ao sempre ´e menor com o uso da terceira estrat´egia.
Por fim, realizou-se um ´ultimo teste para mostrar o impacto do paralelismo variando-se
o tamanho das seq
¨
uˆencias. Este teste utilizou a melhor estrat´egia e entradas com o mesmo
n´umero de seq
¨
uˆencias. O comprimento m´edio das seq
¨
uˆencias em cada entrada varia de
1000 `a 5000. A figura 4.36 mostra o speedup real obtido com v´arios n´os de execu¸c˜ao.
Como mostra a figura este algoritmo apresenta sinais de escalabilidade. Com o au-
mento do tamanho do problema, aumenta-se o ganho de desempenho para uma mesma
configura¸c˜ao de sistema.
4.4 Alinhamento par-a-par 109
Comprimento médio: 1000
Comprimento médio: 2000
Comprimento médio: 3000
Comprimento médio: 4000
Comprimento médio: 5000
número de processadores
speedup real
Figura 4.36: Compara¸c˜ao do speedup real da estrat´egia que paraleliza o m´etodo de constru-
¸c˜ao do caminho de alinhamento para entradas com seq
¨
uˆencias de aproximadamente 1000,
2000, 3000, 4000 e 5000 res´ıduos
110
5 Conclus˜oes
O uso da computa¸c˜ao paralela em ferramentas de alinhamento m´ultiplo de seq
¨
uˆencias
apresenta uma demanda crescente, visto o n´umero cada vez maior de seq
¨
uˆencias utilizadas
para compara¸c˜ao. Muitos trabalhos prop˜oem o paralelismo de t´ecnicas isoladas, de uso
impratic´avel pela maioria dos bi´ologos. Poucas s˜ao as ferramentas completas paralelizadas e
que consideram aspectos fundamentais da computa¸c˜ao paralela. Encontrou-se na literatura
abordagens que, segundo a metodologia de Foster [8], n˜ao consideram aspectos como o
balanceamento da carga e a latˆencia. A paraleliza¸c˜ao proposta contorna este problema
possibilitando uma f´acil execu¸c˜ao de problemas reais em sistemas reais com eficiˆencia e
escalabilidade, atrav´es da paraleliza¸c˜ao de uma ferramenta de alinhamento m´ultiplo muito
bem aceita, o MUSCLE.
Identificamos, primeiramente, v´arias formas de paralelizarmos os est´agios de execu¸c˜ao
do MUSCLE. Em seguida, definimos poss´ıveis estrat´egias, baseadas ou n˜ao em abordagens
existentes. Nas estrat´egias em que identificamos gargalos de execu¸c˜ao, trabalhou-se sobre
uma otimiza¸c˜ao em busca da diminui¸c˜ao ou elimina¸c˜ao completa desses gargalos. Com
isso, novas estrat´egias foram criadas e comparadas com o que j´a foi proposto. A melhor
estrat´egia foi incorporada como padr˜ao na vers˜ao paralela da ferramenta MUSCLE. Ela,
entretanto, n˜ao est´a restrita ao c´odigo do MUSCLE, podendo ser adaptada em ferramentas
que abordam, de uma forma similar, um mesmo sub-problema de alinhamento.
Ao todo, dez estrat´egias paralelas foram desenvolvidas: duas na etapa de constru¸c˜ao da
matriz de distˆancia, cinco na etapa de alinhamento progressivo e trˆes na etapa de alinha-
mento par-a-par. A estrat´egia do alinhamento par-a-par, em particular, pode ser utilizada
em algoritmos progressivos. O alinhamento par-a-par ´e um subproblema do alinhamento
progressivo, o que possibilita a execu¸c˜ao do problema maior em uma menor granularidade.
5.1 Trabalhos futuros 111
Todas as adapta¸c˜oes foram feitas no c´odigo do MUSCLE. A escolha das estrat´egias
´e feita atrav´es de chamadas de execu¸c˜ao, utilizando a mesma interface com o usu´ario
da ferramenta MUSCLE original. Os testes apresentam o tempo de execu¸c˜ao e ganho
de desempenho com cada estrat´egia para v´arios n´os de execu¸c˜ao. Tamb´em ´e feita uma
an´alise dos tipos de entrada utilizada, mostrando como a ´arvore de dependˆencia de tarefas
primitivas afeta o desempenho do algoritmo.
Os resultados s˜ao muito satisfat´orios. Ao menos uma estrat´egia definida e que pode ser
incorporada em uma etapa espec´ıfica do MUSCLE apresenta melhores resultados no tempo
de execu¸c˜ao e no uso de mem´oria em rela¸c˜ao a estrat´egias j´a existentes. O algoritmo do
MUSCLE paralelo completo, entretanto, n˜ao foi totalmente mensurado e comparado com
seu algoritmo seq
¨
uencial, uma vez que esta an´alise ´e muito restrita a problemas pequenos,
devido `as limita¸c˜oes de mem´oria do sistema seq
¨
uencial. Adicionalmente, v´arios s˜ao os
caminhos de execu¸c˜ao, definidos pelo usu´ario na chamada de execu¸c˜ao. Pelo mesmo motivo,
e pela falta de um sistema de mem´oria compartilhada, n˜ao foi feita uma compara¸c˜ao com
o MUSCLE-SMP. J´a com o CLUSLTAW-MPI, uma compara¸c˜ao n˜ao faz muito sentido,
uma vez que o resultado obtido ´e muito diferente e o CLUSTALW-MPI n˜ao apresenta um
est´agio de refinamento. Fez-se uma apresenta¸c˜ao de todas as paraleliza¸c˜oes propostas por
essas ferramentas, e que s˜ao incorporadas em algumas etapas do algoritmo, e comparou-se
a abordagem que eles adotam com a abordagem proposta neste trabalho. Como j´a dito,
melhores resultados foram obtidos com as paraleliza¸c˜oes definidas neste trabalho.
5.1 Trabalhos futuros
Identificou-se alguns poss´ıveis caminhos para a continuidade deste trabalho. O primeiro
consiste na incorpora¸c˜ao de um mecanismo autom´atico de defini¸c˜ao de tamanho dos blocos
(gr˜aos) da matriz de programa¸c˜ao dinˆamica para ser utilizado no algoritmo do alinhamento
par-a-par baseado na estrat´egia block-based wavefront. Como o tamanho m´ınimo ideal
de um bloco depende de fatores como velocidade de processamento e comunica¸c˜ao de
um sistema, a obten¸c˜ao de medidas de desempenho cr´ıticas atrav´es de testes r´apidos no
in´ıcio da execu¸c˜ao do algoritmo pode conduzir a uma melhor defini¸c˜ao do tamanho da
granularidade.
5.1 Trabalhos futuros 112
Um outro caminho ´e resolver o problema do alinhamento m´ultiplo progressivo atrav´es
de uma abordagem mista, utilizando a melhor estrat´egia de alinhamento progressivo pro-
posta (se¸c˜ao 3.3.7) e a melhor estrat´egia do alinhamento par-a-par proposta (se¸c˜ao 3.4.1).
Essa abordagem consideraria no in´ıcio de sua execu¸c˜ao uma granularidade maior. Cada
n´o da ´arvore seria uma tarefa primitiva. Utiliza-se uma granularidade maior uma vez que,
no in´ıcio, mais tarefas podem ser executadas simultaneamente. Identificaria-se, ent˜ao, o
momento, na ´arvore de tarefas, em que tal granularidade habilita a ocorrˆencia de ociosi-
dade, levando `a um desbalanceamento de carga. Essa ociosidade ocorre uma vez que a
dependˆencia das tarefas ´e maior quando elas est˜ao mais pr´oximas da tarefa raiz. A partir
deste ponto, utilizaria-se uma granularidade menor, em n´ıvel de bloco da matriz.
Ambos os caminhos possuem uma s´erie de aplica¸c˜oes, n˜ao restritas apenas ao c´odigo
do MUSCLE. O primeiro caminho visa melhorar o paralelismo de t´ecnicas de alinhamento
par-a-par, enquanto que o segundo visa uma melhora no paralelismo do alinhamento pro-
gressivo. Como o alinhamento par-a-par ´e um subproblema do alinhamento progressivo
que est´a sendo proposto, um terceiro caminho pode ser a unifica¸c˜ao de ambos os caminhos.
113
Referˆencias Bibliogr´aficas
1 EDGAR, R. C. Muscle: multiple sequence alignment with high accuracy and high
throughput. Nucleic Acids Res, bob@drive5.com, v. 32, n. 5, p. 1792–1797, 2004. ISSN
1362-4962. Dispon´ıvel em: <http://view.ncbi.nlm.nih.gov/pubmed/15034147>.
2 EDGAR, R. C.; BATZOGLOU, S. Multiple sequence alignment. Current
Opinion in Structural Biology, v. 16, n. 3, p. 368–373, June 2006. Dispon´ıvel em:
<http://dx.doi.org/10.1016/j.sbi.2006.04.004>.
3 DENG, X. et al. Parallel implementation and performance characterization of muscle.
Parallel and Distributed Processing Symposium, International, IEEE Computer Society,
Los Alamitos, CA, USA, v. 0, p. 359, 2006.
4 THOMPSON, J. D.; HIGGINS, D. G.; GIBSON, T. J. Clustal w: improving the
sensitivity of progressive multiple sequence alignment through sequence weighting,
position-specific gap penalties and weight matrix choice. Nucleic Acids Res, European
Molecular Biology Laboratory, Heidelberg, Germany., v. 22, n. 22, p. 4673–4680, November
1994. ISSN 0305-1048. Dispon´ıvel em: <http://dx.doi.org/10.1093/nar/22.22.4673>.
5 JUAN, D.; PAZOS, F.; VALENCIA, A. High-confidence prediction of global
interactomes based on genome-wide coevolutionary networks. Proceedings of the
National Academy of Sciences, p. 0709671105+, January 2008. Dispon´ıvel em:
<http://dx.doi.org/10.1073/pnas.0709671105>.
6 WONG, K. M.; SUCHARD, M. A.; HUELSENBECK, J. P. Alignment uncertainty
and genomic analysis. Science, v. 319, n. 5862, p. 473–476, January 2008. Dispon´ıvel em:
<http://dx.doi.org/10.1126/science.1151532>.
7 FAVIA, A. D. et al. Molecular docking for substrate identification: the short-chain
dehydrogenases/reductases. J Mol Biol, European Molecular Biology Laboratory-European
Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge CB10
1SD, UK. afavia@ebi.ac.uk, v. 375, n. 3, p. 855–874, January 2008. ISSN 1089-8638.
Dispon´ıvel em: <http://dx.doi.org/10.1016/j.jmb.2007.10.065>.
8 FOSTER, I. Designing and Building Parallel Programs: Concepts and Tools for
Parallel Software Engineering. Boston, MA, USA: Addison-Wesley Longman Publishing
Co., Inc., 1995. ISBN 0201575949.
Referˆencias Bibliogr´aficas 114
9 OGATA, S. O. Alinhamento de seq
¨
uˆencias biol´ogicas com o uso de algoritmos gen´eticos.
Disserta¸c˜ao (Mestrado) — UFSCAR - Universidade Federal de S˜ao Carlos, 2005.
10 NEEDLEMAN, S.; WUNSCH, C. A general method applicable to the search for
similarities in the amino acid sequence of two proteins. J Mol Biol, v. 48, n. 3, p. 443–53,
1970.
11 SMITH, T. F.; WATERMAN, M. S. Identification of common molecular
subsequences. Journal of Molecular Biology, v. 147, p. 195–197, 1981. Dispon´ıvel em:
<citeseer.ist.psu.edu/smith81identification.html>.
12 LUO, J. et al. Parallel multiple sequence alignment with dynamic scheduling. In:
ITCC ’05: Proceedings of the International Conference on Information Technology:
Coding and Computing (ITCC’05) - Volume I. Washington, DC, USA: IEEE Computer
Society, 2005. p. 8–13. ISBN 0-7695-2315-3.
13 FENG, D. F.; DOOLITTLE, R. F. Progressive sequence alignment as a prerequisite
to correct phylogenetic trees. J Mol Evol, Department of Chemistry, University of
California-San Diego, La Jolla 92093., v. 25, n. 4, p. 351–360, 1987. ISSN 0022-2844.
Dispon´ıvel em: <http://view.ncbi.nlm.nih.gov/pubmed/3118049>.
14 TAYLOR, W. A flexible method to align large numbers of biological sequences. J.
Mol. Evol., v. 28, p. 161–169, 1988.
15 EDGAR, R. C.; SJ
¨
oLANDER, K. A comparison of scoring functions for protein
sequence profile alignment. Bioinformatics, Oxford University Press, Oxford, UK, v. 20,
n. 8, p. 1301–1308, 2004. ISSN 1367-4803.
16 WALLACE, I. M.; ORLA, O.; HIGGINS, D. G. Evaluation of iterative
alignment algorithms for multiple alignment. Bioinformatics, Oxford University
Press, v. 21, n. 8, p. 1408–1414, April 2005. ISSN 1367-4803. Dispon´ıvel em:
<http://dx.doi.org/10.1093/bioinformatics/bti159>.
17 EDGAR, R. C. Muscle: a multiple sequence alignment method with reduced
time and space complexity. BMC Bioinformatics, Department of Plant and Microbial
Biology, 461 Koshland Hall, University of California, Berkeley, CA 94720-3102,
USA. bob@drive5.com, v. 5, n. 1, August 2004. ISSN 1471-2105. Dispon´ıvel em:
<http://dx.doi.org/10.1186/1471-2105-5-113>.
18 EDGAR, R. Local homology recognition and distance measures in linear time using
compressed amino acid alphabets. Nucleic Acids Res, v. 32, p. 380–385, 2004.
19 LAWLER, E. L.; WOOD, D. E. Branch-and-bound methods: A survey. Operations
Research, v. 14, n. 4, p. 699–719, 1966.
Referˆencias Bibliogr´aficas 115
20 YU, K.-M. et al. Parallel branch-and-bound algorithm for constructing evolutionary
trees from distance matrix. In: HPCASIA ’05: Proceedings of the Eighth International
Conference on High-Performance Computing in Asia-Pacific Region. Washington, DC,
USA: IEEE Computer Society, 2005. p. 66. ISBN 0-7695-2486-9.
21 HIGGS, P. G.; ATTWOOD, T. K. Bioinformatics and molecular evolution. [S.l.]:
Blackwell Publishing, 2005. 384 p.
22 DURBIN, R. et al. Biological Sequence Analysis : Probabilistic Models of Proteins
and Nucleic Acids. Cambridge University Press, 1999. Paperback. ISBN 0521629713.
Dispon´ıvel em: <http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-
20&path=ASIN/0521629713>.
23 SETUBAL, J.; MEIDANIS, J. Introduction to Computational Molecular Biology.
[S.l.]: PWS Publishing, 1997.
24 QUINN, M. J. Parallel Programming in C with MPI and OpenMP.
McGraw-Hill Education (ISE Editions), 2003. Paperback. ISBN 0071232656.
Dispon´ıvel em: <http://www.amazon.fr/exec/obidos/redirect?tag=citeulike06-
21&path=ASIN/0071232656>.
25 GABRIEL, E. et al. Open MPI: Goals, concept, and design of a next generation
MPI implementation. In: Proceedings, 11th European PVM/MPI Users’ Group Meeting.
Budapest, Hungary: [s.n.], 2004. p. 97–104.
26 FORUM, M. P. I. MPI: A Message Passing Interface Standard. Junho 1995.
http://www.mpi-forum.org/.
27 FORUM, M. P. I. MPI-2: Extensions to the Message Passing Interface. Julho 1997.
http://www.mpi-forum.org/.
28 GRAHAM, R. L.; WOODALL, T. S.; SQUYRES, J. M. Open MPI: A flexible high
performance MPI. In: Proceedings, 6th Annual International Conference on Parallel
Processing and Applied Mathematics. Poznan, Poland: [s.n.], 2005.
29 SUN, X.-H.; NI, L. M. Another view on parallel speedup. In: Supercomputing ’90:
Proceedings of the 1990 conference on Supercomputing. Los Alamitos, CA, USA: IEEE
Computer Society Press, 1990. p. 324–333. ISBN 0-89791-412-0.
30 BERTSEKAS, D. et al. Parallel computing in network optimization. In: In Handbooks
in Operations Research. [S.l.: s.n.], 1995. p. 330–399.
31 KARRELS, E.; LUSK, E. Performance analysis of MPI programs. In: DONGARRA,
J.; TOURANCHEAU, B. (Ed.). Proceedings of the Workshop on Environments and Tools
For Parallel Scientific Computing. [S.l.]: SIAM Publications, 1994. p. 195–200.
Referˆencias Bibliogr´aficas 116
32 CHAN, A.; GROPP, W.; LUSK, E. An efficient format for nearly constant-time
access to arbitrary time intervals in large trace files. Scientific Programming, IOS Press,
Amsterdam, The Netherlands, The Netherlands, v. 16, n. 2-3, p. 155–165, 2008. ISSN
1058-9244.
33 LUSK, E.; CHAN, A. Early experiments with the OpenMP/MPI hybrid programming
model. In: EIGENMANN, R.; SUPINSKI, B. R. de (Ed.). OpenMP in a New Era of
Parallelism. [S.l.]: Springer, 2008. (Lecture Notes in Computer Science, v. 5004), p. 36–47.
IWOMP, 2008.
34 WU, C. E. et al. From trace generation to visualization: A performance framework
for distributed parallel systems. SC Conference, IEEE Computer Society, Los Alamitos,
CA, USA, v. 0, p. 50, 2000. ISSN 1063-9535.
35 ZAKI, O. et al. Toward scalable performance visualization with Jumpshot. High
Performance Computing Applications, v. 13, n. 2, p. 277–288, Fall 1999.
36 TRELLES, O. On the parallelization of bioinformatic applications. Briefings in
Bioinformatics, v. 2, p. 181–194, 2001.
37 LI, K.-B. Clustalw-mpi: Clustalw analysis using distributed and parallel computing.
Bioinformatics, v. 19, p. 1585–1586, 2003.
38 BOUKERCHE, A. et al. Parallel strategies for the local biological sequence alignment
in a cluster of workstations. J. Parallel Distrib. Comput., Academic Press, Inc., Orlando,
FL, USA, v. 67, n. 2, p. 170–185, 2007. ISSN 0743-7315.
39 BOUKERCHE, A. et al. An exact parallel algorithm to compare very long biological
sequences in clusters of workstations. Cluster Computing, Kluwer Academic Publishers,
Hingham, MA, USA, v. 10, n. 2, p. 187–202, 2007. ISSN 1386-7857.
40 CATALYUREK, U. et al. A component-based implementation of multiple sequence
alignment. In: SAC ’03: Proceedings of the 2003 ACM symposium on Applied computing.
New York, NY, USA: ACM, 2003. p. 122–126. ISBN 1-58113-624-2.
41 ZOLA, J. et al. Parallel multiple sequence alignment with local phylogeny search by
simulated annealing. Parallel and Distributed Processing Symposium, International, IEEE
Computer Society, Los Alamitos, CA, USA, v. 0, p. 279, 2006.
42 DU, Z.; LIN, F. pnjtree: a parallel program for reconstruction of neighbor-joining
tree and its application in clustalw. Parallel Comput., Elsevier Science Publishers B.
V., Amsterdam, The Netherlands, The Netherlands, v. 32, n. 5, p. 441–446, 2006. ISSN
0167-8191.
43 LOPES, H. S.; MORITZ, G. L. A distributed approach for a multiple sequence
alignment algorithm using a parallel virtual machine. Engineering in Medicine and
Referˆencias Bibliogr´aficas 117
Biology Society, 2005. IEEE-EMBS 2005. 27th Annual International Conference of the,
p. 2843–2846, 2005.
44 DU, Z.; JI, Z.; LIN, F. Parallel computing for optimal genomic sequence alignment.
In: FSKD. [S.l.: s.n.], 2006. p. 532–535.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
