Load Balancing of Irregular Parallel Divide-and-Conquer Algorithms in Group-SPMD Programming Environments

摘要: We study strategies for local load balancing of irregular parallel divide-and- conquer algorithms such as Quicksort and Quickhull in SPMD-parallel environments MPI Fork that allow to exploit nested parallelism by dynamic group split- ting. propose two new strategies, repivoting serialisation, develop a hybrid strategy, which is calibrated parameters are derived off-line from programming optimisation. While the approach generic, we have implemented evaluated our method very different plat- forms. found strategy superior global on Linux cluster, while latter performs better tightly synchronised shared- memory platform with nonblocking, cheap task queue access.