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

Vladimir Janjic; Kevin Hammond

doi:10.1007/978-3-642-32820-6_17

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

Vladimir Janjic, Kevin Hammond

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English
Title of host publication	Proc. EuroPar 2012: 2012 International European Conference on Parallel and Distributed Computing
Publisher	Springer
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-32820-6_17
Publication status	Published - 2012

Access to Document

10.1007/978-3-642-32820-6_17

EP/F030657/1 Adaptive Hardware Systems: Copy of Adaptive Hardware Systems with Novel Algorithmic Design and Guaranteed Resource Bounds
Hammond, K. (PI)
EPSRC
1/09/08 → 31/08/11
Project: Standard

Cite this

@inproceedings{52da807e6a8d446a825a7f5a26804a2e,

title = "Using Load Information in Work-Stealing on Distributed Systems with Non-Uniform Communication Latencies",

abstract = "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.",

author = "Vladimir Janjic and Kevin Hammond",

year = "2012",

doi = "10.1007/978-3-642-32820-6_17",

language = "English",

booktitle = "Proc. EuroPar 2012: 2012 International European Conference on Parallel and Distributed Computing",

publisher = "Springer",

address = "Netherlands",

}

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 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.

AB - 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.

U2 - 10.1007/978-3-642-32820-6_17

DO - 10.1007/978-3-642-32820-6_17

M3 - Conference contribution

BT - Proc. EuroPar 2012: 2012 International European Conference on Parallel and Distributed Computing

PB - Springer

ER -

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

Abstract

Access to Document

Fingerprint

Projects

EP/F030657/1 Adaptive Hardware Systems: Copy of Adaptive Hardware Systems with Novel Algorithmic Design and Guaranteed Resource Bounds

Cite this