A New Approximation Algorithm for Matrix Partitioning in Presence of Strongly Heterogeneous Processors
Olivier D.E. Beaumont, Lionel Eyraud‐Dubois, Thomas Andrew Lambert · 2016
In this paper, we consider the problem of partitioning a square into aset of zones of prescribed areas, while minimizing the overall size oftheir projections onto horizontal and vertical axes. This problemtypically arises when considering the amount of communications inducedwhen partitioning matrices for dense linear algebra kernels onto a setof heterogeneous processors. It has been first introduced for matrixmultiplication in the 2000's, with a best known approximation ratiowas 1.75. Since then, two main new ingredients have beenintroduced. First, Lastovetsky et al. proposed a special partitioningin the case of 2 or 3 strongly heterogeneous processors, as in thecase of a platform made of CPUs and GPUs, relaxing the constraint of arectangular based partitioning. Second, Nagamochi et al. haveintroduced clever recursive partitioning techniques and proved, thanksto a careful analysis, that their algorithm achieves a 1.25approximation ratio. In this paper, we combine both ingredients inorder to obtain a non-rectangular recursive partitioning (NRRP), whoseapproximation 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.