A New Approximation Algorithm for Matrix Partitioning in Presence of Strongly Heterogeneous Processors

International audienceIn this paper, we consider the problem of partitioning a square into a set of zones of prescribed areas, while minimizing the overall size of their projections onto horizontal and vertical axes. This problem typically arises when considering the amount of communications induced when partitioning matrices for dense linear algebra kernels onto a set of heterogeneous processors. It has been first introduced for matrix multiplication in the 2000's, with a best known approximation ratio was 1.75. Since then, two main new ingredients have been introduced. First, Lastovetsky et al. proposed a special partitioning in the case of 2 or 3 strongly heterogeneous processors, as in the case of a platform made of CPUs and GPUs, relaxing the constraint of a rectangular based partitioning. Second, Nagamochi et al. have introduced clever recursive partitioning techniques and proved, thanks to a careful analysis, that their algorithm achieves a 1.25 approximation ratio. In this paper, we combine both ingredients in order to obtain a non-rectangular recursive partitioning (NRRP), whose approximation ratio is 2 √ 3 1.15. Moreover, we observe on a large set of realistic platforms built from CPUs and GPUs that this proposed NRRP algorithm allows to achieve very efficient partitionings on all considered cases. Index Terms