@inproceedings{4d26ff9a336041549342a8d6e04f08ab,
title = "How to be a successful thief: Feudal work stealing for irregular divide-and-conquer applications on heterogeneous distributed systems",
abstract = "Work Stealing has proved to be an effective method for load balancing regular divide-and-conquer (D&C) applications on heterogeneous 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 consistently 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.",
keywords = "Divide-and-Conquer, Heterogeneous Systems, Irregular Parallelism, Work Stealing",
author = "Vladimir Janjic and Kevin Hammond",
year = "2013",
doi = "10.1007/978-3-642-40047-6_14",
language = "English",
isbn = "9783642400469",
series = "Lecture Notes in Computer Science",
publisher = "Springer ",
pages = "114--125",
editor = "Felix Wolf and Bernd Mohr and {an Mey}, Dieter",
booktitle = "Euro-Par 2013 Parallel Processing - 19th International Conference, Proceedings",
note = "19th International Conference on Parallel Processing, Euro-Par 2013 ; Conference date: 26-08-2013 Through 30-08-2013",
}