Otimizando estruturas de grafos em memória persistente para arquiteturas NUMA
Carregando...
Data
Autores
Orientador
Baldassin, Alexandro José 
Coorientador
Francesquini, Emilio de Camargo
Pós-graduação
Ciência da Computação - FC/FCT/IBILCE/IGCE
Curso de graduação
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Tipo
Dissertação de mestrado
Direito de acesso
Acesso aberto
Resumo
Resumo (português)
Estruturas de grafos dinâmicos desempenham papel fundamental em aplicações que demandam processamento eficiente de grandes volumes de dados conectados, como redes sociais e sistemas de recomendação. Este trabalho apresenta uma adaptação do framework DGAP para ambientes NUMA, explorando o particionamento round-robin e a afinidade explícita de threads para otimizar o processamento de grafos dinâmicos em memória persistente. Os experimentos, conduzidos com dois conjuntos de dados reais do SNAP (Orkut e LiveJournal), avaliam o impacto das características topológicas dos grafos nas otimizações propostas e demonstram ganhos expressivos, com speedup de até 2,3x em algoritmos como Connected Components, além de evidenciarem limitações em grafos de baixa densidade e em algoritmos sensíveis à latência (como BFS), indicando a necessidade de estratégias adaptativas de balanceamento em ambientes NUMA.
Resumo (inglês)
Dynamic graph structures play a key role in applications that require efficient processing of large volumes of connected data, such as social networks and recommender systems. This dissertation presents an adaptation of the DGAP framework to NUMA environments, exploring round-robin partitioning and explicit thread affinity to optimize the processing of dynamic graphs on persistent memory. Experiments conducted with two real-world datasets from SNAP (Orkut and LiveJournal) assess the impact of graph topological characteristics on the proposed optimizations and show expressive gains, with speedups of up to 2.3× in algorithms such as Connected Components, while also revealing limitations on low-density graphs and latencysensitive algorithms (e.g., BFS), indicating the need for adaptive load-balancing strategies in NUMA environments.
Descrição
Palavras-chave
Ciência da computação, Teoria dos grafos, Arquitetura de computador, Computação paralela, Sistemas de memória de computadores, Dynamic graphs, Persistent memory, NUMA, Thread affinity, Speedup
Idioma
Português
Citação
SPAGNOL, Lucas Bastelli. Otimizando estruturas de grafos em memória persistente para arquiteturas NUMA. 2025. Dissertação (Mestrado em Ciência da Computação) – Instituto de Geociências e Ciências Exatas, Universidade Estadual Paulista (UNESP), Rio Claro, 2025.
