Two-Dimensional Matrix Partitioning for Parallel Computing on Heterogeneous Processors Based on Their Functional Performance Models

Abstract. The functional performance model (FPM) of heterogeneous proces-sors has proven to be more realistic than the traditional models because it integrates many important features of heterogeneous processors such as the processor heterogeneity, the heterogeneity of memory structure, and the effects of paging. Optimal 1D matrix partitioning algorithms employing FPMs of het-erogeneous processors are already being used in solving complicated linear al-gebra kernel such as dense factorizations. However, 2D matrix partitioning algorithms for parallel computing on heterogeneous processors based on their FPMs are unavailable. In this paper, we address this deficiency by presenting a novel iterative algorithm for partitioning a dense matrix over a 2D grid of het-erogeneous processors and employing their 2D FPMs. Experiments with a par-allel matrix multiplication application on a local heterogeneous computational cluster demonstrate the efficiency of this algorithm