Implementação e Avaliação de Desempenho do LCS Paralelo em Cluster Multicore - Lauredo, Alexandre; de Mesquita, Joyce; Santiago, Leandro; de Castro, Maria Clicia; Sena, Alexandre; Marzulo, Leandro (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD); 2014: Anais do XV Simpósio em Sistemas Computacionais de Alto Desempenho, 2014)
Encontrar a maior subsequência comum (LCS) entre duas sequências é uma técnica muito utilizada para o alinhamento de sequências de DNA. Através da programação dinâmica se consegue a solução exata para o LCS, com complexidade de tempo e espaço O(m x n), onde m e n são os tamanhos das sequências. Algoritmos paralelos são fundamentais, tanto pelo tempo de processamento, quanto pela quantidade de memória necessária para processar sequências grandes. Logo, o objetivo deste trabalho é implementar e avaliar quatro versões paralelas do LCS para máquinas com memória distribuída, otimizando o paralelismo entre nós e também dentro de cada nó e buscando uso homogêneo de memória nos nós de processamento.