Otimizando estruturas de grafos em memória persistente para arquiteturas NUMA
Loading...
Date
Authors
Advisor
Baldassin, Alexandro José 
Coadvisor
Francesquini, Emilio de Camargo
Graduate program
Ciência da Computação - FC/FCT/IBILCE/IGCE
Undergraduate course
Journal Title
Journal ISSN
Volume Title
Publisher
Universidade Estadual Paulista (Unesp)
Type
Master's thesis
Access right
Acesso aberto
Abstract
Abstract (portuguese)
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.
Abstract (english)
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.
Description
Keywords
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
Language
Portuguese
Citation
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.
