On the Complexity of the Generalized Block Distribution

Abstract

We consider the problem of mapping an array onto a mesh of processors in such a way that locality is preserved. When the computational work associated with the array is distributed in an unstructured way the generalized block distribution has been recognized as an efficient way of achieving an even load balance while at the same time imposing a simple communication pattern. In this paper we consider the problem of computing an optimal generalized block distribution. We show that this problem is NP-complete even for very simple cost functions. We also classify a number of variants of the general problem.

Back to publication page