Dissertação

SIMD Parallelization of Profile HMMs EVALUATED

A comparação de sequências é uma tarefa crucial em bioinformática, para avaliar a semelhança (homologia) entre regiões de sequências biológicas. Pesquisa por Homólogos envolve ou alinhamento, ou modelos probabilísticos como os Modelos Ocultos de Markov (HMMs), e ambos usam algoritmos de Programação Dinâmica Dado as enormes bases de dados, é essencial paralelizar as pesquisas. As estratégias de paralelização podem ser divididas entre Intra-tarefa (apenas uma tarefa paralelizada) e Inter-tarefa (várias tarefas realizadas em paralelo). Uma estratégia Intra-tarefa eficiente é o método intercalado do Farrar, usado pelo HMMER em SIMD de processadores comuns (por exemplo, SSE do x86). Foi desenvolvida uma solução Inter-tarefa alternativa para o HMMER, baseada na abordagem do Rognes de 2011, também em SSE. Esta abordagem, denominada COPS, resolveu alguns problemas do Rognes, e implementou uma técnica Cache-Oblivious para processar HMMs de comprimentos arbitrários. Os resultados são fortemente positivos: mais rápido que o HMMER para todos os testes realizados, e com um speedup máximo de 2x contra o HMMER. Também foi explorado o potencial de uma paralelização adicional Intra-tarefa com threads, através de um modelo frente-de-onda, obtendo resultados positivos. Assim, são abertos novos caminhos para paralelização de HMMs. Demonstrou-se ser uma alternativa mais eficiente face à implementação Farrar do HMMER, especialmente para modelos longos. Os métodos estudados aqui podem ser aplicados a outras áreas, tais como reconhecimento de voz. Também podem-se estender a AVX2, o sucessor do SSE, de 256-bit.
Alinhamento, paralelizacao, SSE, Modelos Ocultos de Markov, HMMER, Viterbi

Outubro 30, 2013, 16:30

Documentos da dissertação ainda não disponíveis publicamente

Orientação

CO-ORIENTADOR

Nuno Filipe Valentim Roma

Departamento de Engenharia Electrotécnica e de Computadores (DEEC)

Professor Auxiliar

ORIENTADOR

Luís Manuel Silveira Russo

Departamento de Engenharia Informática (DEI)

Professor Auxiliar