Optimal partitioning of nodes to space-sharing parallel tasks

This paper focuses on the execution of distributed applications on parallel platforms, such as MPPs or homogeneous clusters. These applications are usually formed by individual tasks, which are each mapped to the nodes available in the parallel platform. When these tasks can execute simultaneously, it may be necessary to space-share the nodes available within the application. In this case, partitioning the nodes among the space-sharing tasks is key in obtaining the best performance. This paper presents a polynomial algorithm to provide an optimal partitioning of nodes to parallel tasks, enabling them to execute simultaneously in minimum time.