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.
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Koren et al., "Matrix Factorization Techniques for Recommender Systems," Computer, Vol. 42, No. 8, pp. 30--37, 2009. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- NVIDIA CUPARSE and CUBLAS libraries, https://developer.nvidia.com/gpu-accelerated-librariesGoogle Scholar
- csrGEMM library, http://on-demand.gputechconf.com/gtc/2012/presentations/S0285-GTC2012-Sparse-Matrix-Multiplication.pdfGoogle Scholar
- D. Kirk and W. Hwu, Programming Massively Parallel Processors, Morgan Kaufmann, 2010. Google ScholarDigital Library
- Stanford Large Network Dataset Collection, http://snap.stanford.edu/data/Google Scholar
- 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. Google ScholarDigital Library
- GTX Titan Black Specification, http://www.geforce.com/hardware/desktop-gpus/geforce-gtx-titanblack/specificationsGoogle Scholar
- 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. Google ScholarDigital Library
- V. Volkov and J. Demmel, "Benchmarking GPUs to Tune Dense Linear Algebra," In Proc. Int'l Conf. on Supercomputing, SC, pp. 1--11, 2008. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- N. Bell and M. Garland, Efficient Sparse Matrix-Vector Multiplication on CUDA, NVIDIA Technical Report NVR-2008-2004, NVIDIA Corporation, 2008.Google Scholar
- 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. Google ScholarDigital Library
- Linear Algebra (4th Edition), S. Lipcshutz, M. Lipson, Schaum's Outlines, McGraw Hill (USA), 2009.Google Scholar
- 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. Google ScholarDigital Library
Index Terms
Efficient Sparse Matrix Multiplication on GPU for Large Social Network Analysis
Recommendations
Adaptive sparse matrix-matrix multiplication on the GPU
PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel ProgrammingIn 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, ...
Optimizing Sparse Matrix—Matrix Multiplication for the GPU
Sparse matrix--matrix multiplication (SpGEMM) is a key operation in numerous areas from information to the physical sciences. Implementing SpGEMM efficiently on throughput-oriented processors, such as the graphics processing unit (GPU), requires the ...
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 ...
Comments