Non-Standard Contractions

5.2.1 MSA exato com MPI

Helal et al. [42–44] apresentam em 2009 estratégias em MPI para calcular em um cluster de computadores o alinhamento múltiplo exato, reduzindo o espaço de busca sem usar o Carrillo-Lipman (Seção 2.3.1.1) ou A-Star (Seção 2.3.2). Em [44], Helal et al. uti- lizam uma abordagem mestre/escravo, onde o espaço é dividido em ondas de computação que contém partições equidistantes de um mesmo ponto de origem. Essas ondas são pré- processadas para acelerar a computação. O processo mestre é responsável por consumir recursos e escalonar as partições nos processadores. Há um custo de comunicação dentro e através das ondas de processamento. Na abordagem distribuída [42, 43], não existe um processador mestre e o escalonamento de partições se dá através da interação entre processadores vizinhos.

O algoritmo proposto em [44] foi implementado em C eMPI, podendo ser executado em ambientes com até 64 processadores. Foi utilizado um SunFire X2200 com 2 processadores AMD Opteron quad core de 2,3 GHz, 512 Kb L2 cache e 2 MB L3 em cada processador. A estação estava equipada com 8 GB RAM e 8 cores foram utilizados.

Nos resultados experimentais, o número de sequências comparadas é muito pequeno (até 5) e seu tamanho máximo também é pequeno (até 41). Como o algoritmo imple- mentado é exato e, portanto, executa-se em tempo exponencial, pode ser notada a grande diferença entre os tempos de comparação de três sequências e os tempos de comparação de cinco sequências.

5.2.2 MSA exato em FPGA

Utilizando FPGA (Seção 4.2), Yamaguchi et al. [79] implementaram o algoritmo Carrillo-Lipman (Seção 2.3.1.1) para o alinhamento múltiplo exato. Sua solução consiste em utilizar o FPGA para calcular o escore visitando todos os vizinhos de uma célula do espaço de busca e utilizar dados calculados em software para auxiliar na redução do espaço de busca.

No circuito implementado, a programação dinâmica N-dimensional é realizada repetindo-a em duas dimensões e variando as outras dimensões. Considere X, Y , Z os tamanhos de três sequências nos eixos x, y, z respectivamente. Sejam Wx, Wy, Wz as

qualquer entrada ou saída de dados da placa. A Figura 5.2 mostra como a programação dinâmica em três dimensões é realizada através de repetições de uma programação dinâ- mica de duas dimensões. A área em processamento é chamada de janela de varredura [79].

Para implementar o método de Carrillo-Lipman, seja P , assim como mostrado na Seção 2.3.1.1, o conjunto do espaço de busca reduzido. O limite do espaço de busca que deve ser calculado para obter o alinhamento é calculado em CPU e carregado em bancos externos de memória na placa FPGA. Antes de iniciar o cálculo de alguma janela de varredura, o algoritmo decide se a janela de varredura atual deve ou não ser calculada. Desta forma, o espaço de busca é reduzido.

Figura 5.2: Programação dinâmica em três dimensões [79].

Dois circuitos foram implementados, um para alinhamento de quatro sequências e outro para alinhamento de cinco sequências com frequências de 36 MHz e 31 MHz, res- pectivamente. A frequência baixa de operação é causada pelos seletores para escolher entre 2n_{− 1 candidatos.}

O MSA emFPGA foi comparado com o MSA 2.0 (Seção [31]), executado em um pro- cessador Intel Pentium 4 3 GHz com 2 GB de memória. O speedup obtido é influenciado pela similaridade das sequências comparadas. Quando as sequências são muito semelhan- tes, a solução em software funciona muito bem, pois grande parte do espaço de busca não é calculado. Por outro lado, grandes blocos de processamento são sempre executados em FPGA, resultando em um desempenho inferior neste caso.

Por não ser sempre melhor, é aconselhável utilizar a solução em FPGA em paralelo com a solução em software, pois algumas execuções podem ser feitas em menor tempo em CPU. Para problemas de baixa similaridade foi possível obter speedups de até 50× quando comparada à solução em software.

5.2.3 MSA exato com Carrillo-Lipman (MSA-GPU)

Em um trabalho anterior, nós propusemos o MSA-GPU [124], uma solução que utiliza GPU (Seção 4.4) para resolver o alinhamento múltiplo exato. Para reduzir o espaço de busca foi utilizado o método de Carrillo-Lipman (Seção 2.3.1.1). Foram propostas duas estratégias: fine-grained e coarse-grained.

Figura 5.3: Visão geral das estratégias [124].

A Figura 5.3 fornece uma visão geral da solução. Primeiramente, o usuário provê as sequências e o limite de Carrillo-Lipman δmsa (delta_cl) (Seção 2.3.1.1). Então, é feita a

leitura das sequências, a inicialização e cópia dos dados para aGPU. Após isso, os kernels da GPU são executados de acordo com a estratégia utilizada. Após a execução de cada kernel, a variável bound_reached é utilizada para informar se o limite Carrillo-Lipman foi atingido e as células podem ser descartadas do espaço de busca. Ao final de toda a execução, o escore ótimo é retornado ao usuário.

Na estratégia Coarse-Grained busca-se aumentar o paralelismo calculando o maior nú- mero de células possível do espaço de busca simultaneamente. Porém, devido a limitações de recursos do hardware, nem sempre é possível criar um wavefront multidimensional do tamanho do espaço de busca, e neste momento inicia-se o percorrimento do espaço de busca projetando-se em uma dimensão. Foi observada uma queda de paralelismo nesta estratégia. Por este motivo, decidiu-se criar uma outra estratégia, de granularidade mais fina, e que percorre o espaço de busca em projeções de diagonais 2D conforme a proposta de Yamaguchi et al. (Seção 5.2.2).

Nesta estratégia de granularidade fina, o espaço de busca é otimizado para ser percor- rido conforme projeções de diagonais 2D, de forma que quando todo o espaço de busca é percorrido em uma diagonal, ocorre o deslocamento em um sentido e então o processo é reiniciado. A granularidade deste método é maior pois o cálculo de cada célula não é feita apenas por uma thread, mas por 2n_{− 1, onde n é o número de sequências. Desta}

forma, cada thread é responsável por uma célula na equação de recorrência, e ao final elas fazem uma comparação em paralelo para decidir qual valor é o melhor para ser utilizado na célula.

O MSA-GPU foi implementado em CUDA C e testado em uma estação com uma

placa NVIDIA GeForce GTX 280 e 1 GB RAM e um processador AMD Opteron 248 2,2 GHz. Os resultados foram coletados com conjuntos de 3 sequências reais e sintéticas de aminoácidos e mostraram que para as sequências de menor tamanho, a estratégia fine-grained consegue melhores resultados que a estratégia coarse-grained mesmo quando emprega menos threads. Quando o tamanho das sequências é aumentado, a estratégia coarse-grained ultrapassa a fine-grained com um bloco, pois o número de threads não é o suficiente para lidar com o paralelismo. Porém, para todas as sequências comparadas, a estratégia fine-grained com múltiplos blocos consegue os melhores tempos de execução entre as estratégias, com uma grande vantagem sobre as outras estratégias, conseguindo reduzir o tempo de 8 minutos e 55 segundos (coarse-grained) para 6,62 segundos (fine- grained multibloco).

A estratégia fine-grained com múltiplos blocos foi comparada com o programa MSA 2.0 (Seção 2.3.1.2). Os resultados mostram que, para instâncias pequenas do problema a execução do programa em CPU é muito rápida, obtendo melhores resultados do que a GPU. Porém, para os casos com menor similaridade, o programa MSA 2.0 não se executa eficientemente com os parâmetros padrão, e então foi necessária uma nova execução, com outros parâmetros. Para estes casos, o programa MSA 2.0 foi mais lento que a implementação em GPU, sendo que aGPUapresenta um speedup de 7, 8× para o caso de sequências de média similaridade e 6, 02× e 8, 60× para os casos de sequências de baixa similaridade, de comprimento médio e longo, respectivamente.

5.2.4 MSA exato com A-Star em Cluster

Niewiadomski et al. [89], apresentaram duas estratégias, uma serial e uma paralela para resolver o problema do alinhamento múltiplo exato de sequências. Nele, é usada uma variação do A-Star (Seção 2.3.2) chamada Frontier A* (Seção 2.3.2), combinada com a otimização DDD (Seção 2.3.2).

A principal contribuição do trabalho é o PFA*-DDD, uma versão paralela do algoritmo que combina o Frontier A* e o DDD, executando-se em um cluster de computadores. Uma

dificuldade em criar a versão paralela é em como distribuir o trabalho entre as estações de maneira eficiente. A ideia da estratégia proposta é particionar a fila de tarefas em grupos disjuntos entre as n estações do cluster. Todo o trabalho envolvendo nós do i-ésimo grupo é processado pela i-ésima estação de cluster. Cada nó é representado por um inteiro e o particionamento inicial é feito dividindo-se o intervalo inteiro em n intervalos. A cada iteração o PFA*-DDD pode escolher entre manter o particionamento decidido, ou caso um dos nós acredite estar sobrecarregado, ele pode iniciar um procedimento para dividir novos intervalos entre o cluster.

O artigo mostra os resultados para a solução de duas instâncias do BAliBASE [130] em um cluster de 32 cores. Essas instâncias estão entre as mais difíceis da referência 1 do BAliBASE , apresentando speedups de até 32x usando 32 cores. No entanto, a implementação limita o número de sequências entre 3 e 8, de forma que limita os testes a serem realizados em instâncias maiores do problema.

5.2.5 MSA exato com A-Star e Memória Externa

Um dos principais fatores limitantes do algoritmo A-Star é a memória para manter a lista de nós abertos e fechados. Hatem et al. [37] propuseram uma estratégia com o uso de uma memória externa (disco) para poder solucionar o problema em instâncias mais difíceis.

A principal contribuição deste trabalho é propor uma estratégia que combina as expan- sões parciais do PEA* com a técnica de hash do HBDDD. Esse nova estratégia é chamado de Parallel External Partial Expansion A* (PE2A*) e foi testada em uma estação com 12 discos em paralelo, visto que o uso intensivo de disco do algoritmo visa ganho com I/O paralelo. São utilizadas 24 threads durante a execução deste teste.

Nos resultados experimentais, foram utilizadas todos os conjuntos de sequência da referência 1 do BAliBASE [130]. A estação utilizada estava equipada com dois processa- dores Intel Xeon X5660, 2,80 GHz e 6 cores, além de ter 12 GB de RAM e 12 discos de 320 GB.

Os resultados mostram que o PE2A* consegue reduzir em cerca de 60% o tempo de execução quando comparado a outra abordagem, o PA*-DDD [68]. A instância que mais tempo exigiu foi a 1pamA, resolvida pelo PA*-DDD em 32 dias e 14 horas, porém o PE2A* resolve em 9 dias e 8 horas. Os autores afirmam que foi a primeira vez que estas instâncias foram resolvidas utilizando affine gap em uma única máquina.