Straight‐line programs for fast sparse matrix‐vector multiplication. (28th January 2014)

• Record Type: Journal Article
• Authors: Neves, Samuel; Araujo, Filipe; Limet, Sébastien; Smari, Waleed W.; Spalazzi, Luca; Hu, Jia; Gao, Jianliang
• Is Part Of: Concurrency and computation. Volume 27:Number 13(2015:Sep.)
• Page Start: 3245
• Page End: 3261
• Publication Date: 2014-01-28
• Subjects: Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3211
• Languages: English
• ISSNs: 1532-0626

Abstract

<abstract abstract-type="main" id="cpe3211-abs-0001"> <title>Summary</title> <p id="cpe3211-para-0001">Sparse matrix‐vector multiplication dominates the performance of many scientific and industrial problems. For example, iterative methods for solving linear systems often rely on the performance of this critical operation. The particular case of binary matrices shows up in several important areas of computing, such as graph theory and cryptography. Unfortunately, irregular memory access patterns cause poor memory throughput, slowing down this operation. To maximize memory throughput, we translate the matrix into a straight‐line program that takes advantage of the CPU's instruction cache and hardware prefetchers. The regular loopless pattern of the program reduces cache misses, thus decreasing the latency for most instructions. We focus on the widely used <monospace>x86_64</monospace> architecture and on binary matrices, to explore several possible tradeoffs regarding memory access policies and code size. We also consider matrices with elements over various mathematical structures, such as floating‐point reals and integers modulo <italic>m</italic>. When compared to a Compressed Row Storage implementation, we obtain significant speedups. Copyright © 2014 John Wiley &amp; Sons, Ltd.</p> </abstract>