skip to main content
10.1145/1391469.1391473acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
research-article

Sparse matrix computations on manycore GPU's

Published:08 June 2008Publication History

ABSTRACT

Modern microprocessors are becoming increasingly parallel devices, and GPUs are at the leading edge of this trend. Designing parallel algorithms for manycore chips like the GPU can present interesting challenges, particularly for computations on sparse data structures. One particularly common example is the collection of sparse matrix solvers and combinatorial graph algorithms that form the core of many physical simulation techniques. Although seemingly irregular, these operations can often be implemented with data parallel operations that map very well to massively parallel processors.

References

  1. P. Alliez, G. Ucelli, C. Gotsman, and M. Attene. Recent advances in remeshing of surfaces. In L. D. Floriani and M. Spagnulo, editors, Shape Analysis and Structuring, pages 53--82. Springer, 2007.Google ScholarGoogle Scholar
  2. A.-L. Barabási and E. Bonabeau. Scale-free networks. Scientific American, 288:60--69, 2003.Google ScholarGoogle ScholarCross RefCross Ref
  3. G. E. Blelloch. Vector models for data-parallel computing. MIT Press, Cambridge, MA, USA, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, Second edition, Sept. 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. CUDPP: CUDA data parallel primitives library. http://www.gpgpu.org/developer/cudpp/.Google ScholarGoogle Scholar
  6. G. H. Golub and C. F. V. Loan. Matrix Computations. Johns Hopkins Univ. Press, Baltimore, Third edition, 1996.Google ScholarGoogle Scholar
  7. W. D. Hillis and J. Guy L. Steele. Data parallel algorithms. Commun. ACM, 29(12):1170--1183, 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. E. Lindholm, J. Nickolls, S. Oberman, and J. Montrym. NVIDIA Tesla: A unified graphics and computing architecture. IEEE Micro, 28(2), Mar/Apr 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. M. E. J. Newman. The structure and function of complex networks. In SIAM Review, volume 45, pages 167--256, 2003.Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. J. Nickolls, I. Buck, K. Skadron, and M. Garland. CUDA: Scalable parallel programming. ACM Queue, Mar/Apr 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. NVIDIA Corporation. NVIDIA CUDA Programming Guide, Nov. 2007. Version 1.1.Google ScholarGoogle Scholar
  12. S. Sengupta, M. Harris, Y. Zhang, and J. D. Owens. Scan primitives for GPU computing. In Graphics Hardware 2007, pages 97--106. ACM, Aug. 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. J. A. Stratton, S. S. Stone, and W. W. Hwu. M-CUDA: An efficient implementation of CUDA kernels on multi-cores. IMPACT Technical Report IMPACT-08-01, UIUC, Feb. 2008.Google ScholarGoogle Scholar
  14. S. Williams, L. Oliker, R. Vuduc, J. Shalf, K. Yelick, and J. Demmel. Optimization of sparse matrix-vector multiplication on emerging multicore platforms. In Proc. Supercomputing 2007, Nov. 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Sparse matrix computations on manycore GPU's

      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
        DAC '08: Proceedings of the 45th annual Design Automation Conference
        June 2008
        993 pages
        ISBN:9781605581156
        DOI:10.1145/1391469
        • General Chair:
        • Limor Fix

        Copyright © 2008 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: 8 June 2008

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

        Acceptance Rates

        Overall Acceptance Rate1,369of4,297submissions,32%

        Upcoming Conference

        DAC '24
        61st ACM/IEEE Design Automation Conference
        June 23 - 27, 2024
        San Francisco , CA , USA

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader