Biblioteca MPI

Introdução

Recentemente resolvi aprender um pouco sobre a biblioteca MPI (Message Passing Interface). Ela é uma das principais bibliotecas para fazer a paralelização de código. Existe uma outra chamada OpenMP. Pelo que andei pesquisando, OpenMP é feita para sistemas com memória compartilhada, como por exemplo uma máquina multicore. Nela temos vários processadores compartilhando uma mesma memória. Já o MPI é voltado para memória distribuída, como é o caso de clusters, que são basicamente um conjunto de máquinas rodando um sistema operacional distribuído. A vantagem do MPI é que ele é escalável para as diversas máquinas do cluster, enquanto o OpenMP fica restrito a uma só. Apesar de o MPI também rodar em uma máquina multicore só, podemos ter um desempenho menor em relação ao OpenMP, já que o primeiro não aproveita o fato da memória ser compartilhada. Uma abordagem híbrida pode ser uma boa solução. A nível de cluster, utilizamos o MPI e em cada nó (máquina) do cluster, usamos o OpenMP.

Super-computador Cray Jaguar, o computador mais rápido do mundo. Muitos dos super-computadores (top500) são clusters.

A paralelização de código consiste em quebrá-lo em pedaços que podem ser executados independentemente e distribuir para vários processadores. Assim, por exemplo, um programa que recebe um vetor de inteiros e soma seus elementos, provavelmente o fará através de um laço, parecido com o programa abaixo

int s = 0, v[ ] = {1,2,3,4};

for (int i=0; i<4; i++)
    s += v[i];

Se a máquina for multicore, podemos quebrar o laço em várias partes de forma que cada processador execute aquele pedaço do laço. Se o vetor tivesse 15.000 entradas e a máquina tiver quatro cores, usaríamos uma para gerenciar a distribuição de trabalho e as outras três para fazer os cálculos. O primeiro processador somaria os elementos de 0 a 4.999, o segundo de 5.000 a 9.999 e o terceiro de 10.000 a 14.999. Depois de computar a soma dos elementos, cada processador devolveria o resultado para o processador principal e este trataria de somar os resultados parciais. Uma propriedade importante que o programa acima tem é que cada iteração do laço é independente das outras. Assim, o resultado não ia ser diferente se eu resolvesse somar o vetor começando pelo último elemento. Isso não é verdade por exemplo, para o cálculo da recorrência de fibonacci. Nesse caso temos

Um loop para calcular o n-ésimo número de fibonacci não pode ser paralelizado. Programas como o da soma são exemplos fáceis de paralelizar, sendo apenas necessário distribuir pedaços das iterações para os processadores. Tais programas são ditos vergonhosamente (:P) paralelizáveis (do inglês embarrassingly parallel).

Para compilar um programa C++ utilizando MPI no linux, fazemos:

mpic++ programa.cpp -o programa

Em seguida, é preciso editar um arquivo de texto chamado ‘hostfile’ contendo o endereço dos nós do cluster (no caso de uma máquina, basta colocar localhost). Após isso é preciso inicializar o LAM (Local Area Multicomputer)

lamboot -v hostfile

Para executar o programa, basta fazer

mpirun -np <numero de threads> ./programa <argumentos do programa>

O programa iniciará com o número especificado de threads. Como queremos paralelizar o código, esse número pode ser a quantidade de processadores disponíveis. O laboratório IC3 da Unicamp possui um cluster com atualmente 6 nós, cada qual uma máquina com 4 processadores. Dessa forma, temos 24 processadores para paralelizar o código.

Testes

Para aprender um pouco sobre a biblioteca e testar suas capacidades, resolvi implementar o seguinte algoritmo: dado um vetor de n inteiros, execute uma função com complexidade para cada elemento do vetor. A ideia então é paralelizar esse código que é vergonhosamente paralelizável.

Testei duas abordagens: uma em que o número de iterações para cada processador é igual, ou seja, n dividido pelo número de processadores. A outra divide as iterações em pequenos blocos (e.g. blocos de tamanho 10) e distribui-se um bloco para cada processador. Conforme este termine de computar, retorna a resposta para o processador principal que se encarrega de mandar um novo bloco para aquele, até que todos os blocos tenham sido processados. Chamei a primeira estratégia de uniform-share e a outra de demand-share. Os processadores podem levar tempos diferentes para computar sua parte e por isso aqueles que terminarem primeiro vão ficar ociosos até que o último processo termine. Com o demand-share esse efeito é minimizado, pois quem terminar suas iterações mais rápido, acaba processando mais blocos. A desvantagem é que há um maior número de troca de mensagens nessa abordagem.

Fiz dois tipos de instâncias: a primeira consiste de 50.000 números aleatórios entre 10 e 20, enquanto a segunda consiste de 50.000 números indo de 10 a 20 em ordem crescente (os 5.000 primeiros números são 10, os próximos 5.000 são 11 e assim por diante). Chamei a primeira de random e a segunda de sequential.

Tempos (em segundos) para a instância random.

Aqui os tempos foram praticamente os mesmos. Eu imaginava que o overhead causado pelo número maior de mensagens pudesse aumentar o tempo do algoritmo por demanda, mas não foi o que se verificou.

Tempo (em segundos) para a instância sequential.

Para a instância sequential, aconteceu o que eu esperava: a divisão uniforme fez com que os últimos processadores ficassem com a parte mais demorada (só com elementos 20), o que prejudicou o tempo total de execução.

Próximos Passos

Pretendo fazer testes com problemas não tão vergonhosamente paralelizáveis e também aprender como integrar MPI e OpenMP. O prof. Rodolfo, especialista em arquitetura multicore, sugeriu também que eu tentasse otimizações em nível mais baixo, através das instruções SSE. Lembro vagamente o que são e por isso vou ter que dar uma revisada.

Os comentários estão fechados.

%d bloggers like this: