A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs

Hartwig Anzt; Jack Dongarra

doi:10.1109/CAHPC.2018.8645946

A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs

Hartwig Anzt, Jack Dongarra

Computer Science and Mathematics Div

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	229-232
Number of pages	4
ISBN (Electronic)	9781538677698
DOIs	https://doi.org/10.1109/CAHPC.2018.8645946
State	Published - Jul 2 2018
Event	30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018 - Lyon, France Duration: Sep 24 2018 → Sep 27 2018

Publication series

Name	Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018

Conference

Conference	30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018
Country/Territory	France
City	Lyon
Period	09/24/18 → 09/27/18

Funding

ACKNOWLEDGMENT This material is based upon work supported by the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under Award Number DE-SC0016513. H. Anzt was supported by the “Impuls und Vernetzungsfondof the Helmholtz Association” under grant VH-NG-1241. The authors would like to thank the High Performance Computing & Architectures (HPCA) group at the University of Jaume for granting access to the TITAN X GPU.

Access to Document

10.1109/CAHPC.2018.8645946

Cite this

Anzt, H., & Dongarra, J. (2018). A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs. In Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018 (pp. 229-232). Article 8645946 (Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CAHPC.2018.8645946

Anzt, Hartwig ; Dongarra, Jack. / A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs. Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 229-232 (Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018).

@inproceedings{f02ff70e15a64afbaf2d2951da5104fb,

title = "A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs",

abstract = "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.",

author = "Hartwig Anzt and Jack Dongarra",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018 ; Conference date: 24-09-2018 Through 27-09-2018",

year = "2018",

month = jul,

day = "2",

doi = "10.1109/CAHPC.2018.8645946",

language = "English",

series = "Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "229--232",

booktitle = "Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018",

}

Anzt, H & Dongarra, J 2018, A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs. in Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018., 8645946, Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018, Institute of Electrical and Electronics Engineers Inc., pp. 229-232, 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018, Lyon, France, 09/24/18. https://doi.org/10.1109/CAHPC.2018.8645946

A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs. / Anzt, Hartwig; Dongarra, Jack.
Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 229-232 8645946 (Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs

AU - Anzt, Hartwig

AU - Dongarra, Jack

PY - 2018/7/2

Y1 - 2018/7/2

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

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

UR - http://www.scopus.com/inward/record.url?scp=85063143725&partnerID=8YFLogxK

U2 - 10.1109/CAHPC.2018.8645946

DO - 10.1109/CAHPC.2018.8645946

M3 - Conference contribution

AN - SCOPUS:85063143725

T3 - Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018

SP - 229

EP - 232

BT - Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018

Y2 - 24 September 2018 through 27 September 2018

ER -

Anzt H, Dongarra J. A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs. In Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 229-232. 8645946. (Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018). doi: 10.1109/CAHPC.2018.8645946

A Jaccard Weights Kernel Leveraging Independent Thread Scheduling on GPUs

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this