O MPS é um método numérico de natureza lagrangiana para aplicação em problemas de escoamento de fluidos incompressíveis. O MPS teve origem em trabalhos pioneiros de Koshizuka e Oka [35][36].
O foco inicial dos autores foi o aperfeiçoamento do método original, visando resolver problemas de estabilidade numérica e a aplicabilidade do modelo a fenômenos físicos mais complexos, ainda assim, já neste período de consolidação do método tiveram início os esforços para melhorar seu desempenho computacional.
Em 1996, Koshizuka et al. [35] desenvolveram modelos para os operadores gradiente e laplaciano, além de um modelo para o tratamento de superfície livre. Os autores apresentaram, também, resultados de testes para aperfeiçoamento dos valores para o coeficiente de superfície livre e para o raio de vizinhança.
Em 1998, Koshizuka et al. [36] aplicaram o método MPS à simulação de ondas geradas e quebradas em uma praia. Até aquele momento, não havia simulação em três dimensões com o método MPS, pois o atrito artificial devido ao movimento desordenado das partículas introduzia erros na simulação. Os autores apresentaram, também, uma otimização para o cálculo da vizinhança que reduzia o tempo de processamento de para , onde é o número de partículas.
Nos anos seguintes, com as bases do método melhor estabelecidas e com o aumento do interesse por simulações 3D, de maior custo computacional, aumentou o interesse de pesquisas focadas principalmente no aumento da escalabilidade e melhora do desempenho computacional do método, através do aperfeiçoamento de algoritmos existentes e a introdução de algoritmos paralelizados.
Em 1999, Vertanen [37] desenvolveu uma implementação paralelizada para o método SPH. Da perspectiva atual trata-se de implementação bastante limitada, usando somente modelos 2D com alguns milhares de partículas. No entanto, o autor além de inovar na metodologia de desenvolvimento, utilizando-se de modelagem
orientada a objetos, descreve de forma muito instrutiva suas dificuldades em transformar uma solução inicialmente serial em uma versão paralelizada. O autor relata como certas dificuldades enfrentadas no desenvolvimento paralelizado não têm similar no desenvolvimento serial, com destaque para a identificação de erros. De particular interesse foi um fenômeno que a versão paralelizada apresentava após alguns milhares de passos de simulação: o surgimento e proliferação aleatórios de “buracos” no interior do fluído. A investigação deste problema, segundo o autor, resultou na implementação de diversas ferramentas essenciais para monitoração de detalhes da simulação e mostrou a importância da execução de testes de longa duração desde os estágios iniciais do desenvolvimento.
Em 2003, Premože et al. [9] apresentou os resultados de simulações realizadas pelo método MPS utilizando recursos gráficos mais avançados. Os autores concluíram que o gargalo das simulações é a solução da equação de Poisson de pressão e sugeriram que este problema poderia ser contornado paralelizando-se a solução da equação. Além disso, concluíram que o uso de esquemas de interpolação mais sofisticado poderia melhorar a precisão dos resultados.
Em 2004, Yao et al. [23] utilizaram um lista encadeada de células para representação da vizinhança das partículas e conseguiram reduzir o tempo de cálculo da vizinhança para , onde é número de partículas.
Em 2006, Tsukamoto[11] utilizou paralelização em memória compartilhada, como forma de acelerar o método MPS, para realizar a simulação de corpos flutuantes em ondas altamente não lineares, obtendo-se ganhos significativos de desempenho em relação à versão serial.
Ainda em 2006, Shibata e Koshizuka [38] simularam, em três dimensões, o impacto de água marítima em um convés utilizando o método MPS. A pressão de impacto da água no convés foi determinada e comparada com os resultados experimentais obtidos por um modelo bidimensional. O movimento do fluido, a elevação da superfície e a pressão de impacto da água no deck estavam de acordo com os resultados experimentais. Neste trabalho os autores verificaram a necessidade de desenvolvimento de novas técnicas para a aceleração da determinação da vizinhança, pois o modelo tridimensional era composto por 328.452 partículas.
Utilizando uma estratégia de divisão estática do domínio do problema, os autores conseguiram realizar a busca de vizinhanças com tempo de processamento de , onde é número de partículas.
Em 2008, Ikari e Gotoh [32] comparam dois métodos de decomposição do problema: decomposição baseada nas partículas (particles decomposition) e decomposição do domínio (domain decomposition) e verificaram que a aplicação com decomposição de domínio tende a executar os cálculos em menos tempo que a aplicação utilizando decomposição por partículas.
Em 2009, Gotoh [33] desenvolveu uma versão do MPS para execução paralelizada, denominada 3D CMPS-HS, combinando técnicas de decomposição de domínio com fronteiras dinâmicas, recalculadas periodicamente com base no centro de massa de cada subdomínio, para melhorar o balanceamento de carga nos processadores e um processo de reestruturação da matriz de pré-condicionador para realização do processo de forward/backward do método de Conjugate Gradient em paralelo. Neste trabalho foram comparados os resultados de desempenho de dois métodos para solução do sistema de equações lineares: PICCG-RP (Parallelized Incomplete Cholesky Conjugate Gradientwith Renumbering Process) e SCG (Scaled Conjugate Gradient). Os autores concluíram que a versão 3D CMPS-HS foi capaz de simular satisfatoriamente os modelos estudados, mas que ainda seriam necessários diversos aperfeiçoamentos ao modelo paralelizado: melhorar a precisão e eficiência computacional, através do desenvolvimento e aplicação de esquemas numéricos mais precisos e consistentes para os modelos de operador diferencial, bem como para a integração do tempo; melhorar o desempenho através do uso de solucionadores (solvers 2 ) mais apropriados e rápidos e de estratégias de
decomposições de domínio dinâmico mais eficiente tanto para problemas 2D quanto 3D.
2 O termo inglês solver, que pode ser traduzido com solucionador, é comumente usado em computação numérica para designar uma implementação computacional de algoritmo para solução de sistemas de equações lineares. Para maior concisão deste texto, o termo solver será utilizado com esta conotação.
Em 2010, Iribe et al. [27] apresentaram resultados da simulação do MPS paralelizado para um cluster de PC’s. Neste trabalho eles identificaram que o gargalo da paralelização do solver iterativo em memória distribuída é o custo computacional da comunicação entre os subdomínios. Para minimizar a comunicação os autores testaram um sofisticado processo de renumeração das partículas baseado em “pacotes” e no uso de uma lista de comunicação. Com estas técnicas conseguiram aumentar a velocidade de comunicação e realizaram uma simulação de tsunami com seis milhões de partículas em 237 horas. Os autores desenvolveram um processo eficiente de rotulagem das partículas baseado em um algoritmo de células ligadas, para reduzir o tempo de computação para uma simulação de dinâmica molecular por um fator de três. Eles mostraram que a melhoria do desempenho deve-se ao cumprimento eficiente de ambos os princípios localidade espacial e temporal, resultado da proximidade dos rótulos associados aos átomos que interagem. Finalmente, eles mostraram que o procedimento de reordenação apresentado pode ser usado para elaborar um eficiente esquema de decomposição unidimensional para processamento.
O histórico dos esforços em melhorar a escalabilidade e o desempenho do MPS mostra a importância e a complexidade desta tarefa. Em linhas gerais, as soluções analisadas se baseiam em duas estratégias básicas: a decomposição dinâmica do domínio e a utilização de solver iterativo. A primeira como forma de preservar o balanceamento de carga e a segunda devido a limitações de escalabilidade dos métodos diretos para solução de sistemas lineares.
A paralelização do MPS tem evoluído gradualmente através da combinação de algoritmos não numéricos cada vez mais sofisticados para o gerenciamento da configuração dinâmica dos domínios (construção da vizinhança das partículas, sincronização das fronteiras, etc.), minimização da comunicação na solução do sistema de equações lineares e reorganização da matriz de coeficientes de interação.
Nos trabalhos analisados as diferentes estratégias implementadas combinam, em grau variado, a soluções do problema de modelagem física / geométrica da decomposição do domínio do modelo com o problema matemático da solução de
sistemas lineares, resultando em soluções computacionais com unidades fortemente interligadas. Em soluções com esta característica o ganho em desempenho é em geral associado a um custo muito alto no tempo de desenvolvimento.
Para simulação de fluxo de fluídos por métodos numéricos com malhas, cuja história de desenvolvimento remonta à década de 1960, as estratégias básicas da modelagem computacional dos problemas numéricos estão mais bem estabelecidas e, com isto, muitos projetos de software tem focado a formulação de soluções mais gerais e flexíveis. O emprego de técnicas modernas de engenharia de software a estes problemas, para identificação das características matemáticas do modelo relevantes à solução computacional paralelizada, e a abstração dos objetos computacionais, tem resultado em soluções flexíveis e expansíveis [39] [40] [41]. No desenvolvimento do framework de paralelização do simulador MPS utilizou-se destas técnicas para combinar algumas das estratégias mais bem sucedidas da abordagem usual de paralelização do MPS.