Como o custo computacional de uma operação mpi_allgather se compara com uma operação de coleta / dispersão?

11

Estou trabalhando em um problema que pode ser paralelo usando uma única operação mpi_allgather ou uma operação mpi_scatter e uma mpi_gather. Essas operações são chamadas dentro de um loop while, portanto, podem ser chamadas várias vezes.

Na implementação com um esquema MPI_allgather, estou reunindo um vetor distribuído em todos os processos para solução de matriz duplicada. Na outra implementação, reuno o vetor distribuído em um único processador (o nó raiz), resolvo o sistema linear nesse processador e depois disperso o vetor da solução em todos os processos.

Estou curioso para saber se o custo de uma operação geral é significativamente maior do que as operações de dispersão e coleta combinadas. O comprimento da mensagem desempenha um papel significativo em sua complexidade? Isso varia entre implementações de mpi?

Editar:

Paulo
fonte
Por favor, descreva a estrutura da comunicação e os tamanhos envolvidos. Um MPI_Scatterseguido por MPI_Gathernão fornece a mesma comunicação semântica que MPI_Allgather. Talvez exista redundância quando você expressa a operação de qualquer maneira?
Jed Brown
Paul, Jed está certo, você quis dizer a MPI_Gatherseguido de a MPI_Bcast?
Aron Ahmadia 27/03
@JedBrown: eu adicionei um pouco mais de informação.
Paul
@AronAhmadia: Acho que não devo usar um MPI_Bcast porque estou enviando uma parte do vetor, para cada processo, não o vetor inteiro. Minha lógica é que uma mensagem mais curta será mais rápida de enviar do que uma mensagem maior, em geral. Isso faz sentido?
Paul
A matriz já está distribuída de forma redundante? Já é fatorado? Vários processos compartilham os mesmos caches e barramento de memória? (Isso afetaria a velocidade de resolução de sistemas redundantes.) Qual o tamanho / custo dos sistemas? Por que resolver em série?
precisa

Respostas:

9

Primeiro, a resposta exata depende de: (1) uso, isto é, argumentos de entrada de função, (2) qualidade e detalhes da implementação do MPI e (3) o hardware que você está usando. Freqüentemente, (2) e (3) estão relacionados, como quando o fornecedor de hardware otimiza o MPI para sua rede.

Em geral, a fusão de coletivos MPI é melhor para mensagens menores, pois os custos de inicialização podem não ser triviais e a sincronização causada pelo bloqueio de coletivos deve ser minimizada se houver variação no tempo de computação entre as chamadas. Para mensagens maiores, o objetivo deve ser minimizar a quantidade de dados enviados.

Por exemplo, em teoria, MPI_Reduce_scatter_blockdeve ser melhor do que o MPI_Reduceseguido MPI_Scatter, embora o primeiro seja frequentemente implementado em termos do último, de modo que não exista vantagem real. Existe uma correlação entre a qualidade da implementação e a frequência de uso na maioria das implementações do MPI, e os fornecedores obviamente otimizam as funções para as quais isso é exigido pelo contrato da máquina.

Por outro lado, se alguém está em um Blue Gene, MPI_Reduce_scatter_blockusar usando MPI_Allreduce, que faz mais comunicação do que MPI_Reducee MPI_Scattercombinado, é na verdade um pouco mais rápido. Isso é algo que eu descobri recentemente e é uma violação interessante do princípio da consistência do desempenho no MPI (esse princípio é descrito em mais detalhes em "Diretrizes de desempenho do MPI autoconsistentes " ).

No caso específico de dispersão + coletar versus reunir, considere que no primeiro, todos os dados devem ir para e de um único processo, o que o torna um gargalo, enquanto no geral, os dados podem fluir para dentro e para fora de todas as classificações imediatamente , porque todas as classificações têm alguns dados para enviar a todas as outras classificações. No entanto, o envio de dados de todos os nós de uma só vez não é necessariamente uma boa ideia em algumas redes.

Por fim, a melhor maneira de responder a essa pergunta é fazer o seguinte em seu código e responder a pergunta por experiência.

#ifdef TWO_MPI_CALLS_ARE_BETTER_THAN_ONE
  MPI_Scatter(..)
  MPI_Gather(..)
#else
  MPI_Allgather(..)
#endif

Uma opção ainda melhor é fazer com que seu código o avalie experimentalmente durante as duas primeiras iterações e use o que for mais rápido nas demais iterações:

const int use_allgather = 1;
const int use_scatter_then_gather = 2;

int algorithm = 0;
double t0 = 0.0, t1 = 0.0, dt1 = 0.0, dt2 = 0.0;

while (..)
{
    if ( (iteration==0 && algorithm==0) || algorithm==use_scatter_then_gather )
    {
        t0 = MPI_Wtime();
        MPI_Scatter(..);
        MPI_Gather(..);
        t1 = MPI_Wtime();
        dt1 = t1-t0;
    } 
    else if ( (iteration==1 && algorithm==0) || algorithm==use_allgather)
    {
        t0 = MPI_Wtime();
        MPI_Allgather(..);
        t1 = MPI_Wtime();
        dt2 = t1-t0;
    }

    if (iteration==1)
    {
       dt2<dt1 ? algorithm=use_allgather : algorithm=use_scatter_then_gather;
    }
}
Jeff
fonte
Não é uma má idéia ... cronometre os dois e determine qual deles é mais rápido.
Paul
O hardware dos ambientes HPC mais modernos otimiza muitas chamadas MPI. Às vezes, isso leva a acelerações incríveis, outras vezes, comportamentos extremamente opacos. Seja cuidadoso!
meawoppl
@ Jeff: Acabei de perceber que deixei de fora um detalhe importante ... Estou trabalhando com um cluster no Texas Advanced Computing Center, onde eles usam uma rede de topologia de árvores gordas. Isso afetaria a diferença de desempenho entre as abordagens de todos-reunir e reunir-transmissão?
Paul
A @Paul Topology não é o fator dominante aqui, mas uma árvore de gordura possui uma largura de banda de bissecção substancial, o que deve tornar o conjunto mais barato. No entanto, a coleta deve ser sempre mais barata do que o conjunto. Para mensagens maiores, no entanto, pode ser menor que um fator de 2. #
1178 Jeff Jeff
5

Jeff está absolutamente certo sobre a única maneira de ter certeza é medir - afinal somos cientistas, e esta é uma pergunta empírica - e oferece excelentes conselhos sobre como implementar essas medições. Permitam-me agora oferecer uma visão contrária (ou, talvez, complementar).

Há uma distinção a ser feita entre escrever um código para ser amplamente usado e ajustá-lo para um fim específico. Em geral, estamos fazendo o primeiro - construindo nosso código para que: a) possamos usá-lo em uma ampla variedade de plataformas eb) o código seja sustentável e extensível nos próximos anos. Mas, às vezes, estamos fazendo o outro - temos um ano de alocação em uma grande máquina e estamos aumentando o conjunto necessário de grandes simulações e precisamos de uma certa linha de base de desempenho para obter o que precisamos durante a hora da alocação concedida.

Quando estamos escrevendo código, torná-lo amplamente utilizável e sustentável é muito mais importante do que reduzir alguns por cento do tempo de execução em uma máquina específica. Nesse caso, a coisa certa a fazer é quase sempre usar a rotina que melhor descreve o que você deseja fazer - essa geralmente é a chamada mais específica que você pode fazer e fazer o que deseja. Por exemplo, se um allgather straight ou allgatherv faz o que você deseja, você deve usá-lo em vez de executar suas próprias operações dispersas / combinadas. As razões são as seguintes:

  • O código agora representa mais claramente o que você está tentando fazer, tornando-o mais compreensível para a próxima pessoa que acessá-lo no ano seguinte, sem ter idéia do que o código deve fazer (essa pessoa pode muito bem ser você);
  • As otimizações estão disponíveis no nível MPI para este caso mais específico que não está no caso mais geral, para que sua biblioteca MPI possa ajudá-lo; e
  • Tentar rolar sozinho provavelmente sairá pela culatra; mesmo que tenha um desempenho melhor na máquina X com a implementação de MPI Y.ZZ, pode ter um desempenho muito pior quando você se muda para outra máquina ou atualiza sua implementação de MPI.

Nesse caso bastante comum, se você descobrir que algum coletivo MPI funciona de maneira excessivamente lenta em sua máquina, a melhor coisa a fazer é registrar um relatório de bug com o fornecedor de MPI; você não deseja complicar seu próprio software tentando solucionar o código do aplicativo, o que deve ser corrigido corretamente no nível da biblioteca MPI.

No entanto . Se você estiver no modo "tuning" - você tem um código de trabalho, precisa escalar escalas muito grandes em um curto período de tempo (por exemplo, uma alocação de um ano) e criar um perfil de seu código e descobrimos que essa parte específica do seu código é um gargalo, faz sentido começar a executar essas afinações muito específicas. Espero que eles não sejam partes de longo prazo do seu código - idealmente, essas alterações permanecerão em algum ramo específico do projeto do seu repositório - mas você pode precisar fazer isso. Nesse caso, a codificação de duas abordagens diferentes, diferenciadas pelas diretivas de pré-processador, ou uma abordagem de "autotuning" para um padrão de comunicação específico - pode fazer muito sentido.

Portanto, não estou discordando de Jeff, só quero adicionar um contexto sobre quando você deve se preocupar o suficiente com essas questões de desempenho relativo para modificar seu código e lidar com isso.


fonte
Eu acho que eu estou mais interessado em portabilidade de otimização neste momento, mas estou sempre curioso para saber se há uma outra aplicação que é tão portátil, mas mais rápido :)
Paul