Optimization by runtime specialization for sparse matrix-vector multiplication

Sam Kamin, María Jesús Garzarán, Bariş Aktemur, Danqing Xu, Buse Yilmaz, Zhongbo Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Runtime specialization optimizes programs based on partial information available only at run time. It is applicable when some input data is used repeatedly while other input data varies. This technique has the potential of generating highly efficient codes. In this paper, we explore the potential for obtaining speedups for sparse matrix-dense vector multiplication using runtime specialization, in the case where a single matrix is to be multiplied by many vectors. We experiment with five methods involving runtime specialization, comparing them to methods that do not (including Intel's MKL library). For this work, our focus is the evaluation of the speedups that can be obtained with runtime specialization without considering the overheads of the code generation. Our experiments use 23 matrices from the Matrix Market and Florida collections, and run on five different machines. In 94 of those 115 cases, the specialized code runs faster than any version without specialization. If we only use specialization, the average speedup with respect to Intel's MKL library ranges from 1.44x to 1.77x, depending on the machine. We have also found that the best method depends on the matrix and machine; no method is best for all matrices and machines. Copyright is held by the author/owner(s).

Original languageEnglish (US)
Title of host publication13th International Conference on Generative Programming
Subtitle of host publicationConcepts and Experiences, GPCE 2014 - Proceedings
PublisherAssociation for Computing Machinery, Inc
Pages93-102
Number of pages10
ISBN (Electronic)9781450331616
DOIs
StatePublished - Sep 15 2014
Event13th International Conference on Generative Programming: Concepts and Experiences, GPCE 2014 - Vasteras, Sweden
Duration: Sep 15 2014Sep 16 2014

Publication series

Name13th International Conference on Generative Programming: Concepts and Experiences, GPCE 2014 - Proceedings

Other

Other13th International Conference on Generative Programming: Concepts and Experiences, GPCE 2014
CountrySweden
CityVasteras
Period9/15/149/16/14

Keywords

  • Performance evaluation
  • Program specialization
  • Sparse matrix-vector multiplication

ASJC Scopus subject areas

  • Computer Science Applications
  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'Optimization by runtime specialization for sparse matrix-vector multiplication'. Together they form a unique fingerprint.

  • Cite this

    Kamin, S., Garzarán, M. J., Aktemur, B., Xu, D., Yilmaz, B., & Chen, Z. (2014). Optimization by runtime specialization for sparse matrix-vector multiplication. In 13th International Conference on Generative Programming: Concepts and Experiences, GPCE 2014 - Proceedings (pp. 93-102). (13th International Conference on Generative Programming: Concepts and Experiences, GPCE 2014 - Proceedings). Association for Computing Machinery, Inc. https://doi.org/10.1145/2658761.2658773