Efficient strategies for graph pattern mining algorithms on GPUS

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).