A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs

• Hartwig Anzt Karlsruhe Institute of Technology / University of Tennessee
• Jack Dongarra University of Tennessee / Oak Ridge National Laboratory / University of Manchester

Resumo

Jaccard weights are a popular metric for identifying communities in social network analytics. In this paper we present a kernel for efficiently computing the Jaccard weight matrix on G PU s. The kernel design is guided by fine-grained parallelism and the independent thread scheduling supported by NVIDIA's Volta architecture. This technology makes it possible to interleave the execution of divergent branches for enhanced data reuse and a higher instruction per cycle rate for memory-bound algorithms. In a performance evaluation using a set of publicly available social networks, we report the kernel execution time and analyze the built-in hardware counters on different GPU architectures. The findings have implications beyond the specific algorithm and suggest a reformulation of other data-sparse algorithms.

Palavras-chave: Kernel, Graphics processing units, Sparse matrices, Instruction sets, Memory management, Message systems