Using Computational Geometry to Improve Process Rescheduling on Round-Based Parallel Applications

Abstract

Process rescheduling is a known technique to face with system heterogeneity and dynamism, being especially pertinent on Bulk Synchronous Parallel (BSP) programs. These programs are organized in a set of round-based supersteps, in which the slowest process determines the moment of synchronization. This approach motivated us to develop a first model called MigBSP, which combines computation, communication and migration costs metrics for process rescheduling decisions. MigBSP originally employed an heuristic that could select either a single or a collection of process to migrate at each load balancing invocation. The first proposal is not reactive, so you should manually setup a percentage of processes to be migrated as input parameter for the load balancing model. In this work, two novel heuristics, named MigCube and MigHull, are proposed to choose the candidate processes for migration and their destination. Both heuristics consider the use of computational geometry for plotting computation, communication and migration costs metrics in a 3D graph, so both which and where load balancing questions can be answered without any user intervention. We believe that the contribution is not only in the MigBSP landscape, but also for the BSP community, who is trying to enhance performance in round-based applications in an effortless way. In addition to the description of MigCube and MigHull, this article also presents their evaluations with performance gains of up to 42% when enabling process migration over a subset of the Grid5000 infrastructure.