How to be a Successful Thief:Feudal Work Stealing for Irregular Divide-and-Conquer Applications on Heterogeneous Distributed Systems

Work Stealing has proved to be an effective method for load balancing regular divide-and-conquer (D&C) applications on heteroge- neous distributed systems, but there have been relatively few attempts to adapt it to address irregular D&C applications. For such applications, it is essential to have a mechanism that can estimate dynamic system load during the execution of the applications. In this paper, we evaluate a number of work-stealing algorithms on a set of generic Unbalanced Tree Search (UTS) benchmarks. We present a novel Feudal Stealing work- stealing algorithm and show, using simulations, that it delivers consis- tently better speedups than other work-stealing algorithms for irregular D&C applications on high-latency heterogeneous distributed systems. Compared to the best known work-stealing algorithm for high-latency distributed systems, we achieve improvements of between 9% and 48% for irregular D&C applications