MPI – Trocas de mensagens

Nesse post vou comentar sobre alguns aspectos de comunicação entre nós, através da biblioteca MPI, a qual introduzi neste outro post.

Comunicação ponto a ponto

Como diz o próprio nome, a biblioteca MPI (interface de passagem de mensagens), tem como característica principal a comunicação entre nós através de mensagens. O modo mais simples de trocar mensagens, é através das funções de envio e recebimento de mensagens, respectivamente MPI_Send e MPI_Recv.

A ideia é muito próxima do envio de cartas do mundo real: o remetente deve especificar para a função MPI_Send, a mensagem e o destinatário. O destinatário, por sua vez, especifica para a função MPI_Recv o remetente de quem ele está esperando a carta. Um detalhe é que a função MPI_Recv é bloqueante, ou seja, o destinatário fica bloqueado até receber a mensagem que está esperando.

Broadcast

Se um processo p quiser mandar uma mensagem para todos os outros, pode utilizar a função MPI_Send para cada outro processo. Se o envio de cada uma dessas mensagens levar um tempo t e houver n processos, o tempo necessário para que todos os processos tenham a informação passada pelo processo p, será da ordem de t(n – 1). Além de não ser muito eficiente, ainda há o empecilho de o processo p estar concentrando todo o trabalho em si, o que não é interessante, uma vez que nosso objetivo é paralelizar o código.

Uma ideia é usar uma topologia em árvore para a distribuição da mensagem. Suponha que n = 8 e o processo 0 quer enviar a mensagem. A troca de mensagens segue o esquema da figura abaixo.


Topogia de árvore

Inicialmente o nó 0 envia a mensagem para o nó 1. Em um segundo momento, o nó 0 envia a mensagem para o nó 2, ao mesmo tempo em que o nó 1 envia a mensagem para o nó 3. Agora os nós 0, 1, 2 e 3 possuem a informação que o nó 0 queria transmitir. No terceiro estágio, o nó 0 envia para 0 4, o nó 1 para o 5, o 2 para o 6 e o 3 para o 7. Assim, todos os nós receberam a mensagem em 3 estágios. Não é difícil ver que o tempo gasto será proporcional à altura da árvore, que por sua vez é O(log n). Assim, o tempo total gasto é O(t log n). Na MPI, essa estratégia é implementada pela função MPI_Bcast.

Reduce

Imagine que paralelizamos um laço que fazia a soma de um vetor, distribuindo um pedaço para cada um dos processos. Depois de calculada a soma, é preciso juntar os resultados. No caso da soma, basta que cada nó envie seu resultado para o processo principal e que este os some para obter a resposta final. Assim como a versão simples do broadcast, esse esquema é proporcional ao número de nós.

Aqui, também é possível usarmos a topologia de árvore da seguinte forma: cada nó envia seu resultado para o seu predecessor na árvore. Pelo exemplo da figura anterior, o nó 0 e o nó 4 vão enviar para o nó 0. Na verdade não é preciso que o nó 0 envie o resultado para si mesmo, basta que ele receba a resposta do nó 4 e some com o valor que ele já tinha calculado. Assim, cada nó intermediário fará a soma dos seus dois filhos, de forma que no final o nó 0 conterá a soma total. Novamente conseguimos reduzir o tempo para O(t log n). Na MPI, essa abordagem é utilizada pela função MPI_Reduce.

Reduce + Broadcast

Ao realizar o reduce, o nó 0 conterá a soma total, mas os outros nós terão apenas somas parciais. Se quiséssemos que todos os nós tivessem a soma total, uma possibilidade seria o nó 0 fazer um broadcast para todos os outros nós, ou seja, um reduce seguido de um broadcast. Há um meio mais eficiente de fazer isso, através da topologia borboleta.

Topologia Borboleta

Para entender melhor esse esquema, consideremos a informação que o nó 0 envia (em verde). No primeiro estágio ele envia sua informação para o nó 4. Logo, os nós 0 e 4 têm a informação inicial do nó 0. No segundo estágio, o nó 0 envia sua informação para o nó 2, enquanto o nó 4 envia sua informação para o nó 6. Agora os nós 0, 2, 4 e 6 têm a informação do nó 0. Finalmente no estágio 3, o nó 0 envia para o nó 1, o 2 para o 3, o 4 para o 5 e o 6 para o 7. Assim, todos têm a informação inicial do nó 0. Seguindo a mesma lógica para os outros nós, concluímos que ao final do terceiro estágio, todos os nós terão informação dos outros nós. Se cada nó somar o seu conteúdo com o que receber, no final todos os nós terão as somas totais. A função MPI_Allreduce implementa essa abordagem.

Os comentários estão fechados.

%d bloggers like this: