elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication

Alappat, Christie Louis and Hager, Georg and Schenk, Olaf and Thies, Jonas and Basermann, Achim and Bishop, Alan R. and Fehske, Holger and Wellein, Gerhard (2020) A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication. ACM Transactions on Mathematical Software. Association for Computing Machinery (ACM). ISSN 0098-3500 (Submitted)

WarningThere is a more recent version of this item available.

[img] PDF - Preprint version (submitted draft)
1MB

Abstract

The symmetric sparse matrix-vector multiplication (SymmSpMV) is an important building block for many numerical linear algebra kernel operations or graph traversal applications. Parallelizing SymmSpMV on today's multicore platforms with up to 100 cores is difficult due to the need to manage conflicting updates on the result vector. Coloring approaches can be used to solve this problem without data duplication, but existing coloring algorithms do not take load balancing and deep memory hierarchies into account, hampering scalability and full-chip performance. In this work, we propose the recursive algebraic coloring engine (RACE), a novel coloring algorithm and open-source library implementation, which eliminates the shortcomings of previous coloring methods in terms of hardware efficiency and parallelization overhead. We describe the level construction, distance-k coloring, and load balancing steps in RACE, use it to parallelize SymmSpMV, and compare its performance on 31 sparse matrices with other state-of-the-art coloring techniques and Intel MKL on two modern multicore processors. RACE outperforms all other approaches substantially and behaves in accordance with the Roofline model. Outliers are discussed and analyzed in detail. While we focus on SymmSpMV in this paper, our algorithm and software is applicable to any sparse matrix operation with data dependencies that can be resolved by distance-k coloring.

Item URL in elib:https://elib.dlr.de/130638/
Document Type:Article
Title:A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Alappat, Christie LouisFriedrich-Alexander Universität Erlangen-NürnbergUNSPECIFIED
Hager, GeorgGeorg.Hager (at) fau.deUNSPECIFIED
Schenk, OlafOlaf.Schenk (at) usi.chUNSPECIFIED
Thies, JonasJonas.Thies (at) dlr.deUNSPECIFIED
Basermann, AchimAchim.Basermann (at) dlr.dehttps://orcid.org/0000-0003-3637-3231
Bishop, Alan R.Los Alamos National LaboratoryUNSPECIFIED
Fehske, HolgerFehske (at) physik.uni-greifswald.deUNSPECIFIED
Wellein, GerhardErlangen Regional Computing CenterUNSPECIFIED
Date:2020
Journal or Publication Title:ACM Transactions on Mathematical Software
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:Yes
In ISI Web of Science:Yes
Publisher:Association for Computing Machinery (ACM)
ISSN:0098-3500
Status:Submitted
Keywords:graph coloring, hardware efficiency, performance engineering, multi-threading, distance-k dependencies, sparse matrix
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Technik für Raumfahrtsysteme
DLR - Research theme (Project):R - Vorhaben SISTEC
Location: Köln-Porz
Institutes and Institutions:Institut of Simulation and Software Technology
Deposited By: Thies, Jonas
Deposited On:20 Nov 2019 12:41
Last Modified:20 Nov 2019 12:41

Available Versions of this Item

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.