research-article

Efficient Sparse Matrix Multiplication on GPU for Large Social Network Analysis

Authors:

Duck-Ho BaeAuthors Info & Claims

CIKM '15: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management

Pages 1261 - 1270

https://doi.org/10.1145/2806416.2806445

Published: 17 October 2015 Publication History

Abstract

As a number of social network services appear online recently, there have been many attempts to analyze social networks for extracting valuable information. Most existing methods first represent a social network as a quite sparse adjacency matrix, and then analyze it through matrix operations such as matrix multiplication. Due to the large scale and high complexity, efficient processing multiplications is an important issue in social network analysis. In this paper, we propose a GPU-based method for efficient sparse matrix multiplication through the parallel computing paradigm. The proposed method aims at balancing the amount of workload both at fine- and coarse-grained levels for maximizing the degree of parallelism in GPU. Through extensive experiments using synthetic and real-world datasets, we show that the proposed method outperforms previous methods by up to three orders-of-magnitude.

References

[1]

D. Bae, S. Hwang, and S. Kim, "Constructing Seminal Paper Genealogy," In Proc. ACM Int'l Conf. on Information and Knowledge Management, ACM CIKM, pp. 2101--2104, 2011.

Digital Library

[2]

G. He et al., "Parallel SimRank Computation on Large Graphs with Iterative Aggregation," In Proc. ACM Int'l Conf. on Knowledge Discovery and Data Mining, ACM SIGKDD, pp. 543--552, 2010.

Digital Library

[3]

Y. Cai et al., "Efficient algorithm for computing link-based similarity in real world networks," In Proc. IEEE Int'l Conf. on Data Mining, ICDM, pp. 734--739, 2009.

Digital Library

[4]

Y. Dong et al., "Link Prediction and Recommendation across Heterogeneous Social Networks," In Proc. IEEE Int'l Conf. on Data Mining, ICDM, pp. 181--190, 2012.

Digital Library

[5]

Koren et al., "Matrix Factorization Techniques for Recommender Systems," Computer, Vol. 42, No. 8, pp. 30--37, 2009.

Digital Library

[6]

U. Kang et al., "PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations," In Proc. IEEE Int'l Conf. on Data Mining, ICDM, p.229--238, 2009.

Digital Library

[7]

X. Yang, S. Parthasarathy, and P. Sadayappan, "Fast Sparse Matrix-Vector Multiplication on GPUs: Implications for Graph Mining," VLDB Endowment, Vol. 4, No. 4, pp. 231--242, 2011.

Digital Library

[8]

NVIDIA CUPARSE and CUBLAS libraries, https://developer.nvidia.com/gpu-accelerated-libraries

[9]

csrGEMM library, http://on-demand.gputechconf.com/gtc/2012/presentations/S0285-GTC2012-Sparse-Matrix-Multiplication.pdf

[10]

D. Kirk and W. Hwu, Programming Massively Parallel Processors, Morgan Kaufmann, 2010.

Digital Library

[11]

Stanford Large Network Dataset Collection, http://snap.stanford.edu/data/

[12]

J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graph Evolution: Densification and Shrinking Diameters," ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 1, No. 1, pp. 1--41, 2007.

Digital Library

[13]

GTX Titan Black Specification, http://www.geforce.com/hardware/desktop-gpus/geforce-gtx-titanblack/specifications

[14]

S. Ryoo et al., "Optimization Principles and Application Performance Evaluation of a Multithreaded GPU using CUDA," In Proc. ACM Int'l Symp. on Principles and Practice of Parallel Programming, ACM SIGPLAN, pp. 73--82, 2008.

Digital Library

[15]

V. Volkov and J. Demmel, "Benchmarking GPUs to Tune Dense Linear Algebra," In Proc. Int'l Conf. on Supercomputing, SC, pp. 1--11, 2008.

Digital Library

[16]

S. Ryoo et al., "Program Optimization Space Pruning for a Multithreaded GPU," In Proc. Int'l Symp. on Code Generation and Optimization, CGO, pp. 195--204, 2008.

Digital Library

[17]

N. Bell and M. Garland, Efficient Sparse Matrix-Vector Multiplication on CUDA, NVIDIA Technical Report NVR-2008-2004, NVIDIA Corporation, 2008.

[18]

J. W. Choi, et al., "Model-Driven Autotuning of Sparse Matrix-Vector Multiply on GPUs," In Proc. ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, PPoPP, pp. 115--126, 2010.

Digital Library

[19]

Linear Algebra (4th Edition), S. Lipcshutz, M. Lipson, Schaum's Outlines, McGraw Hill (USA), 2009.

[20]

O. Ibarra and C. Kim, "Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems", Journal of the ACM, Vol. 22, No. 4, pp. 463--468, 1975.

Digital Library

Cited By

Bi FHe TLuo X(2024)A Fast Nonnegative Autoencoder-Based Approach to Latent Feature Analysis on High-Dimensional and Incomplete DataIEEE Transactions on Services Computing10.1109/TSC.2023.331971317:3(733-746)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3319713
Xiao GYin CZhou TLi XChen YLi K(2023)A Survey of Accelerating Parallel Sparse Linear AlgebraACM Computing Surveys10.1145/360460656:1(1-38)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1145/3604606
Yang YPeng SPark DHao FLee H(2022)A Novel Community Detection Method of Social Networks for the Well-Being of Urban Public SpacesLand10.3390/land1105071611:5(716)Online publication date: 10-May-2022
https://doi.org/10.3390/land11050716
Show More Cited By

Index Terms

Efficient Sparse Matrix Multiplication on GPU for Large Social Network Analysis
1. Information systems
  1. Information systems applications

Recommendations

Adaptive sparse matrix-matrix multiplication on the GPU
PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming

In the ongoing efforts targeting the vectorization of linear algebra primitives, sparse matrix-matrix multiplication (SpGEMM) has received considerably less attention than sparse Matrix-Vector multiplication (SpMV). While both are equally important, ...
GPU accelerated sparse matrix-vector multiplication and sparse matrix-transpose vector multiplication

Many high performance computing applications require computing both sparse matrix-vector product SMVP and sparse matrix-transpose vector product SMTVP for better overall performance. Under such a circumstance, it is critical to maintain a similarly high ...
Design Principles for Sparse Matrix Multiplication on the GPU
Euro-Par 2018: Parallel Processing
Abstract
We implement two novel algorithms for sparse-matrix dense-matrix multiplication (SpMM) on the GPU. Our algorithms expect the sparse input in the popular compressed-sparse-row (CSR) format and thus do not require expensive format conversion. While ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '15: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management

October 2015

1998 pages

ISBN:9781450337946

DOI:10.1145/2806416

General Chairs:
James Bailey
The University of Melbourne
,
Alistair Moffat
The University of Melbourne
,
Program Chairs:
Charu C. Aggarwal
IBM
,
Maarten de Rijke
University of Amsterdam
,
Ravi Kumar
Google
,
Vanessa Murdock
Microsoft
,
Timos Sellis
RMIT University
,
Jeffrey Xu Yu
Chinese University of Hong Kong

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Research Foundation of Korea

Conference

CIKM'15

Sponsor:

CIKM'15: 24th ACM International Conference on Information and Knowledge Management

October 18 - 23, 2015

Melbourne, Australia

Acceptance Rates

CIKM '15 Paper Acceptance Rate 165 of 646 submissions, 26%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
410
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bi FHe TLuo X(2024)A Fast Nonnegative Autoencoder-Based Approach to Latent Feature Analysis on High-Dimensional and Incomplete DataIEEE Transactions on Services Computing10.1109/TSC.2023.331971317:3(733-746)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3319713
Xiao GYin CZhou TLi XChen YLi K(2023)A Survey of Accelerating Parallel Sparse Linear AlgebraACM Computing Surveys10.1145/360460656:1(1-38)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1145/3604606
Yang YPeng SPark DHao FLee H(2022)A Novel Community Detection Method of Social Networks for the Well-Being of Urban Public SpacesLand10.3390/land1105071611:5(716)Online publication date: 10-May-2022
https://doi.org/10.3390/land11050716
Chen YXiao GLi KPiccialli FZomaya A(2022)fgSpMSpV: A Fine-grained Parallel SpMSpV Framework on HPC PlatformsACM Transactions on Parallel Computing10.1145/35127709:2(1-29)Online publication date: 30-Jun-2022
https://doi.org/10.1145/3512770
Moe JPogorelov KSchroeder DLangguth J(2022)Implementing Spatio-Temporal Graph Convolutional Networks on Graphcore IPUs2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW55747.2022.00016(45-54)Online publication date: May-2022
https://doi.org/10.1109/IPDPSW55747.2022.00016
Lee JKang SYu YJo YKim SPark Y(2020)Optimization of GPU-based Sparse Matrix Multiplication for Large Sparse Networks2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00085(925-936)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00085
Zhang JGruenwald L(2018)Regularizing irregularityProceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3210259.3210263(1-8)Online publication date: 10-Jun-2018
https://dl.acm.org/doi/10.1145/3210259.3210263
Jo YLee KJang MKim SSong E(2017)Efficient processing of large-scale sparse matrix-matrix multiplications on a single machine2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC.2017.8122896(1908-1913)Online publication date: 5-Oct-2017
https://dl.acm.org/doi/10.1109/SMC.2017.8122896
AlZu'bi SShehab MAl-Ayyoub MBenkhelifa EJararweh Y(2016)Parallel implementation of FCM-based volume segmentation of 3D images2016 IEEE/ACS 13th International Conference of Computer Systems and Applications (AICCSA)10.1109/AICCSA.2016.7945811(1-6)Online publication date: Nov-2016
https://doi.org/10.1109/AICCSA.2016.7945811

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents