skip to main content
10.1145/2806416.2806445acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Efficient Sparse Matrix Multiplication on GPU for Large Social Network Analysis

Published:17 October 2015Publication 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Koren et al., "Matrix Factorization Techniques for Recommender Systems," Computer, Vol. 42, No. 8, pp. 30--37, 2009. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. NVIDIA CUPARSE and CUBLAS libraries, https://developer.nvidia.com/gpu-accelerated-librariesGoogle ScholarGoogle Scholar
  9. csrGEMM library, http://on-demand.gputechconf.com/gtc/2012/presentations/S0285-GTC2012-Sparse-Matrix-Multiplication.pdfGoogle ScholarGoogle Scholar
  10. D. Kirk and W. Hwu, Programming Massively Parallel Processors, Morgan Kaufmann, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Stanford Large Network Dataset Collection, http://snap.stanford.edu/data/Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. GTX Titan Black Specification, http://www.geforce.com/hardware/desktop-gpus/geforce-gtx-titanblack/specificationsGoogle ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. N. Bell and M. Garland, Efficient Sparse Matrix-Vector Multiplication on CUDA, NVIDIA Technical Report NVR-2008-2004, NVIDIA Corporation, 2008.Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. Linear Algebra (4th Edition), S. Lipcshutz, M. Lipson, Schaum's Outlines, McGraw Hill (USA), 2009.Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

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

    Recommendations

    Comments

    Login options

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

    Sign in
    • 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

      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]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 17 October 2015

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      CIKM '15 Paper Acceptance Rate165of646submissions,26%Overall Acceptance Rate1,861of8,427submissions,22%

      Upcoming Conference

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader