Efficient strategies for graph pattern mining algorithms on GPUS
Carregando...
Data
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Artigo de evento
Título alternativo
Estratégias eficientes para algoritmos de mineração de padrões gráficos em GPUS
Primeiro orientador
Membros da banca
Resumo
Graph Pattern Mining (GPM) is an important,
rapidly evolving, and computation demanding area. GPM computation relies on subgraph enumeration, which consists in
extracting subgraphs that match a given property from an input
graph. Graphics Processing Units (GPUs) have been an effective
platform to accelerate applications in many areas. However, the
irregularity of subgraph enumeration makes it challenging for
efficient execution on GPU due to typical uncoalesced memory
access, divergence, and load imbalance. Unfortunately, these
aspects have not been fully addressed in previous work. Thus,
this work proposes novel strategies to design and implement
subgraph enumeration efficiently on GPU. We support a depthfirst search style search (DFS-wide) that maximizes memory
performance while providing enough parallelism to be exploited
by the GPU, along with a warp-centric design that minimizes
execution divergence and improves utilization of the computing
capabilities. We also propose a low-cost load balancing layer
to avoid idleness and redistribute work among thread warps in
a GPU. Our strategies have been deployed in a system named
DuMato, which provides a simple programming interface to allow
efficient implementation of GPM algorithms. Our evaluation has
shown that DuMato is often an order of magnitude faster than
state-of-the-art GPM systems and can mine larger subgraphs (up
to 12 vertices).
Abstract
Graph Pattern Mining (GPM) é uma ferramenta importante,
área em rápida evolução e exigente em computação. O cálculo do GPM depende da enumeração de subgráficos, que consiste em
extraindo subgráficos que correspondem a uma determinada propriedade de uma entrada
gráfico. Unidades de processamento gráfico (GPUs) têm sido uma solução eficaz
plataforma para acelerar aplicações em muitas áreas. No entanto, o
irregularidade na enumeração de subgráficos torna um desafio para
execução eficiente na GPU devido à memória não coalescida típica
acesso, divergência e desequilíbrio de carga. Infelizmente, estes
aspectos não foram totalmente abordados em trabalhos anteriores. Por isso,
este trabalho propõe novas estratégias para projetar e implementar
enumeração de subgráficos de forma eficiente na GPU. Oferecemos suporte a um estilo de pesquisa em profundidade (em todo o DFS) que maximiza a memória
desempenho enquanto fornece paralelismo suficiente para ser explorado
pela GPU, junto com um design centrado em warp que minimiza
divergência de execução e melhora a utilização da computação
capacidades. Também propomos uma camada de balanceamento de carga de baixo custo
para evitar ociosidade e redistribuir o trabalho entre thread warps em
uma GPU. Nossas estratégias foram implantadas em um sistema chamado
DuMato, que fornece uma interface de programação simples para permitir
implementação eficiente de algoritmos GPM. Nossa avaliação tem
mostrou que DuMato é frequentemente uma ordem de magnitude mais rápida que
sistemas GPM de última geração e pode extrair subgráficos maiores (até
para 12 vértices).
Assunto
Ciência da Computação, Estruturas de dados (Computação), Hardware
Palavras-chave
Structures, Data (Computer science), GPU
Citação
Departamento
Curso
Endereço externo
https://arxiv.org/abs/2212.04551