1 Load balancing in pre-processing of large-scale distributed sparse computation

Abstract In this paper, we study the sparse matrix-vector product (SMVP) distribution on a large scale distributed system (LSDS). The framework is defined by three steps: pre-processing, processing and post processing. We focus here only on the first step i.e. pre-processing. Our general goal is to detect, for a given sparse matrix, the best compression format i.e. which leads to the best performances for the SMVP on the LSDS. Thus, we need to study different approaches to distribute the data, essentially the sparse matrix. Three approaches are proposed. In the first one, the matrix A is partitioned into row blocks with the same number of rows. The second (resp. third) approach consists in partitioning A into blocks of contiguous (resp. non contiguous) rows with the same number of non-zero elements. These approaches result in solving some constrained scheduling problems of the NP-hard type. To solve them, we propose some multi-phase heuristics. After presenting these approaches, we present for each one a performance analysis. These analyses are then validated through a series of experimentations that permit to show their interest