Comunicação Não Bloqueante

A forma mais comum de comunicação entre dois processos no MPI é através de Sends e Receives, implementados pelas funções MPI_Send e MPI_Recv, respectivamente. Em teoria essas funções são bloqueantes, no sentido de que ao enviar uma mensagem com MPI_Send, o programa para sua execução até que o processador para o qual ele enviou a mensagem receba sua mensagem com um MPI_Recv.

Imagine um cenário simples com 2 processos que queiram trocar mensagens entre si. Localmente, ambos executam um MPI_Send seguido de um MPI_Recv. O diagrama abaixo ilustra esse caso:


Diagrama ilustrando potencial deadlock

No caso em que o send e o receive são bloqueantes, teremos o chamado deadlock (no diagrama de dependência, ele é caracterizado por um ciclo dirigido), ou seja, os processadores ficam esperando infinitamente.


Exemplo de deadlock no dia-a-dia (foto recebida por email).

Felizmente, a maior parte das implementações do padrão MPI, provê um buffer para que o send não seja bloqueante. Ao chamar MPI_Send, a mensagem é copiada em um buffer e a execução do programa continua. Aí quando o destinatário chama MPI_Recv, ele lê a mensagem do buffer. Em implementações onde não há o esse buffer, deve-se usar MPI_Bsend, onde o buffer deve ser explicitamente alocado.

Porém, a chamada MPI_Recv continua bloqueante. Dependendo da aplicação, essa característica pode ser custosa, pois enquanto espera uma mensagem, o processador fica ocioso. Recentemente me deparei com uma situação que sofria desse problema.

Suponha três processos p1, p2, p3, sendo que p1 é o processo que gerencia a execução do algoritmo (leitura de entrada, repassar tarefa para p2 e p3, além de processar os resultados de p2 e p3). Ao processo p1 é dado um certo número de iterações que deverão executadas por p1, p2 e p3. Como cada iteração executada leva um tempo diferente, usamos a estratégia de distribuição por demanda.

Assim, p1 inicialmente envia um bloco de iterações a p2 e p3 para que estes executem. Enquanto isso, ele trata de executar também algumas iterações. Ao final dessa execução, ele comunica com p2 e p3 para verificar se eles já terminaram suas iterações. Se sim, envia mais um bloco de iterações para que eles executem. Caso contrário, volta para executar mais iterações, fazendo a verificação novamente, até que o número especificado de iterações seja executado.

Para fazer a comunicação com p2 (ou p3), o processo p1 pode chamar MPI_Recv, esperando que p2 retorne seus resultados. Depois, ele decide se ainda há iterações para serem executadas. Então, envia com o MPI_Send um ‘ok’, em caso positivo, ou um ‘stop’, em caso negativo. Por outro lado, o processo p2, ao terminar de executar seu bloco de iterações, envia seus resultados com o MPI_Send e espera a resposta de p1 para saber se deve parar ou continuar, através do MPI_Recv.

É muito provável que algum dos processos fique esperando os outros terminarem suas tarefas, enquanto poderia estar executando mais iterações. Nesse caso, operações de send e receive não bloqueantes seriam mais adequadas. Felizmente, a biblioteca MPI oferece essa alternativa.

Sends e Receives não bloqueantes

No MPI, as funções que implementam send e receive não bloqueantes são denominadas MPI_Isend e MPI_Irecv, respectivamente. Elas não bloqueiam, mas também não efetuam de fato a operação de send/receive, apenas iniciam o processo.

Ao chamar uma dessas funções, é retornado um objeto do tipo ‘request’, que indica o status do send ou do receive. Esse ‘request’ pode ser verificado basicamente de duas maneiras: através da função MPI_Wait ou da função MPI_Test. A primeira bloqueia a execução até que o send ou receive se complete. A segunda retorna uma flag que é true se a operação completou, ou false caso contrário.

O exemplo apresentado anteriormente pode ser adaptado para usar comunicação não bloqueantes. Agora, o processador p1 distribui o bloco de iterações e começa a executar as suas. Ao final, ele chama o MPI_Irecv para indicar que está esperando uma mensagem de p2 e p3. Aí então ele verifica através do MPI_Test se a sua mensagem já chegou. Em caso positivo, ele executa o MPI_Isend dizendo se é para parar ou continuar a execução. Caso não tenha chegado a mensagem, ele simplesmente executa mais um bloco de iterações e volta para verificar novamente.

No outro lado, o processo p2 (ou p3), ao terminar suas iterações, envia uma mensagem para p1 com MPI_Isend e então invoca MPI_Irecv para indicar que está esperando a resposta de p1. Em seguida, chama MPI_Test para determinar se a mensagem já chegou. Em caso negativo, volta a executar mais um bloco de iterações. Em caso positivo, verifica se a mensagem é para que ele pare de executar.

Experimentos computacionais

Implementei as duas estratégias mencionadas acima, simulando a execução de iteração com um sleep de um tempo aleatório entre 1 e 5 segundos. Fixei 100 iterações e variei os tamanhos de bloco em 1, 5, 10 e 20. A tabela abaixo sumariza os tempos de execução obtidos e os tempos de espera.

O tempo de espera é a soma do tempo de chamada de cada função de send ou receive. Mais especificamente, eu meço o tempo com MPI_Wtime antes e depois de chamar cada uma dessas funções, e somo a diferença desses tempos.

Para medir o tempo total, foi medido apenas no processador mestre, mas para garantir que a medida corresponde ao tempo do processador que terminou por último, usei a função MPI_Barrier, que bloqueia todo mundo que a chama enquanto houver que ainda não a chamou.

Tabela: Comparação de tempo de execução total e tempo ocioso total entre a estratégia bloqueante e a não bloqueante para diversos tamanhos de blocos.

Verificamos, como era esperado, que o uso de chamadas não bloqueantes resulta em tempo ocioso nulo. O tempo de execução total tende a aumentar com o tamanho dos blocos.

Observe que para blocos pequenos, a estratégia não-bloqueante se deu melhor, devido aos tempos de processador ocioso da estratégia bloqueante. Porém, para blocos maiores, a estratégia bloqueante é mais rápida. Uma explicação para isso é que na estratégia não-bloqueante, o número de iterações realizadas pode superar a quantidade estabelecida de iterações, pois quando o MPI_Test retorna falso, o processador vai executar outro bloco de iterações, mesmo que nesse momento o número de iterações já tenha sido atingido.

Da forma como o tempo de processador ocioso é medido, está incluindo o tempo de envio e recebimento das mensagens. Note então que esse tempo é irrelevante perto do tempo de execução do algoritmo. Assim, usar blocos de tamanho pequeno, em detrimento do aumento de trocas de mensagem, e comunicação não-bloqueante parece uma boa ideia.

Os comentários estão fechados.

%d bloggers like this: