Optimizing graph processing execution on NUMA machines

Abstract

In recent years, there has been an unprecedented growth of interconnected data built on top of graph data structures, with graph applications processing large amounts of information. Graph algorithms, such as Breadth-First-Search (BFS) and PageRank (PR), directly benefit several fields, such as scientific computing, neuroscience, and social network analysis, and execute on High-Performance Computing (HPC) servers. These HPC systems are usually Non-Uniform Memory Access (NUMA) machines, where the memory access time depends on the memory location in relation to the cores, so performance strongly depends on how threads and pages (data) are mapped to different processor nodes, and the number of actives cores. Given their highly irregular communication pattern and poor data locality, graph processing are more sensitive to such alternative configurations, introducing additional challenges. Therefore, considering that the ideal thread/data mapping and number of active threads may change according to the system (e.g., microarchitecture and number of cores), graph algorithm, input graph, or even the source vertex, rightly choosing the ideal configuration is not straightforward. In this scenario, this thesis proposes new approaches to finding such near-optimal configurations for graph algorithms executing on NUMA machines. To achieve that, we leverage the unique features that characterize graph data (e.g., the number of vertices and clustering coefficient) to use in a machine learning framework. Our experimental results, considering different input graphs and algorithms executing on three NUMA machines, and comparing them with other approaches for tuning the number of threads, thread mapping, and/or data mapping, reveal the effectiveness of our proposed methods in improving algorithm execution time while significantly reducing energy consumption.

Nos últimos anos, houve um crescimento sem precedentes de dados interconectados construídos sobre estruturas de dados de grafos, com aplicações de grafos processando grandes quantidades de informações. Algoritmos de grafos, como Breadth-First-Search (BFS) e PageRank (PR), beneficiam diretamente várias áreas, como computação científica, neurociência e análise de redes sociais, executando em servidores de Computação de Alto Desempenho (HPC). Esses sistemas de HPC geralmente são compostos por máquinas de Acesso Não Uniforme à Memória (NUMA), onde o tempo de acesso à memória depende da localização da memória em relação aos núcleos, portanto, o desempenho depende fortemente de como as threads e páginas (dados) são mapeadas para diferentes nós do processador e o número de núcleos ativos. Dada a natureza altamente irregular do padrão de comunicação e a baixa localidade dos dados, o processamento de grafos é mais sensível a essas configurações alternativas, introduzindo desafios adicionais. Portanto, considerando que o mapeamento ideal de threads/dados e o número de threads ativas podem mudar de acordo com o sistema (por exemplo, microarquitetura e número de núcleos), algoritmo de grafos, grafo de entrada ou até mesmo o vértice de origem, escolher adequadamente a configuração ideal não é uma tarefa trivial. Nesse cenário, esta tese propõe novas abordagens para encontrar configurações otimizadas para algoritmos de grafos executando em máquinas NUMA. Para alcançar isso, aproveitamos as características únicas que descrevem a estrutura dos grafos (por exemplo, o número de vértices e coeficiente de agrupamento) para usar em um framework de aprendizado de máquina. Nossos resultados experimentais, considerando diferentes grafos de entrada e algoritmos executados em três máquinas NUMA, e comparando-os com outras abordagens para ajuste do número de threads e mapeamento de threads e dados, revelam a eficácia de nossos métodos propostos em melhorar o tempo de execução do algoritmo, reduzindo significativamente o consumo de energia.