On-line Scheduling of MPI-2 Programs with Hierarchical Work Stealing

MPI (Message Passing Interface) is the de facto stan-dard in High Performance Computing. By using some MPI-2 new features, such as the dynamic creation of processes, it is possible to implement highly efficient parallel programs that can run on dynamic and/or heterogeneous resources, provided a good schedule of the processes can be computed at run-time. A classical solution to schedule parallel pro-grams on-line is Work Stealing. However, its use with MPI-2 is complicated by a restricted communication scheme be-tween the processes: namely, spawned processes in MPI-2 can only communicate with their direct parents. This work presents an on-line scheduling algorithm, called Hierarchi-cal Work Stealing, to obtain good load-balancing of MPI-2 programs that follow a Divide & Conquer strategy. Ex-perimental results are provided, based on a synthetic appli-cation, the N-Queens computation. The results show that the Hierarchical Work Stealing algorithm enables the use of MPI with high efficiency, even in parallel dynamic HPC platforms that are not as homogeneous as clusters.