ti-enxame.com

Diferença entre as funções MPI_Allgather e MPI_Alltoall?

Qual é a principal diferença entre as funções MPI_Allgather e MPI_Alltoall no MPI?

Quero dizer, alguém pode me dar exemplos em que o MPI_Allgather será útil e o MPI_Alltoall não será? e vice versa.

Eu não sou capaz de entender a principal diferença? Parece que em ambos os casos todos os processos enviam elementos send_cnt para todos os outros processos participantes do comunicador e os recebem?

Obrigado

24
Kranthi Kumar

Uma imagem diz mais que mil palavras, então aqui estão várias ASCII imagens de arte:

rank    send buf                        recv buf
----    --------                        --------
 0      a,b,c         MPI_Allgather     a,b,c,A,B,C,#,@,%
 1      A,B,C        ---------------->  a,b,c,A,B,C,#,@,%
 2      #,@,%                           a,b,c,A,B,C,#,@,%

Este é apenas o habitual MPI_Gather, somente neste caso todos os processos recebem os blocos de dados, ou seja, a operação é sem raiz.

rank    send buf                        recv buf
----    --------                        --------
 0      a,b,c          MPI_Alltoall     a,A,#
 1      A,B,C        ---------------->  b,B,@
 2      #,@,%                           c,C,%

(a more elaborate case with two elements per process)

rank    send buf                        recv buf
----    --------                        --------
 0      a,b,c,d,e,f    MPI_Alltoall     a,b,A,B,#,@
 1      A,B,C,D,E,F  ---------------->  c,d,C,D,%,$
 2      #,@,%,$,&,*                     e,f,E,F,&,*

(fica melhor se cada elemento for colorido pela classificação que o envia, mas ...)

MPI_Alltoall funciona como combinado MPI_Scatter e MPI_Gather - o buffer de envio em cada processo é dividido como em MPI_Scatter e, em seguida, cada coluna de partes é reunida pelo respectivo processo, cuja classificação corresponde ao número da coluna de partes. MPI_Alltoall também pode ser vista como uma operação de transposição global, atuando em blocos de dados.

Existe um caso em que as duas operações são intercambiáveis? Para responder adequadamente a essa pergunta, basta analisar os tamanhos dos dados no buffer de envio e dos dados no buffer de recebimento:

operation      send buf size      recv buf size
---------      -------------      -------------
MPI_Allgather  sendcnt            n_procs * sendcnt
MPI_Alltoall   n_procs * sendcnt  n_procs * sendcnt

O tamanho do buffer de recebimento é realmente n_procs * recvcnt, mas MPI exige que o número de elementos básicos enviados seja igual ao número de elementos básicos recebidos, portanto, se o mesmo MPI for usado em enviar e receber partes de MPI_All..., então recvcnt deve ser igual a sendcnt.

É imediatamente óbvio que, para o mesmo tamanho dos dados recebidos, a quantidade de dados enviados por cada processo é diferente. Para que as duas operações sejam iguais, uma condição necessária é que os tamanhos dos buffers enviados nos dois casos sejam iguais, ou seja, n_procs * sendcnt == sendcnt, que só é possível se n_procs == 1, ou seja, se houver apenas um processo ou se sendcnt == 0, ou seja, nenhum dado está sendo enviado. Portanto, não existe um caso praticamente viável em que ambas as operações sejam realmente intercambiáveis. Mas pode-se simular MPI_Allgather com MPI_Alltoall repetindo n_procs vezes os mesmos dados no buffer de envio (como já observado por Tyler Gill). Aqui está a ação de MPI_Allgather com buffers de envio de um elemento:

rank    send buf                        recv buf
----    --------                        --------
 0      a             MPI_Allgather     a,A,#
 1      A            ---------------->  a,A,#
 2      #                               a,A,#

E aqui o mesmo implementado com MPI_Alltoall:

rank    send buf                        recv buf
----    --------                        --------
 0      a,a,a          MPI_Alltoall     a,A,#
 1      A,A,A        ---------------->  a,A,#
 2      #,#,#                           a,A,#

O inverso não é possível - não se pode simular a ação de MPI_Alltoall com MPI_Allgather no caso geral.

69
Hristo Iliev

Essas duas capturas de tela têm uma explicação rápida:

MPI_Allgatherv

MPI_Allgatherv

MPI_Alltoallv

MPI_Alltoallv

Embora essa seja uma comparação entre MPI_Allgatherv e MPI_Alltoallv, mas também explica como o MPI_Allgather difere de MPI_Alltoall.

13
Tong Zhou

Embora esses dois métodos sejam realmente muito semelhantes, parece haver uma diferença crucial entre os dois.

MPI_Allgather termina com cada processo com exatamente os mesmos dados em seu buffer de recebimento e cada processo contribui com um único valor para a matriz geral. Por exemplo, se cada um de um conjunto de processos necessário compartilhar algum valor único sobre seu estado com todos os outros, cada um forneceria seu valor único. Esses valores seriam enviados a todos, para que todos tivessem uma cópia da mesma estrutura.

MPI_Alltoall não envia os mesmos valores para o outro processo. Em vez de fornecer um valor único que deve ser compartilhado entre si, cada processo especifica um valor a ser atribuído ao outro. Em outras palavras, com n processos, cada um deve especificar n valores para compartilhar. Então, para cada processador j, seu valor de k'th será enviado para processar o índice de j'th no buffer de recebimento. Isso é útil se cada processo tiver uma mensagem única e exclusiva para o outro processo.

Como observação final, os resultados da execução de allgather e alltoall seriam os mesmos no caso em que cada processo preenchesse seu buffer de envio com o mesmo valor. A única diferença seria que o allgather provavelmente seria muito mais eficiente.

4
Tyler Gill