TY - GEN
T1 - Using load information in work-stealing on distributed systems with non-uniform communication latencies
AU - Janjic, Vladimir
AU - Hammond, Kevin
PY - 2012
Y1 - 2012
N2 - We evaluate four state-of-the-art work-stealing algorithms for distributed systems with non-uniform communication latenices (Random Stealing, Hierarchical Stealing, Cluster-aware Random Stealing and Adaptive Cluster-aware Random Stealing) on a set of irregular Divide-and-Conquer (D&C) parallel applications. We also investigate the extent to which these algorithms could be improved if dynamic load information is available, and how accurate this information needs to be. We show that, for highly-irregular D&C applications, the use of load information can significantly improve application speedups, whereas there is little improvement for less irregular ones. Furthermore, we show that when load information is used, Cluster-aware Random Stealing gives the best speedups for both regular and irregular D&C applications.
AB - We evaluate four state-of-the-art work-stealing algorithms for distributed systems with non-uniform communication latenices (Random Stealing, Hierarchical Stealing, Cluster-aware Random Stealing and Adaptive Cluster-aware Random Stealing) on a set of irregular Divide-and-Conquer (D&C) parallel applications. We also investigate the extent to which these algorithms could be improved if dynamic load information is available, and how accurate this information needs to be. We show that, for highly-irregular D&C applications, the use of load information can significantly improve application speedups, whereas there is little improvement for less irregular ones. Furthermore, we show that when load information is used, Cluster-aware Random Stealing gives the best speedups for both regular and irregular D&C applications.
KW - Processing Element
KW - Parallel Application
KW - Runtime System
KW - Load Information
KW - Potential Victim
UR - http://www.scopus.com/inward/record.url?scp=84867630252&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32820-6_17
DO - 10.1007/978-3-642-32820-6_17
M3 - Conference contribution
AN - SCOPUS:84867630252
SN - 9783642328190
T3 - Lecture Notes in Computer Science
SP - 155
EP - 166
BT - Parallel Processing - 18th International Conference, Euro-Par 2012, Proceedings
A2 - Kaklamanis, Christos
A2 - Papatheodorou, Theodore
A2 - Spirakis, Paul G.
PB - Springer
CY - Berlin
T2 - 18th International Conference on Parallel Processing, Euro-Par 2012
Y2 - 27 August 2012 through 31 August 2012
ER -