Bounding cache miss costs of multithreaded computations under general schedulers

Richard Cole; Vijaya Ramachandran

doi:10.1145/3087556.3087572

Bounding cache miss costs of multithreaded computations under general schedulers

Richard Cole, Vijaya Ramachandran

Computer Science

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

Abstract

We analyze the caching overhead incurred by a class of multithreaded algorithms when scheduled by an arbitrary scheduler. We obtain bounds that match or improve upon the well-known O(Q + S · (M/B)) caching cost for the randomized work stealing (RWS) scheduler, where S is the number of steals, Q is the sequential caching cost, and M and B are the cache size and block (or cache line) size respectively.

Original language	English (US)
Title of host publication	SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
Publisher	Association for Computing Machinery
Pages	351-362
Number of pages	12
ISBN (Electronic)	9781450345934
DOIs	https://doi.org/10.1145/3087556.3087572
State	Published - Jul 24 2017
Event	29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017 - Washington, United States Duration: Jul 24 2017 → Jul 26 2017

Publication series

Name	Annual ACM Symposium on Parallelism in Algorithms and Architectures
Volume	Part F129316

Other

Other	29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017
Country/Territory	United States
City	Washington
Period	7/24/17 → 7/26/17

Keywords

Cache oblivious
Fork-Join algorithms
Schedulers

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Access to Document

10.1145/3087556.3087572

Cite this

Cole, R., & Ramachandran, V. (2017). Bounding cache miss costs of multithreaded computations under general schedulers. In SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 351-362). (Annual ACM Symposium on Parallelism in Algorithms and Architectures; Vol. Part F129316). Association for Computing Machinery. https://doi.org/10.1145/3087556.3087572

Bounding cache miss costs of multithreaded computations under general schedulers. / Cole, Richard; Ramachandran, Vijaya.
SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2017. p. 351-362 (Annual ACM Symposium on Parallelism in Algorithms and Architectures; Vol. Part F129316).

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

Cole, R & Ramachandran, V 2017, Bounding cache miss costs of multithreaded computations under general schedulers. in SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures. Annual ACM Symposium on Parallelism in Algorithms and Architectures, vol. Part F129316, Association for Computing Machinery, pp. 351-362, 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, Washington, United States, 7/24/17. https://doi.org/10.1145/3087556.3087572

@inproceedings{97bac5f6a1274a7394e4cc3ec210afc9,

title = "Bounding cache miss costs of multithreaded computations under general schedulers",

abstract = "We analyze the caching overhead incurred by a class of multithreaded algorithms when scheduled by an arbitrary scheduler. We obtain bounds that match or improve upon the well-known O(Q + S · (M/B)) caching cost for the randomized work stealing (RWS) scheduler, where S is the number of steals, Q is the sequential caching cost, and M and B are the cache size and block (or cache line) size respectively.",

keywords = "Cache oblivious, Fork-Join algorithms, Schedulers",

author = "Richard Cole and Vijaya Ramachandran",

note = "Publisher Copyright: {\textcopyright} 2017 Copyright held by the owner/author(s).; 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017 ; Conference date: 24-07-2017 Through 26-07-2017",

year = "2017",

month = jul,

day = "24",

doi = "10.1145/3087556.3087572",

language = "English (US)",

series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",

publisher = "Association for Computing Machinery",

pages = "351--362",

booktitle = "SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures",

}

TY - GEN

T1 - Bounding cache miss costs of multithreaded computations under general schedulers

AU - Cole, Richard

AU - Ramachandran, Vijaya

PY - 2017/7/24

Y1 - 2017/7/24

N2 - We analyze the caching overhead incurred by a class of multithreaded algorithms when scheduled by an arbitrary scheduler. We obtain bounds that match or improve upon the well-known O(Q + S · (M/B)) caching cost for the randomized work stealing (RWS) scheduler, where S is the number of steals, Q is the sequential caching cost, and M and B are the cache size and block (or cache line) size respectively.

AB - We analyze the caching overhead incurred by a class of multithreaded algorithms when scheduled by an arbitrary scheduler. We obtain bounds that match or improve upon the well-known O(Q + S · (M/B)) caching cost for the randomized work stealing (RWS) scheduler, where S is the number of steals, Q is the sequential caching cost, and M and B are the cache size and block (or cache line) size respectively.

KW - Cache oblivious

KW - Fork-Join algorithms

KW - Schedulers

UR - http://www.scopus.com/inward/record.url?scp=85027862195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027862195&partnerID=8YFLogxK

U2 - 10.1145/3087556.3087572

DO - 10.1145/3087556.3087572

M3 - Conference contribution

AN - SCOPUS:85027862195

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 351

EP - 362

BT - SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017

Y2 - 24 July 2017 through 26 July 2017

ER -

Bounding cache miss costs of multithreaded computations under general schedulers

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this