Scalable Multilevel Monte Carlo Methods Exploiting Parallel Redistribution on Coarse Levels

Resumo Técnico: Métodos de Monte Carlo Multinível Escaláveis Explorando a Redistribuição Paralela em Níveis Coarsos

Definição do Problema
Em ambientes paralelos distribuídos, métodos de Multigrid Algébrico (AMG) baseados em agregação — especificamente o AMG baseado em elementos (AMGe) — enfrentam um gargalo de escalabilidade quando o número de agregados grosseiros (elementos) torna-se menor que o número de núcleos computacionais disponíveis. Em implementações padrão, uma vez que o número de agregados cai abaixo da contagem de núcleos, o refinamento adicional é frequentemente interrompido ou torna-se ineficiente porque os dados devem ser agregados através das fronteiras dos núcleos, levando a sobrecarga de comunicação ou núcleos ociosos. Essa limitação restringe a profundidade da hierarquia multinível.

No contexto de simulações de Monte Carlo Multinível (MLMC) para equações diferenciais parciais (PDEs) estocásticas, como a equação de Darcy com permeabilidade incerta, uma hierarquia profunda é crucial. Resultados teóricos indicam que a adição de níveis mais grosseiros reduz a variância das correções do nível fino, diminuindo assim o número de simulações caras no nível fino necessárias para atingir um erro quadrático médio (MSE) alvo. No entanto, se o solver não conseguir escalar eficientamente nesses níveis mais grosseiros (devido ao descompasso entre núcleo e agregado), o potencial de economia computacional do MLMC não é totalmente realizado.

Metodologia
O artigo propõe uma estratégia para estender o processo de coalescência além do número de núcleos disponíveis, implementando um mecanismo de redistribuição de dados paralela em níveis grosseiros. A metodologia é construída sobre os seguintes componentes:

1. Aglomeração de Elementos (AMGe): O método utiliza aglomeração de elementos não estruturados para gerar espaços grosseiros. Esses espaços grosseiros são construídos para conter polinômios de ordem igual à do nível fino, garantindo que possuam propriedades de aproximação comparáveis aos espaços do nível fino. Isso é essencial para a estabilidade e convergência dos solvers de MLMC e de PDEs não lineares.
2. Redistribuição Paralela via Operações Matriciais: A inovação central é um algoritmo de redistribuição formulado inteiramente através de operações de matriz esparsa paralelas.
   • Redistribuição de Topologia: O algoritmo constrói relações entre "núcleos" e "elementos" (ex: núcleo elemento, elemento elemento). Ele agrega núcleos ativos em um conjunto menor de "super-núcleos" (ou Cores) usando um particionador de grafos na relação núcleo núcleo. Os elementos são então redistribuídos para esses novos núcleos com base na topologia do elemento aglomerado (AE), garantindo que cada AE permaneça fisicamente conectado dentro de um único núcleo.
   • Redistribuição de Dados: Uma vez que a topologia é redistribuída, os graus de liberdade (dofs) e as matrizes dos elementos são realocados. O método utiliza matrizes booleanas esparsas (ex: dof truedof, element dof) para mapear os dofs do nível fino para os "novos_dofs" atribuídos à nova configuração de núcleos. As matrizes globais são atualizadas via produtos como $P^T A_{diag} P$, onde $P$ representa o mapeamento de redistribuição.
3. Integração com MLMC: A hierarquia AMGe redistribuída é integrada em uma estrutura MLMC. O método emprega um amostrador de PDE escalável para gerar realizações do campo de permeabilidade estocástica. O estimador MLMC utiliza uma soma telescópica de expectativas através dos níveis, com o número de amostras por nível otimizado com base na variância das diferenças de nível e no custo computacional por amostra.

Principais Contribuições

• Distribuição de Dados Independente de Nível: O artigo demonstra um método para desacoplar o número de núcleos usados nos níveis grosseiros do número de núcleos usados no nível mais fino. Isso permite que a hierarquia seja coalescida arbitrariamente profunda, limitada apenas pelo número total de elementos, e não pelo número de processadores.
• Preservação das Propriedades de Aproximação: A estratégia de redistribuição mantém a ordem de aproximação dos espaços grosseiros. Ao garantir que os elementos grosseiros sejam uniões de elementos finos e que as matrizes de interpolação sejam construídas de forma conforme, o método retém as garantias teóricas necessárias para a convergência do MLMC.
• Extensão de Escalabilidade: A abordagem permite o uso de níveis grosseiros adicionais em hierarquias MLMC. Como hierarquias mais profundas reduzem a variância das correções do nível fino, isso se traduz diretamente em uma redução no número total de resoluções de grade fina necessárias.
• Implementação via Álgebra Linear Esparsa: A redistribuição é implementada usando operações padrão de matriz esparsa paralela, tornando-a compatível com bibliotecas de computação de alto desempenho (HPC) existentes e evitando a necessidade de padrões de comunicação customizados complexos.

Resultos
Os autores realizaram experimentos numéricos resolvendo a equação de Darcy com um campo de permeabilidade log-normal utilizando os pacotes de software Parelag e MFEM no cluster Quartz, no Lawrence Livermore National Laboratory.

• Escalabilidade de Solves Diretos: A análise de escalabilidade fraca mostrou que, embora a redistribuição aumente o tamanho do problema local nos níveis grosseiros (levando a um ligeiro aumento no tempo de execução por amostra para esses níveis específicos), ela melhora significamente a eficiência de escalonamento. Por exemplo, nos níveis mais grosseiros de um problema de 512 núcleos, a eficiência de escalabilidade fraca melhorou de 20% (sem redistribuição) para 40% (com redistribuição).
• Redução de Custo de MLMC: A métrica primária de sucesso foi o tempo total de CPU necessário para atingir um MSE alvo ($\epsilon^2$).
  • Ao incorporar níveis grosseiros adicionais (até 8 níveis em comparação com os 6 padrão), o método de redistribuição permitiu um melhor equilíbrio de trabalho computacional através da hierarquia.
  • O custo era dominado pelos níveis mais grosseiros no MLMC padrão (devido ao baixo escalonamento), mas a redistribuição equilibrou esse custo, reduzindo o custo do nível mais grosseiro por um fator de aproximadamente 10.
  • Acelerações (Speed-ups): O estudo relatou acelerações de tempo de CPU total de 1.8x, 1.6x e 2.8x para tamanhos de problemas utilizando 8, 64 e 512 núcleos, respectivamente, ao usar a redistribuição em comparação com a abordagem padrão não redistribuída.
• Custo Offline vs. Online: A construção da hierarquia AMGe com redistribuição acarretou um aumento negligenciável no tempo de execução offline (tipicamente menos de 5 segundos), o qual é compensado pela redução significativa no tempo de simulação online.

Significância e Alegações
O artigo alega que a capacidade de coalescer além do número de núcleos disponíveis é um fator chave para alcançar a escalabilidade para métodos MLMC. Os autores enfatizam que, embora o foco seja o paralelismo de resoluções individuais de PDE via redistribuição dependente de nível, o trabalho não aborda outras formas de paralelismo em MLMC (como o agendamento de simulações independentes entre núcleos).

A significância deste trabalho reside na demonstração de que a redistribuição dependente de nível permite que os solvers MLMC explorem hierarquias mais profundas sem sacrificar a qualidade da aproximação. Isso resulta em uma redução substancial no custo computacional total (tempo de CPU) para simulações estocásticas. Os autores observam que, à medida que os problemas avançam para a computação de "escala extrema", os benefícios desta redistribuição de nível grosseiro devem se tornar ainda mais pronunciados. O artigo conclui que esta abordagem é um método prático e eficaz para melhorar a eficiência de solvers multinível para PDEs não lineares e simulações estocásticas.