Melhorando Localidade de Acesso à Memória no Método de Elementos Espectrais Através de Curvas de Preenchimento de Hilbert
Curvas de preenchimento de Hilbert, método dos elementos espectrais, propagação de ondas, processamento paralelo
A equação da onda tem uso frequente na física matemática e na engenharia, e temos de resolvê-la repetidamente para simular propagações de onda via software. O método dos elementos espectrais, uma das várias abordagens utilizadas na solução numérica da equação da onda, discretiza o domínio subjacente através de uma malha feita de elementos e nós, e percorre todos os elementos e todos os nós a cada intervalo de tempo para avançar a equação de interesse ao longo do tempo. Propomos um algoritmo de reordenação de memória, projetado para ser usado com o método dos elementos espectrais, que reorganiza informações da malha para reduzir o número de falhas de cache e incrementar a localidade de referência de dados, o que melhora o tempo de execução ao percorrer a malha. Elaboramos uma formulação do método dos elementos espectrais para ondas 2D sobre malhas não estruturadas compostas de triângulos, e associamos a ela nosso algoritmo de reordenação de memória para construir um simulador de propagação de ondas acústicas. Nossos experimentos mostram que a técnica de reordenação baseada em curvas de preenchimento de Hilbert tem bom desempenho em malhas de diversas granularidades, e também quando a variação no tamanho dos elementos é pequena ou grande. Além disso, comparamos a abordagem proposta a três outros procedimentos de reordenação de memória, e verificamos que o tempo de execução de nosso algoritmo é de 9% a 25% mais rápido do que as alternativas testadas. Recomendamos a adoção deste algoritmo de reordenação de memória em qualquer aplicação que demande percorrer domínios repetidamente.