Galerkin descontínuo é realmente mais paralelizável que Galerkin contínuo?

Sempre ouvi dizer que a fácil paralelização era uma das vantagens dos métodos DG, mas não vejo realmente por que nenhuma dessas razões também se aplica ao Galerkin contínuo.

Uma razão pela qual os métodos DG podem receber mais atenção como um método paralelo é que é facilmente visto que o método é inerentemente local para um elemento. O acoplamento nos métodos DG é fraco, pois ocorre apenas através de arestas adjacentes (ou faces em 3d). Portanto, para triângulos ou quads, a DG se comunicará com três ou quatro processadores, no máximo, respectivamente. Enquanto os métodos de CG incluem cantos de elementos, a valência do canto de um elemento se torna importante. Dependendo do gerador de malha usado, essa valência pode ser de oito processadores (possivelmente mais altos). Portanto, o custo de montagem da derivada de tempo pode ser considerado "mais alto" para os métodos de CG. Isso é particularmente preocupante para métodos espectrais, onde o volume de informações a serem comunicadas pode ser bastante grande (e a ocultação de latência pode se tornar mais difícil à medida que o tamanho de cada partição diminui).

Mas esse custo extra para o CG montar sua derivada de tempo pode ser compensado por uma estratégia de balanceamento de carga diferente. Diferentes estratégias de particionamento de malha (eu sou mais familiarizado com o METIS) permitem ao usuário equilibrar a carga através de várias métricas, por exemplo, garantindo que cada partição tenha aproximadamente o mesmo número de elementos ou limitando a quantidade de comunicação entre as partições. Sinto que um motivo pelo qual o coloquisium da DG seja prontamente paralelelizável é que uma divisão ingênua do problema em partes iguais pode fornecer uma implementação paralela muito eficiente, apresentando uma aceleração super linear em certos casos devido a efeitos de cache (veja, por exemplo, Baggag et al. . ou Altmann et. al.) Enquanto o CG pode exigir um método de particionamento mais inteligente. Portanto, pode ser que a mudança de discretizações espaciais de DG para CG exija que se reconsidere também como dividir a malha em subproblemas.

Dos meus muitos anos escrevendo software FEM, acredito que a afirmação de que os esquemas de DG sejam mais adequados à paralelização do que os esquemas de CG é apócrifa. É freqüentemente usado na introdução de documentos da DG como justificativa para os métodos da DG, mas nunca o vi substanciado com uma referência que realmente investigou a questão. É semelhante a toda proposta da NSF em um projeto de teoria dos números que faz referência à "criptografia" como uma área de impacto mais amplo, uma afirmação de que nessa generalidade também nunca é substanciada.

De fato, acredito que, com a única exceção de esquemas explícitos de escalonamento no tempo e, possivelmente, problemas nos quais você precisa inverter uma matriz de massa, os esquemas de DG não são melhores nem piores que os esquemas de CG se alguém investigar o custo da comunicação envolvido. Quero dizer que isso é prático: claro, talvez seja necessário comunicar menos dados, mas eu imagino que a diferença no tempo do relógio de parede seja desprezível para todos os outros programas de operações nesses dados.

Claro, eu ficaria encantado se alguém aceitasse o desafio de me provar que estava errado!

Assim como acontece com a maioria das declarações gerais sobre esquemas numéricos, a resposta depende das circunstâncias exatas que você está observando. Antes de mais, as vantagens da DG no que respeita à paralelização compensam principalmente no caso de esquemas explícitos de integração do tempo devido a

• A matriz de massa local da célula dos esquemas de DG (para que você não precise aplicar o inverso da matriz de massa globalmente)
• Uma proporção favorável de trabalho local da CPU (integrais de volume) para trabalho relacionado à comunicação (integrais de borda), especialmente para pedidos mais altos

Embora essas instruções se apliquem a discretizações genéricas de DG, aplicativos HPC reais (por exemplo, usando vários milhares de processadores) exigem um pouco mais de esforço em relação à estratégia de paralelização, a fim de manter uma boa escala. Este artigo mostra, por exemplo, como é possível obter um dimensionamento quase perfeito de até uma célula por processador . Isso certamente é algo que você não pode esperar de um MEF contínuo, mas, como mencionado anteriormente, esquemas implícitos são algo totalmente diferente.

Ao montar uma matriz de rigidez, os dados armazenados em um elemento no FEM contínuo (nodal) devem ser comunicados a todos os seus vizinhos nodais. Por outro lado, o DGFEM exige que os dados do elemento sejam comunicados a todos os seus vizinhos. Em vizinhos nodais e de face 1D são idênticos, mas em 3D a diferença pode ser bastante grande: para uma malha hexaédrica comum, existem 26 vizinhos nodais, mas apenas 6 vizinhos de face. Para malhas irregulares com muitos vértices de alta valência, a situação piora para o CG, enquanto permanece o mesmo para o DG.

O DG para PDE hiperbólico pode ser usado como um substituto para esquemas de volumes finitos. Em volume finito e em diferença finita, quando você aumenta a ordem do esquema, seu estêncil aumenta. Isso dificulta a paralelização, pois para cada ordem de esquema, você tem estêncil diferente. Nos limites da partição, você deve garantir que todas as células necessárias da partição vizinha para a ordem específica do esquema estejam disponíveis. Porém, com a DG, não importa qual seja a ordem do esquema, cada célula se comunica apenas com seus vizinhos. Então, comparado entre volume / diferença finita e DG, pode-se dizer que a DG é mais fácil de paralelizar.