Guntram Berti and Jesper L. Träff. What MPI could (and cannot) do for Mesh-partitioning on Non-homogeneous Networks. In Bernd Mohr and Jesper Larsson Träff and Joachim Worringen and Jack Dongarra, editors, Proceedings of EUROPVM/MPI 2006, Bonn, Germany, 17.-20. September 2006.
We discuss the mesh-partitioning load-balancing problem for non-homogeneous communication systems, and investigate whether the MPI process topology functionality can aid in solving the problem. An example kernel shows that specific communication patterns can benefit substantially from a non-trivial MPI topology implementation, achieving improvements beyond a factor of five for certain system configurations. Still, the topology functionality lacks expressivity to deal effectively with the mesh-partitioning problem. A mild extension to MPI is suggested, which, however, still cannot exclude possibly sub-optimal partitioning results. Solving instead the mesh-partitioning problem outside of MPI requires knowledge of the communication system. We discuss ways in which such could be provided by MPI in a portable way. Finally, we formulate and discuss a more general affinity scheduling problem.