Article

Analysis of Randomized Work Stealing with False Sharing

Authors:

Richard Cole,

Vijaya RamachandranAuthors Info & Claims

IPDPS '13: Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing

Pages 985 - 998

https://doi.org/10.1109/IPDPS.2013.86

Published: 20 May 2013 Publication History

Abstract

This paper analyzes the overhead due to false sharing when parallel tasks are scheduled using randomized work stealing (RWS). We obtain high-probability bounds on the cache miss overhead, including the overhead due to false sharing, for several parallel cache-efficient algorithms when scheduled using RWS. These include algorithms for fundamental problems, such as matrix computations, FFT, sorting, basic dynamic programming, list ranking and graph connected components. Our main technical contribution, from which these results follow, is the derivation of nontrivial high-probability bounds on the number of steals incurred by these algorithms in the presence of false sharing, when using RWS.

Cited By

View all

Batista EAlchieri EDotti FPedone F(2022)Early scheduling on steroidsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.02.001163:C(269-282)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.02.001
Goodrich MJacob RSitchinava NMarx D(2021)Atomic power in forksProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458192(2141-2153)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458192
Ramachandran VShi EAgrawal KAzar Y(2021)Data Oblivious Algorithms for MulticoresProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461783(373-384)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461783
Show More Cited By

Recommendations

False Sharing and Spatial Locality in Multiprocessor Caches

The performance of the data cache in shared-memory multiprocessors has been shown to be different from that in uniprocessors. In particular, cache miss rates in multiprocessors do not show the sharp drop typical of uniprocessors when the size of the ...
Reducing False Sharing and Improving Spatial Locality in a Unified Compilation Framework

The performance of applications on large shared-memory multiprocessors with coherent caches depends on the interaction between the granularity of data sharing, the size of the coherence unit, and the spatial locality exhibited by the applications, in ...
Featherlight on-the-fly false-sharing detection
PPoPP '18

Shared-memory parallel programs routinely suffer from false sharing---a performance degradation caused by different threads accessing different variables that reside on the same CPU cacheline and at least one variable is modified. State-of-the-art tools ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IPDPS '13: Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing

May 2013

1255 pages

ISBN:9780769549712

Publisher

IEEE Computer Society

United States

Publication History

Published: 20 May 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Batista EAlchieri EDotti FPedone F(2022)Early scheduling on steroidsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.02.001163:C(269-282)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.02.001
Goodrich MJacob RSitchinava NMarx D(2021)Atomic power in forksProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458192(2141-2153)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458192
Ramachandran VShi EAgrawal KAzar Y(2021)Data Oblivious Algorithms for MulticoresProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461783(373-384)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461783
Yang JHe Q(2018)Scheduling Parallel Computations by Work StealingInternational Journal of Parallel Programming10.1007/s10766-016-0484-846:2(173-197)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s10766-016-0484-8
Cole RRamachandran V(2017)Resource Oblivious Sorting on MulticoresACM Transactions on Parallel Computing10.1145/30402213:4(1-31)Online publication date: 23-Mar-2017
https://dl.acm.org/doi/10.1145/3040221
Chen QGuo M(2015)Locality-Aware Work Stealing Based on Online Profiling and Auto-Tuning for Multisocket Multicore ArchitecturesACM Transactions on Architecture and Code Optimization10.1145/276645012:2(1-24)Online publication date: 8-Jul-2015
https://dl.acm.org/doi/10.1145/2766450
Chen QGuo MGuan HBode AGerndt MStenström PRauchwerger LMiller BSchulz M(2014)LAWSProceedings of the 28th ACM international conference on Supercomputing10.1145/2597652.2597665(3-12)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2597652.2597665

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Recommendations

False Sharing and Spatial Locality in Multiprocessor Caches

Reducing False Sharing and Improving Spatial Locality in a Unified Compilation Framework

Featherlight on-the-fly false-sharing detection

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations