Optimization of Sparse Distributed Computations

Optimization of Sparse Distributed Computations

Olfa Hamdi Larbi (University of Tunis El Manar, Tunisia & Taibah University, Tunisia)
Copyright: © 2022 |Pages: 18
DOI: 10.4018/IJGHPC.301586
OnDemand:
(Individual Articles)
Available
$37.50
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

We address the problem of the optimization of sparse matrix-vector product (SpMV) on homogeneous distributed systems. For this purpose, we propose three approaches based on partitioning the matrix into row blocks. These blocks are defined by a set of a fixed number of rows and a set of contiguous (resp. non-contiguous) rows containing a fixed number of non-zero elements. These approaches lead to solve some specific NP-hard scheduling problems. Thus, adequate heuristics are designed. We analyse the theoretical performance of the proposed approaches and validate them by a series of experiments. This work represents an important step in an overall objective which is to determine the best-balanced distribution for the SpMV computation on a distributed system. In order to validate our approaches for sparse matrix distribution, we compare them to hypergraph model as well as to PETSc library for SpMV distribution on a homogenous multicore cluster. Experimentations show that our approaches provide performances 2 times better than hypergraph and 49 times better than PETSc.
Article Preview
Top

Framework And Definitions

Sparse Matrices

Let A be a (real) large N×N matrix and NNZ the number of its nonzero elements. If NNZ is very small (resp. large), say NNZ=O(N) (resp O(N2)), then A is called sparse (resp. dense). Both storage requirements and computational time in any application operating on large sparse matrices may be dramatically reduced by only storing nonzero elements and avoiding useless operations on zero elements (Bik, 1996). This is achieved by using compressed storage formats for sparse matrices. A sparse matrix may have various structures according to the locations of its nonzero elements. For each sparse matrix structure, one or more dedicated compressed storage formats are known in the literature (i.e. CSR, COO, MCSR, JAD, etc) (Saad, 2019). In this paper, we are only interested in the CSR (Compressed Storage Row) format because it is the most used in the literature (Goharian, El-Ghazawi & Grossman, 2001).

Complete Article List

Search this Journal:
Reset
Volume 17: 1 Issue (2025): Forthcoming, Available for Pre-Order
Volume 16: 1 Issue (2024)
Volume 15: 2 Issues (2023)
Volume 14: 6 Issues (2022): 1 Released, 5 Forthcoming
Volume 13: 4 Issues (2021)
Volume 12: 4 Issues (2020)
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing