Symmetrical hopping: A scalable scheduling algorithm for irregular problems

Publisher Website
Google Scholar
Abstract
A run‐time support is necessary for parallel computations with irregular and dynamic structures. One important component in the support system is the run‐time scheduler which balances the working load in the system. We present a new algorithm, Symmetrical Hopping, for dynamic scheduling of ultra‐lightweight processes. It is a dynamic, distributed, adaptive and scalable scheduling algorithm. This algorithm is described and compared to four other algorithms that have been proposed in this context, namely the randomized allocation, the sender‐initiated scheduling, the receiver‐initiated scheduling, and the gradient model. The performance of these algorithms on Intel Touchstone Delta is presented. The experimental results show that the Symmetrical Hopping algorithm achieves much better performance due to its adaptiveness.