Estratégia distribuída híbrida em cluster multicore heterogêneo para alinhamento múltiplo de sequencias biológicas com o dialign-tx

AUTOR(ES)

Emerson de Araújo Macedo

DATA DE PUBLICAÇÃO

2010

RESUMO

O Alinhamento Múltiplo de Sequências (AMS) é um problema importante em Bioinformática, permitindo a interpretação de árvores filogenéticas, a identificação de domínios e padrões conservados e a predição de estruturas secundárias. Como o AMS é um problema NP-Difícil, heurísticas são utilizadas. O programa DIALIGN-TX implementa uma heurística iterativa para calcular o AMS em três fases. A fase 1 calcula todas as comparações par a par das sequências de entrada, exigindo a maior parcela do tempo de execução para o cálculo do AMS. Esta fase possui grande potencial para execução em paralelo, pois as comparações par a par são independentes entre si. Os clusters multicore heterogêneos surgem da expansão gradual de ambientes compostos por clusters multicore homogêneos. Para explorar as características multicore e heterogênea desse sistema em cluster, é intuitivo que o emprego de um modelo de programação híbrido com trocas de mensagens e memória compartilhada seja mais apropriado, bem como de uma estratégia de alocação de tarefas que permita lidar com as diferentes capacidades de processamento de seus nós. A presente dissertação propõe e avalia um estratégia distribuída híbrida para que a ferramenta DIALIGN-TX seja executada num cluster multicore heterogêneo. A estratégia proposta foi implementada em um cluster multicore heterogêneo com três nós com capacidades de processamento e velocidades de clock diferentes. Foi utilizado um modelo híbrido de programação com troca de mensagens para a comunicação entre os nós e memória compartilhada para comunicação entre os cores de um mesmo nó. Foram implementadas três novas estratégias de alocação de tarefas, chamadas Hybrid Fixed (HFixed), Hybrid Self-Scheduling (HSS) e Hybrid Weighted Factoring (HWF). Os resultados obtidos mostraram que a solução proposta consegue reduzir de maneira bastante significativa o tempo de execução da fase 1 do AMS do DIALIGN-TX. Além disso, mostraram que a escolha de uma política de alocação de tarefas adequada é de fundamental importância para o desempenho da solução.

ASSUNTO(S)

ciencia da computacao programação paralela computação de alto desempenho bioinformatics sequence alignment bioinformática alinhamento de sequências parallel programming high-performance computing

Documentos Relacionados

• Alinhamento de seqüências biológicas em arquiteturas com memória distribuída
• Estratégia paralela para alinhamento múltiplo de sequências com algoritmo genético multi-ilha
• Alinhamento de seqüências biológicas com o uso de algoritmos genéticos.
• Alinhamento múltiplo progressivo de sequências de proteínas
• Multi-objective genetic algorithms applied to protein sequence alignment.