Quais são as vantagens e desvantagens dos algoritmos de decomposição de partículas e paralelismo de decomposição de domínio?

Estou executando simulações de dinâmica molecular (MD) usando vários pacotes de software, como Gromacs e DL_POLY.

O Gromacs agora suporta os algoritmos de decomposição de partículas e de domínio. Por padrão, as simulações do Gromacs usam a decomposição de domínio, embora por muitos anos, até recentemente, a decomposição de partículas fosse o único método implementado no Gromacs. Em um dos trabalhos de Gromacs (DOI 10.1002 / jcc.20291), os autores dão uma razão para sua escolha inicial de decomposição de partículas:

"Uma decisão inicial do projeto foi a escolha de trabalhar com a decomposição de partículas em vez da decomposição de domínio para distribuir o trabalho pelos processadores. No último caso, os domínios espaciais são atribuídos aos processadores, o que permite encontrar vizinhos espaciais rapidamente apenas pela comunicação local, mas complicações devido as partículas que se movem sobre os limites espaciais são consideráveis. A decomposição de domínio é uma escolha melhor apenas quando o tamanho do sistema linear excede consideravelmente o intervalo de interação, o que raramente é o caso na dinâmica molecular. Com a decomposição de partículas, cada processador calcula as forças e atualiza as coordenadas / velocidades para uma fração atribuída das partículas, usando uma lista de vizinhos pré-computada distribuída uniformemente pelos processadores. resultantes da interacção entre as partículas par i e j , o qual é necessário para a actualização da velocidade de ambas as partículas i e $F_{ij}$$i$$j$$i$$j$, é calculado apenas uma vez e comunicado a outros processadores. Todo processador mantém em sua memória local o conjunto completo de coordenadas do sistema, em vez de restringir o armazenamento às coordenadas necessárias. Isso é mais simples e economiza sobrecarga de comunicação, enquanto a reivindicação de memória geralmente não é um fator limitante, mesmo para milhões de partículas. A lista de vizinhos, por outro lado, que pode conter até 1000 vezes o número de partículas, é distribuída pelos processadores. A comunicação é essencialmente restrita ao envio de coordenadas e forças uma vez por vez, em torno do anel do processador. Essas opções provaram ser robustas ao longo do tempo e facilmente aplicáveis ​​aos modernos clusters de processadores ".

O que eles querem dizer com "tamanho do sistema linear" na frase "A decomposição de domínio é uma escolha melhor apenas quando o tamanho do sistema linear excede consideravelmente o intervalo de interação, o que raramente acontece na dinâmica molecular"? A partir do parágrafo acima, entendo que a decomposição de partículas tem a vantagem de que não é necessário lidar com partículas que se movem através dos limites do domínio; em vez disso, você só precisa ter memória suficiente para cada processador para armazenar a configuração total do sistema. Portanto, a decomposição de partículas parece muito favorável, enquanto a decomposição de domínio parece muito desfavorável.

Tenho certeza de que essa é uma pergunta muito complicada (e provavelmente o assunto de muitos livros), mas basicamente, se a decomposição de partículas parece tão favorável, por que alguém precisaria usar a decomposição de domínio? A decomposição do domínio é apenas favorável se o tamanho do sistema for muito grande (tornando difícil ou impossível armazenar a configuração total em cada processador)? Com base no parágrafo citado acima, não sei por que a decomposição de domínio é agora, apenas recentemente, o algoritmo de paralelização padrão no Gromacs.

Parece que o DL_POLY agora (versão 4) também usa decomposição de domínio. No manual da versão 4:

"A divisão dos dados de conguração dessa maneira é baseada na localização dos átomos na célula de simulação, uma alocação geométrica de dados do sistema é a marca registrada dos algoritmos DD. Observe que, para que essa estratégia funcione com eficiência, a simulação O sistema deve possuir uma densidade razoavelmente uniforme, de modo que cada processador seja alocado quase uma porção igual de dados de átomos (tanto quanto possível). Com essa abordagem, a computação de forças e a integração das equações de movimento são compartilhadas (razoavelmente) igualmente entre processadores e em grande parte, pode ser calculado independentemente em cada processador.O método é conceitualmente simples, porém difícil de programar e é particularmente adequado para simulações em larga escala, nas quais a eficiência é mais alta.

...

No caso da estratégia DD, o algoritmo SHAKE (RATTLE) é mais simples que no método Replicated Data do DL_POLY Classic), onde são necessárias atualizações globais das posições do átomo (mesclagem e junção). "

Isso faz parecer que a decomposição do domínio é boa porque pode ser mais eficiente, mesmo que talvez seja mais difícil de implementar.

Por outro lado, uma versão anterior (DL_POLY Classic) usava paralelização de dados replicados, que parece ser outro nome para decomposição de partículas. No manual dessa versão:

$\textbf{r}_i$$\textbf{v}_i$$\textbf{f}_i$$N$átomos no sistema simulado, são reproduzidos em todos os nós de processamento). Nesta estratégia, a maioria das forças de computação e integração das equações de movimento pode ser compartilhada facilmente e igualmente entre nós e, em grande parte, ser processada independentemente em cada nó. O método é relativamente simples de programar e é razoavelmente eficiente. Além disso, pode ser "recolhido" para rodar em um único processador com muita facilidade. No entanto, a estratégia pode ser cara na memória e ter altos custos de comunicação, mas, no geral, provou ser bem-sucedida em uma ampla gama de aplicativos.

Este parágrafo geralmente parece consistente com o primeiro parágrafo desta questão, exceto pelo fato de dizer que a decomposição de dados / partículas replicadas possui "altos custos indiretos de comunicação". O parágrafo do documento Gromacs parece dizer o contrário - que a decomposição de partículas é preferível porque possui menor sobrecarga de comunicação do que a decomposição de domínio.

Você tem alguma ideia?

A decomposição de partículas e domínios está diretamente conectada aos dois métodos principais de acelerar cálculos de força para sistemas com interações de alcance limitado - listas de vizinhos Verlet e listas de células. Se você quiser entrar em detalhes, há um belo livro de Allen e Tildesley, chamado Computer Simulation of Liquids , considerado por muitos como a "bíblia" dos estudos de Dinâmica Molecular e Monte Carlo. Depois, há a Simulação Numérica em Dinâmica Molecular de Griebel, Knapek e Zumbusch, que se aprofunda nas várias técnicas para implementação paralela de MD.

$O(N^2)$$O(N)$

$O(N)$$O(N)$ $N$Escala melhor. Daí o argumento do tamanho linear. O método de decomposição de domínio é uma extensão direta do método de listas vinculadas a células - as células são divididas entre diferentes CPUs.

O problema com a decomposição do domínio é que ele precisa se comunicar quando as partículas se movem de uma célula para outra que é tratada por outra CPU. Isso pode se tornar problemático em temperaturas de simulação mais altas, onde as partículas tendem a se afastar mais do que sua posição de equilíbrio ou quando há um fluxo de partículas. Também as informações das células na borda do domínio devem ser transferidas em cada iteração para os domínios vizinhos. Mas tudo isso é comunicação localmente síncrona e pode ser feita com muita eficiência.

Os dados replicados são a abordagem mais fácil, mas infelizmente exigem que a cada passo todas as informações de posição e velocidade sejam sincronizadas globalmente. Isso realmente não escala bem e, para um sistema muito grande, a quantidade global de memória é o tamanho da estrutura de dados vezes o número de CPUs usadas, enquanto um dos objetivos do processamento paralelo é a distribuição de dados, de modo que cada CPU tenha menos do que a quantidade global de dados.

Em resumo, não existe um método "tamanho único", adequado para todos os sistemas que estão sendo simulados. Na maioria das vezes, a melhor estratégia de paralelização pode ser deduzida da geometria do sistema e o código MD apropriado para esse caso pode ser escolhido - todos eles implementam mais ou menos os mesmos campos de força e integradores subjacentes.

Por "A decomposição do domínio é uma escolha melhor apenas quando o tamanho do sistema linear excede consideravelmente o intervalo de interação, o que raramente é o caso na dinâmica molecular", os autores desse (muito antigo) artigo do GROMACS significam que, se o tamanho espacial da lista de vizinhos for da ordem de 1 nm, e a célula de simulação é de apenas vários nanômetros, então a sobrecarga da decomposição do domínio é muito alta. Você também pode aceitar uma distribuição de informações de todos para todos na decomposição de partículas e não precisa gastar tempo com toda a contabilidade para decomposição de domínio.

O problema com a decomposição de partículas implementado pelo GROMACS foi que, com o tempo, as partículas atribuídas a cada processador se difundem no espaço. Como a responsabilidade de calcular cada interação foi fixada por sua localização inicial, a difusão aumentou gradualmente o volume do espaço total que cada processador precisava conhecer para criar sua lista de vizinhos, mesmo que o cálculo total descrito pela lista de vizinhos fosse constante. Na prática, você reiniciaria periodicamente a simulação para redefinir a localidade de dados e comunicação.

Sua suposição de que "a decomposição de partículas tem a vantagem de que não é necessário lidar com partículas que se movem através dos limites do domínio" não se aplica se a difusão for significativa ao longo da escala de tempo da simulação.

A decomposição de domínio lida com isso "antecipadamente", migrando a responsabilidade pela interação junto com a difusão, melhorando a localização dos dados em cada processador e minimizando o volume de comunicação.

Isenção de responsabilidade: eu ajudo a desenvolver o GROMACS e provavelmente rasgarei a implementação da decomposição de partículas na próxima semana ;-)

Gostaria de acrescentar a resposta de Hristo Iliev. Enquanto seu post fala principalmente sobre a complexidade computacional , quando se trata de paralelismo, a complexidade da comunicação é pelo menos tão importante - e é o principal motivo da decomposição do domínio.

Máquinas paralelas modernas geralmente têm algum tipo de topologia no toro. Isso significa que cada CPU possui um número de CPUs "vizinhas" com as quais pode se comunicar muito rapidamente. Comunicar-se com uma CPU que não é vizinha é mais caro. Portanto, é sempre favorável ter um algoritmo que só precisa se comunicar com as CPUs vizinhas.

Ao usar uma decomposição de partículas, os parceiros de interação de uma partícula são distribuídos aleatoriamente em todas as outras CPUs. Para poder calcular as interações, ele precisa conhecer as coordenadas de todos os parceiros, portanto, precisa se comunicar com$P$$\mathcal{O}(P^2)$

$P$$\mathcal{O}(P)$

$\mathcal{O}(P)$

Observe, no entanto, que sistemas não uniformes não são tão comuns quanto parece, eles ocorrem apenas ao simular algo no vácuo ou ao usar um solvente implícito. As densidades de cristais e líquidos são próximas o suficiente para executar a decomposição do domínio.