Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves

The wave equation is pervasive in mathematical physics and engineering, and we need to solve it repeatedly to simulate wave propagations in software. The spectral element method, one of several approaches for the numerical solution of the wave equation, discretizes the underlying domain in a mesh ma...

ver descrição completa

Na minha lista:

Detalhes bibliográficos
Autor principal:	Araújo, Roger Rommel Ferreira de
Outros Autores:	Souza, Samuel Xavier de
Formato:	doctoralThesis
Idioma:	pt_BR
Publicado em:	Universidade Federal do Rio Grande do Norte
Assuntos:	Curvas de preenchimento de Hilbert Método dos elementos espectrais Propagação de ondas Processamento paralelo
Endereço do item:	https://repositorio.ufrn.br/handle/123456789/45677
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	ri-123456789-45677
record_format	dspace
spelling	ri-123456789-456772022-05-02T15:31:43Z Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves Araújo, Roger Rommel Ferreira de Souza, Samuel Xavier de http://lattes.cnpq.br/2469398155033763 http://lattes.cnpq.br/9892239670106361 Araújo, João Medeiros de Okuda, Hiroshi Catabriga, Lucia http://lattes.cnpq.br/4364303980383808 Gross, Lutz Curvas de preenchimento de Hilbert Método dos elementos espectrais Propagação de ondas Processamento paralelo The wave equation is pervasive in mathematical physics and engineering, and we need to solve it repeatedly to simulate wave propagations in software. The spectral element method, one of several approaches for the numerical solution of the wave equation, discretizes the underlying domain in a mesh made of elements and nodes, and traverses every element and every node at each time step as it marches the target equation through time. We propose a memory reordering algorithm, meant to be used with the spectral element method, that rearranges mesh-related data to reduce the number of cache misses and boost locality of data reference, thereby improving the execution speed of the mesh traversal process. We devise a spectral element method formulation for 2D waves over unstructured meshes made of triangles, and we pair it to our memory reordering algorithm to construct an acoustic wave propagation simulator. Our experiments show that the reordering technique based on Hilbert space-filling curves performs well in meshes of different granularities, and also when the variation in element sizes is either small or large. In addition, we compare the proposed approach with three other memory reordering schemes, and find that our algorithm runs between 9% and 25% faster than the alternatives we tested. We recommend this memory reordering algorithm to any application that requires successive traversals across domains. 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. 2022-01-18T23:31:35Z 2022-01-18T23:31:35Z 2021-10-07 doctoralThesis ARAÚJO, Roger Rommel Ferreira de. Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves. 2021. 103f. Tese (Doutorado em Engenharia Elétrica e de Computação) - Centro de Tecnologia, Universidade Federal do Rio Grande do Norte, Natal, 2021. https://repositorio.ufrn.br/handle/123456789/45677 pt_BR Acesso Aberto application/pdf Universidade Federal do Rio Grande do Norte Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO
institution	Repositório Institucional
collection	RI - UFRN
language	pt_BR
topic	Curvas de preenchimento de Hilbert Método dos elementos espectrais Propagação de ondas Processamento paralelo
spellingShingle	Curvas de preenchimento de Hilbert Método dos elementos espectrais Propagação de ondas Processamento paralelo Araújo, Roger Rommel Ferreira de Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves
description	The wave equation is pervasive in mathematical physics and engineering, and we need to solve it repeatedly to simulate wave propagations in software. The spectral element method, one of several approaches for the numerical solution of the wave equation, discretizes the underlying domain in a mesh made of elements and nodes, and traverses every element and every node at each time step as it marches the target equation through time. We propose a memory reordering algorithm, meant to be used with the spectral element method, that rearranges mesh-related data to reduce the number of cache misses and boost locality of data reference, thereby improving the execution speed of the mesh traversal process. We devise a spectral element method formulation for 2D waves over unstructured meshes made of triangles, and we pair it to our memory reordering algorithm to construct an acoustic wave propagation simulator. Our experiments show that the reordering technique based on Hilbert space-filling curves performs well in meshes of different granularities, and also when the variation in element sizes is either small or large. In addition, we compare the proposed approach with three other memory reordering schemes, and find that our algorithm runs between 9% and 25% faster than the alternatives we tested. We recommend this memory reordering algorithm to any application that requires successive traversals across domains.
author2	Souza, Samuel Xavier de
author_facet	Souza, Samuel Xavier de Araújo, Roger Rommel Ferreira de
format	doctoralThesis
author	Araújo, Roger Rommel Ferreira de
author_sort	Araújo, Roger Rommel Ferreira de
title	Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves
title_short	Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves
title_full	Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves
title_fullStr	Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves
title_full_unstemmed	Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves
title_sort	boosting memory access locality of the spectral element method with hilbert space-filling curves
publisher	Universidade Federal do Rio Grande do Norte
publishDate	2022
url	https://repositorio.ufrn.br/handle/123456789/45677
work_keys_str_mv	AT araujorogerrommelferreirade boostingmemoryaccesslocalityofthespectralelementmethodwithhilbertspacefillingcurves
_version_	1773962134953132032

Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves

Registros relacionados