Ghent University Academic Bibliography

Advanced

Modeling critical sections in Amdahl's law and its implications for multicore design

Stijn Eyerman and Lieven Eeckhout UGent (2010) Conference Proceedings Annual International Symposium on Computer Architecture. p.362-370
abstract
This paper presents a fundamental law for parallel performance: it shows that parallel performance is not only limited by sequential code (as suggested by Amdahl’s law) but is also fundamentally limited by synchronization through critical sections. Extending Amdahl’s software model to include critical sections, we derive the surprising result that the impact of critical sections on parallel performance can be modeled as a completely sequential part and a completely parallel part. The sequential part is determined by the probability for entering a critical section and the contention probability (i.e., multiple threads wanting to enter the same critical section). This fundamental result reveals at least three important insights for multicore design. (i) Asymmetric multicore processors deliver less performance benefits relative to symmetric processors than suggested by Amdahl’s law, and in some cases even worse performance. (ii) Amdahl’s law suggests many tiny cores for optimum performance in asymmetric processors, however, we find that fewer but larger small cores can yield substantially better performance. (iii) Executing critical sections on the big core can yield substantial speedups, however, performance is sensitive to the accuracy of the critical section contention predictor.
Please use this url to cite or link to this publication:
author
organization
year
type
conference (proceedingsPaper)
publication status
published
subject
keyword
critical sections, synchronization, Analytical performance modeling, Amdahl's law
in
Conference Proceedings Annual International Symposium on Computer Architecture
issue title
ISCA 2010 : the 37th annual international symposium on computer architecture
pages
362 - 370
publisher
Association for Computing Machinery (ACM)
place of publication
New York, NY, USA
conference name
37th Annual international symposium on Computer Architecture (ISCA 2010)
conference location
Saint-Malo, France
conference start
2010-06-19
conference end
2010-06-23
Web of Science type
Proceedings Paper
Web of Science id
000287049300036
ISSN
1063-6897
ISBN
9781450300520
9781450300537
DOI
10.1145/1815961.1816011
language
English
UGent publication?
yes
classification
P1
copyright statement
I have transferred the copyright for this publication to the publisher
id
1024596
handle
http://hdl.handle.net/1854/LU-1024596
date created
2010-08-17 11:25:29
date last changed
2017-01-02 09:52:19
@inproceedings{1024596,
  abstract     = {This paper presents a fundamental law for parallel performance: it shows that parallel performance is not only limited by sequential code (as suggested by Amdahl{\textquoteright}s law) but is also fundamentally limited by synchronization through critical sections. Extending Amdahl{\textquoteright}s software model to include critical sections, we derive the surprising result that the impact of critical sections on parallel performance can be modeled as a completely sequential part and a completely parallel part. The sequential part is determined by the probability for entering a critical section and the contention probability (i.e., multiple threads wanting to enter the same critical section).
This fundamental result reveals at least three important insights for multicore design. (i) Asymmetric multicore processors deliver less performance benefits relative to symmetric processors than suggested by Amdahl{\textquoteright}s law, and in some cases even worse performance. (ii) Amdahl{\textquoteright}s law suggests many tiny cores for optimum performance in asymmetric processors, however, we find that fewer but larger small cores can yield substantially better performance. (iii) Executing critical sections on the big core can yield substantial speedups, however, performance is sensitive to the accuracy of the critical section contention predictor.},
  author       = {Eyerman, Stijn and Eeckhout, Lieven},
  booktitle    = {Conference Proceedings Annual International Symposium on Computer Architecture},
  isbn         = {9781450300520},
  issn         = {1063-6897},
  keyword      = {critical sections,synchronization,Analytical performance modeling,Amdahl's law},
  language     = {eng},
  location     = {Saint-Malo, France},
  pages        = {362--370},
  publisher    = {Association for Computing Machinery (ACM)},
  title        = {Modeling critical sections in Amdahl's law and its implications for multicore design},
  url          = {http://dx.doi.org/10.1145/1815961.1816011},
  year         = {2010},
}

Chicago
Eyerman, Stijn, and Lieven Eeckhout. 2010. “Modeling Critical Sections in Amdahl’s Law and Its Implications for Multicore Design.” In Conference Proceedings Annual International Symposium on Computer Architecture, 362–370. New York, NY, USA: Association for Computing Machinery (ACM).
APA
Eyerman, S., & Eeckhout, L. (2010). Modeling critical sections in Amdahl’s law and its implications for multicore design. Conference Proceedings Annual International Symposium on Computer Architecture (pp. 362–370). Presented at the 37th Annual international symposium on Computer Architecture (ISCA 2010), New York, NY, USA: Association for Computing Machinery (ACM).
Vancouver
1.
Eyerman S, Eeckhout L. Modeling critical sections in Amdahl’s law and its implications for multicore design. Conference Proceedings Annual International Symposium on Computer Architecture. New York, NY, USA: Association for Computing Machinery (ACM); 2010. p. 362–70.
MLA
Eyerman, Stijn, and Lieven Eeckhout. “Modeling Critical Sections in Amdahl’s Law and Its Implications for Multicore Design.” Conference Proceedings Annual International Symposium on Computer Architecture. New York, NY, USA: Association for Computing Machinery (ACM), 2010. 362–370. Print.