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

Abstract

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. __________________________________________________________________________________________ ABSTRACT

The Multiple Sequence Alignment (MSA) is an important problem in Bioinformatics, allowing interpretation of phylogenetic trees, identification of domains and conserved motifs and prediction of secondary structures. As the MSA is an NP-Hard problem, heuristics are used. The DIALIGN-TX program implements an iterative heuristic to calculate the MSA in three phases. Phase 1 calculates all pairwise comparisons of the input sequences, requiring the largest portion of execution time for the calculation of MSA. This phase has great potential for parallel execution, since its pairwise comparisons are independent from each other. The heterogeneous multicore clusters arise from the gradual expansion of environments composed of homogeneous multicore clusters. To explore the multicore and heterogenous characteristics of that cluster system, it is intuitive that the use of a hybrid programming model with message passing and shared memory is more appropriate, as well as a task allocation strategy for addressing the different computation powers in its nodes. This dissertation proposes and evaluates a hybrid distributed strategy that allows DIALIGN-TX to be executed in a heterogeneous multicore cluster. The proposed strategy was implemented in a heterogeneous multicore cluster with three nodes with diferent processing capabilities and clock speeds. A hybrid programming model with message passing for communication among nodes and shared memory for communication among cores of the same node was used. Moreover, three new strategies for task allocation were implemented: Hybrid Fixed (HFixed), Hybrid Self-Scheduling (HSS) and Hybrid Weighted Factoring (HWF). The results showed that the proposed solution can reduce quite significantly the execution time of the first phase of the MSA of DIALIGN-TX. Furthermore, they also showed that choosing an appropriate task allocation centeringpolicy has fundamental importance for the performance of the solution.