A carregar...
Publicação
GPU ACCELERATED DYNAMIC GRAPH PROCESSING
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 3.14 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
Graphs are ubiquitous in today’s large-scale computing systems. With the rapid advance
of technology and applications, the size of these graphs, and the complexity of the
computations performed on them is constantly increasing. This has led to a need for
the development and research of parallel graph processing, in order to overcome the
computational limits of single-processor-based solutions. At the forefront of this research,
is Graphics Processing Unit (GPU)-accelerated graph processing, as the GPU’s massive
parallelization capabilities allow for extremely efficient execution of algorithms on large
graphs.
In the last years, various GPU-accelerated graph processing frameworks have emerged
and started being utilized in the industry. However, practically all of these frameworks
only support static graphs, meaning that whenever the graph is updated, it must be
entirely retransmitted to the GPU for further processing. In a landscape where many
large graphs are constantly evolving, like for example social and financial networks, this
becomes an issue. Some dynamic GPU-accelerated graph processing frameworks have
already emerged, however, they are few and their usability is still limited, making this an
open and relevant area of research.
In this thesis, we present Marrow-Graph, a fast GPU-accelerated dynamic graph pro-
cessing library, built using the Marrow framework. The library supports efficient graph
updates, provides a simple yet expressive programming model, and includes multiple
commonly used graph processing algorithms. To achieve this, the graph is stored both
on the host and device using Marrow collections, allowing one to execute algorithms
efficiently on the device while performing lazy graph updates on the host. Additionally,
we demonstrate how our solution offers better usability and conciseness compared to com-
petitors, and exhibits promising performance. Marrow-Graph outperforms FaimGraph
and Hornet in some algorithms, achieves speedups up to x260 compared to state-of-the-
art Central Processing Unit (CPU)-based solutions, and provides faster real-time edge
insertions using small to medium update batches.
Actualmente, grafos podem ser encontrados numa grande parte dos sistemas informáti- cos de grande escala. Com o rápido avanço da tecnologia e das aplicações, o tamanho destes grafos e a complexidade das computações efectuados sobre estes, estão a aumentar constantemente. Isto tem levado à necessidade de desenvolver e investigar o processa- mento paralelo de grafos, de modo a ultrapassar os limites computacionais das soluções baseadas em processadores únicos. Na frente desta investigação está o processamento de grafos acelerado por GPU, uma vez que as capacidades de paralelização massiva da GPU permitem execuções extremamente eficiente de algoritmos em grafos de grandes dimensões. Nos últimos anos, várias frameworks de processamento de grafos acelerados por GPU têm surgido e começado a ser utilizadas na indústria, no entanto, a maioria suportam apenas grafos estáticos, o que significa que sempre que o grafo é atualizado, este é retransmitido por completo para a GPU para processamento posterior. No cenário atual, em que muitos grafos de grandes dimensões estão em constante evolução, como por exemplo as redes sociais e financeiras, isto torna-se um problema. Já surgiram algumas frameworks de processamento de grafos dinâmicos acelerados por GPU, no entanto são poucas e a sua usabilidade ainda é limitada, tornando esta uma área de investigação aberta e relevante. Nesta dissertação apresentamos o Marrow-Graph, uma biblioteca de processamento de grafos dinâmicos acelerada por GPU, desenvolvida com a framework Marrow. A biblioteca suporta actualizações eficientes sobre grafos, providencia um modelo de programação simples mas expressivo, e inclui multiplos algoritmos comuns de processamento de grafos. Para tal, o grafo é armazenado tanto no host como no device utilizando as coleções do Marrow, o que permite executar algoritmos de forma eficiente no device, e efetuar atualizações lazy sobre o grafo no host. Além disso, demonstramos como a nossa solução oferece melhor usabilidade e concisão em comparação com os concorrentes, e apresenta um desempenho promissor. O Marrow-Graph supera o FaimGraph e o Hornet em alguns algoritmos, atinge speedups até x260 em comparação com as soluções do estado da arte baseadas em CPU, e permite inserções em tempo real de edges mais rápidas usando update batches pequenos a médios.
Actualmente, grafos podem ser encontrados numa grande parte dos sistemas informáti- cos de grande escala. Com o rápido avanço da tecnologia e das aplicações, o tamanho destes grafos e a complexidade das computações efectuados sobre estes, estão a aumentar constantemente. Isto tem levado à necessidade de desenvolver e investigar o processa- mento paralelo de grafos, de modo a ultrapassar os limites computacionais das soluções baseadas em processadores únicos. Na frente desta investigação está o processamento de grafos acelerado por GPU, uma vez que as capacidades de paralelização massiva da GPU permitem execuções extremamente eficiente de algoritmos em grafos de grandes dimensões. Nos últimos anos, várias frameworks de processamento de grafos acelerados por GPU têm surgido e começado a ser utilizadas na indústria, no entanto, a maioria suportam apenas grafos estáticos, o que significa que sempre que o grafo é atualizado, este é retransmitido por completo para a GPU para processamento posterior. No cenário atual, em que muitos grafos de grandes dimensões estão em constante evolução, como por exemplo as redes sociais e financeiras, isto torna-se um problema. Já surgiram algumas frameworks de processamento de grafos dinâmicos acelerados por GPU, no entanto são poucas e a sua usabilidade ainda é limitada, tornando esta uma área de investigação aberta e relevante. Nesta dissertação apresentamos o Marrow-Graph, uma biblioteca de processamento de grafos dinâmicos acelerada por GPU, desenvolvida com a framework Marrow. A biblioteca suporta actualizações eficientes sobre grafos, providencia um modelo de programação simples mas expressivo, e inclui multiplos algoritmos comuns de processamento de grafos. Para tal, o grafo é armazenado tanto no host como no device utilizando as coleções do Marrow, o que permite executar algoritmos de forma eficiente no device, e efetuar atualizações lazy sobre o grafo no host. Além disso, demonstramos como a nossa solução oferece melhor usabilidade e concisão em comparação com os concorrentes, e apresenta um desempenho promissor. O Marrow-Graph supera o FaimGraph e o Hornet em alguns algoritmos, atinge speedups até x260 em comparação com as soluções do estado da arte baseadas em CPU, e permite inserções em tempo real de edges mais rápidas usando update batches pequenos a médios.
Descrição
Palavras-chave
Dynamic Graph Graph Analytics GPU Marrow CUDA