(Como) você leva em consideração a fragmentação da memória?

Uso um exemplo da teoria dos elementos finitos, mas qualquer um que mantenha uma grande estrutura de dados e a estenda sucessivamente encontrará algo semelhante.

Suponhamos que tem uma malha não estruturada de pontos e triângulos, onde os pontos são dados pelas coordenadas (dizer e ) e os triângulos cada um constituído por três índices de pontos (digamos, , e ).$x$$y$$i$$j$$k$

Como é comum no MEF, a malha será refinada sucessivamente. Se recorrermos ao refinamento regular global, o número de triângulos aumentará pelo fator a cada iteração do refinamento. Dependendo de como isso é feito, o layout da memória se desenvolverá de maneira diferente.$4$

Digamos que a malha ocorra nas células de memória de 1 a 300, qualquer coisa além de ser livre.

Exemplo 1:

Alocamos o espaço para a nova malha, células 301 a 1501, preenchemos com os dados da malha refinada e esquecemos a antiga. A próxima malha refinada será colocada nas células 1501 a 6300, a próxima em 6301 a 21500 e assim por diante. A localização da malha atual será movida na memória "para a direita", enquanto um patch enorme não será usado. Podemos ficar sem memória prematuramente.

Pode-se observar no exemplo acima, que isso nos impedirá apenas por uma etapa de refinamento, porque mesmo sem essa fragmentação, ficaríamos sem memória total um refinamento posteriormente. Como a matriz de vértices também é levada em consideração, o problema pode se tornar mais grave.

Como isso pode ser contornado?

Exemplo 2:

Realoque a matriz do triângulo para as células 1..1200. Crie a nova malha nas células 1201 a 2400. Copie o conteúdo dessa cópia de trabalho para as células 1..1200 e esqueça a cópia de trabalho. Repita da mesma forma.

Ok, ainda ficamos sem memória prematuramente, porque precisamos de uma cópia de trabalho. Que tal agora:

Exemplo 3:

Realoque a matriz do triângulo para as células 1..1500. Copie a malha antiga para 1201 .. 1500. Crie uma nova malha nas células 1..1200. Então esqueça a cópia da malha antiga.

O caso aqui é artificial, porque não se usaria refinamento de malha global nessas escalas. Se o crescimento for muito menor, é possível realinhar a memória para evitar a fragmentação. Contudo,

Questões:

1. A fragmentação da memória se torna crítica na computação científica prática / computação de alto desempenho?

2. Se houver, como evitá-lo? Talvez meu modelo de máquina esteja errado, e o sistema operacional, por alguma mágica pesada, realinhe tacitamente a memória ou gerencie blocos fragmentados na pilha.

3. Mais específico, como isso afeta o gerenciamento da grade?

Eu discordo de Matt sobre o uso total de memória para a malha e sobre indireção extra. Para métodos explícitos, é comum um número muito pequeno de vetores (por exemplo, 2) representar todo o estado da simulação. Para um problema escalar, apenas definir as coordenadas da malha pode ser mais do que isso e, se a conectividade for explícita, será substancialmente mais. Simulações de alta resolução com métodos explícitos frequentemente precisam de um grande número de etapas, portanto é comum usar subdomínios razoavelmente pequenos apenas para poder concluir uma execução do modelo em um período razoável de tempo. Portanto, não é tão comum ficar sem memória por causa do custo de armazenamento da malha.

Um problema muito mais fundamental é o requisito de largura de banda da memória para cada etapa de um algoritmo (por exemplo, avaliar um resíduo ou tomar um passo de tempo). Para métodos não estruturados, isso envolve algumas informações baseadas em malha, mas geralmente não requer acesso a todo o armazenamento em malha. Observe que, mesmo que a memória do solver domine a memória de malha (como é comum em muitos métodos implícitos), a simulação ainda depende frequentemente dos requisitos de largura de banda de uma passagem de malha. Existem dois fatores:

Quais dados são necessários durante a passagem de malha de rotina?

Nos métodos de elementos finitos, é necessário um mapa de elemento para global. Para valores superiores à primeira ordem, isso geralmente é implementado associando graus de liberdade a entidades intermediárias, como faces e arestas, mas depois que o mapa elemento para global é construído, as entidades intermediárias não são necessárias. Em particular, a conectividade das entidades intermediárias nunca é usada diretamente por uma simulação. Essas informações podem não ser tocadas para muitas iterações de um solucionador implícito ou integrador de tempo, mas ainda são necessárias durante a adaptabilidade ou para configurar um novo espaço de função. É comum configurar o mapa elemento para global em uma matriz simples e não tocar na estrutura de dados "malha" durante esse período; nesse caso, o formato de armazenamento e a localização dos dados da malha são menos importantes.

Os métodos de volume finito requerem volumes de célula, conectividade face a célula, área de face e normais de face. Observe que as coordenadas de vértices ou a conectividade não precisam estar disponíveis. Em exemplos extremos (por exemplo, FUN3D), todas as outras informações são descartadas durante o pré-processamento offline (geração de malha) e apenas essa representação reduzida está disponível para a simulação. Isso é muito eficiente, mas impede malhas em movimento e refinamento adaptativo.

Como esses dados são dispostos na memória?

Para muitas simulações, com ordens modestas de precisão e complexidade da física, o desempenho é limitado pela largura de banda da memória. As arquiteturas modernas de CPU da IBM, Intel, AMD e NVidia suportam uma intensidade aritmética entre 4 e 8 flops / byte. Com essas unidades de ponto flutuante eficientes, devemos tentar otimizar nossos algoritmos para a largura de banda da memória. Isso pode envolver mudanças algorítmicas um tanto profundas, como favorecer os métodos de alta ordem não montados (compare as linhas "montadas" e (não montadas) de "tensor" na segunda figura), mas podemos começar tentando utilizar totalmente a largura de banda fornecida pelo hardware. Isso geralmente envolve pedidos de computação (de vértices, faces, células etc.), para que o cache seja reutilizado da melhor maneira possível. Também envolve explorar o bloqueio e ordenar incógnitas para ter metadados mínimos e ativar o número certo de fluxos de dados. (Geralmente, a simulação não estruturada em 3D termina com "muitos" fluxos, mas alguns hardwares modernos, como o POWER7, precisam de muitos fluxos para saturar a largura de banda; portanto, ocasionalmente, faz sentido organizar intencionalmente dados para ativar mais fluxos.) O trabalho PETSc-FUN3D fornece um clássico , mas ainda é uma discussão altamente relevante sobre essa otimização de desempenho para CFD implícito não estruturado.

Sugestões para o seu problema

1. Não tenha medo malloc(). Não há necessidade de compactar o refinamento atual da malha na mesma matriz que a parte inativa mais grossa da malha. Sempre que você não precisar mais de uma parte antiga da malha, apenas free()ela.

2. Após o refinamento, calcule uma boa ordem para esse nível de refinamento ( Reverse Cuthill-McKee é popular, mas também podem ser usadas mais ordens específicas do cache). Se o seu desequilíbrio de carga for razoável (menos de 10%, por exemplo), você poderá calcular essa nova ordem localmente (sem particionamento e redistribuição paralelos). O custo provavelmente será semelhante a uma única passagem de malha "física", mas pode acelerar essas travessias por um fator de 2 ou mais. Essa etapa geralmente compensa sempre que a adaptabilidade da malha não ocorre em cada"física" malha transversal. Se essa adaptabilidade frequente for necessária para o seu problema, você provavelmente fará pequenas alterações e ainda deverá reordenar ocasionalmente. Eu ainda evitaria conjuntos de memórias refinadas porque dificulta a reordenação, mas você pode usar blocos razoavelmente grandes para equilibrar o uso máximo de memória, o custo de pedidos e o custo de atualizações incrementais.

3. Dependendo da discretização, considere extrair uma representação reduzida com poucos requisitos de largura de banda de memória para os percursos "físicos". Indireção desnecessária é ruim porque aumenta os requisitos de largura de banda e, se o destino da indireção for irregular, causa reutilização incorreta do cache e inibe a pré-busca.

Em deal.II, refinamos a malha jogando fora as células antigas e substituindo-as por novas. Mas novos também são colocados nos orifícios de memória deixados pelas células excluídas. Todos os loops em todas as células são executados na ordem em que as células são encontradas na memória para manter as ocorrências de cache altas.

A questão maior é como você armazena os dados que definem as células. É claro que você poderia estruturar o Simplex {vértices de vértices [4]; int material_id; int subdomain_id; bool usado; void * user_data; };

classe Triangulação {células Simplex *; }; mas isso não é eficiente em cache, porque a maioria dos loops em todas as células toca apenas em um subconjunto dos dados armazenados na estrutura de dados do Simplex e, portanto, apenas uma fração dos dados que chegam ao cache será realmente usada. Uma estratégia melhor é fazer algo assim: class Triangulation {Vertex * vértices; int * material_ids; int * subdomínio_ids; bool * used_flags; void * * user_data; }; Como em loops em todas as células é provável que as iterações subsequentes acessem o mesmo subconjunto de dados que define as células, os caches de leitura antecipada apenas pré-carregarão os dados que você realmente usará e, consequentemente, levarão a altas taxas de acerto no cache.

1) Não. A memória do Solver supera em muito a memória da malha. Mesmo se você executar o solucionador mais leve e explícito, a malha terá no máximo 25% da memória da simulação e muito provavelmente <10%.

2) Divida sua alocação e use o pool de memória. Você não precisa alocar um pedaço contíguo para toda a malha, pois geralmente só precisa iterar sobre as peças locais. A introdução de um nível de indireção não afeta o desempenho de maneira significativa.

Se estiver ficando sem memória, basta executar mais nós para ter mais memória. Você está desperdiçando um recurso muito valioso (o cérebro humano) para resolver um problema que tem uma solução muito fácil.