Using Load Information in Work-Stealing on Distributed Systems with Non-Uniform Communication Latencies

We evaluate four state-of-the-art work-stealing algorithms for distributedsystems with non-uniform communication latenices(Random Stealing, Hierarchical Stealing, Cluster-awareRandom Stealing and Adaptive Cluster-aware Random Stealing) on a set of irregular Divide-and-Conquer (D\&C) parallel applications. We alsoinvestigate the extent to which these algorithms could beimproved if dynamic load information isavailable, and how accurate this information needs to be. We show that, for highly-irregular D\&Capplications, the use of load information can significantly improveapplication speedups, whereas there is little improvement for less irregular ones. Furthermore, we show that when loadinformation is used, Cluster-aware Random Stealing givesthe best speedups for both regular and irregular D\&C applications.