Friday 21 June 2013

Amdahl's law and the root of all evil

Introduction


In the blog post "Why shared mutable state is the root of all evil." I was trying to explaining why it is important to use proper synchronization while accessing shared-mutable state in your concurrent programs to make sure they behave like expected. What I didn't get around to was talking about reasons why this synchronisation is so bad for performance and therefore the root of all evil for performance optimization.

Speedup


One performance measure is the speed-up of a programme. The speed-up basically compares the time a programme takes when executed one a single core to the time it takes to execute on multiple cores.



To calculate the speed-up (S2) on a dual core system simply measure the time to execute on a single core (T1) and divide to the execution time of on a dual core (T2).

For example if you are running a single-threaded program it doesn't matter how many cores your host system will have. The execution time will stay roughly constant and additional available cores will remain unused and idle. The speed-up therefore will be always one.

If you are running a perfectly parallelizable program on a dual core system the execution time will be exactly half the time than for a single processor system. In this case the program has a speed-up of 2. In cases where the program speed-up grows linear with the number of cores you add to the system we call it a "linear speed-up". That kind of speed-ups are the ideal.

In practise these kind of speed-ups are really rare and this is due to Amdahl's law.


Amdahl's law

What Amdahl's law basically says is that the maximal possible speed-up of a is determined by the part of the program which cannot run in parallel. For example this means if 50% of your algorithm are structured in a way they can't run by multiple threads then the maximal speed-up you will ever be able to achieve is 2. Say this algorithm would take 1 minute to execute on a single threaded system. If you optimize the heck out of your host system and let the algorithm run on with 100 threads you would be able to reduce the timing for the parallel (50%) part of the algorithm by factor 100. You still would be stuck with the single-threaded (50%) part of the algorithm which doesn't benefit from the additional threads. In the end the best you can ever achieve is a runtime of 30 seconds.

Below is a nice graph from wikipedia showing this law for different percentages of parallel proportions of the algorithm.


You can see that the different coloured graphs all flatten out after a while. Adding more threads to the equation doesn't result in any benefits any more. Even for an algorithm with 95% parallel proportion the maximal speed-up you can ever achieve is 20.

In practise having the algorithm run with a large number of threads is actually likely to reduce the speed-up again. This is due to the cost of multi-threading in the operating system like context switching.



What does this mean for my programs?

Like I tried to explain in my blog post "Free lunch for programers" the time of easy performance gains is over and only parallel programs will benefit from future advances in computer hardware. But because of Amdahl's law even parallel programs are very limited in its potential performance gains due to its non-parallel sections.

So in a way we have two conflicting forces: Safety and Performance. You need to use synchronization to make your concurrent programs correct and safe but by introducing synchronization you are installing so called critical sections which are essentially single-threaded and therefore harming performance.

By minimizing shared mutable state you can reduce the amount of synchronization used in your programs and therefore enable them to a higher performance.

Conclusion

Shared mutable state really is the root of all evil. Eliminate it wherever possible and your live as a developer will be a lot easier.


27 comments:

  1. Gun Shot Strike Mod Apk is a new action capturing game. Is a globe loaded with dealing with as well as glory? Every element of the video game will make you really feel shocked. Now that you are an expert battle task force shooter, your goal is to damage all opponents. Hold your weapon and locate the terrorists around you through the radar.

    They do not know your presence, yet when you start Gun Shot Strike Mod Apk the adversary will find your presence, so be extremely careful. Attention to the enemy’s strike, to shield their very own safety. mission accomplished. Depending on the degree of Gun Shot Strike Mod Apk Unlimited Money and AI, you will encounter a number of obstacles. The world’s best multiplayer Basketball Stars Mod Apk No Root facilitate on reduced, from the makers of different raving accomplishment online redirections excitements! Sniper Killer Shooter Mod Apk is the really amazing game with the high graphics and setting with this you can play the game easily and without any hesitation so this game includes many features and the moded version has also

    Now you have a new mission! A terrorist team has occupied the S city, pirating innocent guests as hostages. As an excellent mercenary and also your goal is to eliminate all the terrorists and rescue the hostages. Here you require a cool head abnormality evaluation and quickly, aggressive, precise shooting methods, permit your head to cool down, to enjoy this tough video game now!

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Good blog information
    Sanjary Kids is one of the best play school and preschool in Hyderabad,India. Give your child the best preschool experience by choosing the best playschool of Hyderabad in Abids. we provide programs like Play group,Nursery,Junior KG,Senior KG,and provides Teacher Training Program.
    pre and primary teacher training course in hyderabad

    ReplyDelete
  4. Good blog posting information of the topic

    Sanjary Academy is the best Piping Design institute in Hyderabad, Telangana. It is the best Piping design Course in India and we have offer professional Engineering Courses like Piping design Course, QA/QC Course, document controller course, Pressure Vessel Design Course, Welding Inspector Course, Quality Management Course and Safety Officer Course.
    Piping Design Course
    Piping Design Course in Hyderabad ­
    Piping Design Course in India­

    ReplyDelete
  5. Thank you so much sharing this beautiful post.
    It is very helpful for us.
    tezlyrics.com

    ReplyDelete
  6. Excellent explanation of the blog posts I liked it

    Sanjary Academy provide pressure vessel design, quality management system course piping design course, qa/qc course and document controller course.
    Welding Inspector Course
    Safety officer course
    Quality Management Course
    Quality Management Course in India

    ReplyDelete
  7. Thanks for the informative article. This is one of the best resources I have found in quite some time. Nicely written and great info. I really cannot thank you enough for sharing.
    Data Science Online Training | Data Science Online Certification |Learn Data Science Course

    ReplyDelete
  8. good information
    "Sanjary Academy provides excellent training for Piping design course. Best Piping Design Training Institute in Hyderabad,
    Telangana. We have offer professional Engineering Course like Piping Design Course,QA / QC Course,document Controller
    course,pressure Vessel Design Course, Welding Inspector Course, Quality Management Course, #Safety officer course."
    Piping Design Course in India­
    Piping Design Course in Hyderabad
    Piping Design Course in Hyderabad
    QA / QC Course
    QA / QC Course in india
    QA / QC Course in Hyderabad
    Document Controller course
    Pressure Vessel Design Course
    Welding Inspector Course
    Quality Management Course
    Quality Management Course in india
    Safety officer course

    ReplyDelete

  9. 1croreprojects offersmobile computing projects chennai We list heaps of IEEE Final Year Studies (CSE, ECE, IT, EEE) projects.

    ReplyDelete
  10. 1croreprojects offersieee 2019 power system, electronics projects We list heaps of IEEE Final Year Studies (CSE, ECE, IT, EEE) projects.

    ReplyDelete
  11. We as a team of real-time industrial experience with a lot of knowledge in developing applications in python programming (7+ years) will ensure that we will deliver our best in python training in vijayawada. , and we believe that no one matches us in this context.

    ReplyDelete
  12. Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care
    http://chennaitraining.in/creo-training-in-chennai/
    http://chennaitraining.in/building-estimation-and-costing-training-in-chennai/
    http://chennaitraining.in/machine-learning-training-in-chennai/
    http://chennaitraining.in/data-science-training-in-chennai/
    http://chennaitraining.in/rpa-training-in-chennai/
    http://chennaitraining.in/blueprism-training-in-chennai/

    ReplyDelete
  13. It is amazing and wonderful to visit your site.Thanks for sharing this information,this is useful to me...
    http://chennaitraining.in/etl-testing-training-in-chennai/
    http://chennaitraining.in/java-training-in-chennai/
    http://chennaitraining.in/python-training-in-chennai/
    http://chennaitraining.in/r-programming-training-in-chennai/
    http://chennaitraining.in/salesforce-developer-training-in-chennai/
    http://chennaitraining.in/sap-hana-training-in-chennai/

    ReplyDelete
  14. Nice information. I’ve bookmarked your site, and I’m adding your RSS feeds to my Google account to get updates instantly.

    App development
    software developer

    ReplyDelete
  15. Nice information. I’ve bookmarked your site, fue turkey

    ReplyDelete
  16. They are very useful article. I like your post. Thanks for sharing your information. Fashion Designer Boutique in Mumbai

    ReplyDelete
  17. This is the one of the most important information for me. And I am feeling glad reading your article. The article is really excellent ?

    cusat university time table

    ReplyDelete
  18. Henrik Eichenhardt'S Blog: Amdahl'S Law And The Root Of All Evil >>>>> Download Now

    >>>>> Download Full

    Henrik Eichenhardt'S Blog: Amdahl'S Law And The Root Of All Evil >>>>> Download LINK

    >>>>> Download Now

    Henrik Eichenhardt'S Blog: Amdahl'S Law And The Root Of All Evil >>>>> Download Full

    >>>>> Download LINK eX

    ReplyDelete
  19. Get the complete information about Philippines Import Export trade Data by Philippines Eximp for USA, Russia, United Kingdom, France and more countries.
    Philippines Import Data

    ReplyDelete