Analysis of randomized work stealing with false sharing

Richard Cole, Vijaya Ramachandran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 27th International Parallel and Distributed Processing Symposium, IPDPS 2013
Pages985-998
Number of pages14
DOIs
StatePublished - 2013
Event27th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2013 - Boston, MA, United States
Duration: May 20 2013May 24 2013

Other

Other27th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2013
CountryUnited States
CityBoston, MA
Period5/20/135/24/13

Keywords

  • false sharing
  • performance analysis
  • Randomized work stealing

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Analysis of randomized work stealing with false sharing'. Together they form a unique fingerprint.

Cite this