Otimizando estruturas de grafos em memória persistente para arquiteturas NUMA

Abstract

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.

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.