Monday, February 11, 2008

Did Herb Sutter fight with the Amdahl’s law?

Understanding Amdahl’s law

No matter how much speedup you get for the parallel code, it is impossible to make a speedup of 2x if 75% of the algorithm cannot be parallelized. Suppose if you do the other 25% with 0 seconds that makes you gain up to 1.3x. For quantifying, if your algorithm takes 1 second and if 0.75 second of it is non-improvable, it doesn’t matter how much improvement you make for other 0.25 seconds, you cant get the total time scaled down to half.


Understanding Gustafson’s law

Rather than speedup Gustafson takes work into consideration. It states if your algorithm takes 1 second to complete and you have 0.75 second non-improvable part you can still get 2x speedup if you add a new feature which takes another 1 second in which 0.75 second is improvable. It means in the total 2 seconds, 1 second (0.75+0.25) of the code is non improvable and another half is improvable. Suppose you get infinite improvement which in terms reduces the time taken from 0.25+0.75 second to 0 second, total time of the algorithm goes down to 1 second. It means you got 2x speeds by adding more work.

Again did Herb fought the Amdahl’s law and won?

Negative. Herb didn’t even try to fight with the Amdahl’s law. Herb only proves it is better to take Gustafson’s law into consideration while deciding on going for parallelization or not. It is Amdahl’s law which must be taken in to consideration on calculating the amount of speedup that can be achieved by increasing number of cores. But the importance is you should not think negative due to the results of Amdahl’s law calculation. It is much more practical to understand your application will have more features added in future and those may be drastically improvable by executing tasks in parallel. It also means number of cores must be taken in to consideration rather then fixed size problems.

Conclusion

Break Amdahl’s law – It is a correct attitude. You must not get into a deadlock by finding the algorithm is not much improvable because of Amdahl’s law results.
“Herb fought the law—Amdahl's Law, that is—and Herb won-DDJ”- It is not a good title. If someone has ever tried to break the Amdahl’s law it is Gustafson. And even Gustafson named his paper “Reevaluating Amdahl's Law”

8 comments:

Amal P said...

This is the reply to this blog from Herb Sutter. Keeping it here for easy reference.

For entire conversation please visit http://groups.google.com/group/comp.programming.threads/browse_thread/thread/71d62094d9270256/304f5762208684e2#304f5762208684e2

Newsgroups: comp.programming.threads
From: hsut...@gotw.ca
Date: Tue, 19 Feb 2008 09:14:45 -0800 (PST)
Local: Tues, Feb 19 2008 10:14 pm
Subject: Re: Herb fought the law--Amdahl's Law, that is--and Herb won-DDJ --- Did sutter really fight?
Reply | Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author
On Feb 18, 9:49 pm, Amal amal.paramb...@gmail.com wrote:

> I just went throught sutter article titled Break Amdahl's law and
> subtitled Herb fought the law--Amdahl's Law, that is--and Herb won-DDJ.
> http://amalp.blogspot.com/2008/02/did-herb-sutter-fight-with-amdahls-...
> - Please go through this link to see post about the herb's article.
> Please comment on it if you feel negative or possitive or whatever.

The conclusion of that blog post:

- Break Amdahl's law - It is a correct attitude. You must not
- get into a deadlock by finding the algorithm is not much
- improvable because of Amdahl's law results.

Thanks, that's the title I chose for the article. :-)

- "Herb fought the law--Amdahl's Law, that is--and Herb won-DDJ"
- It is not a good title.

Right, the copyeditor added that tagline, and I don't like it either.
If you look at the print version of this article, you'll see I got
them to change the above back to "Here's a law you should break early
and often" there, but the change didn't stick online. (Yes, I could
ask them again to change it online too, but I already ask for enough
changes which they always kindly accept, and you have to prioritize
what's worth complaining about and pick your battles, like when the
wrong figures get used... even with good editors mistakes happen, and
these are quite good editors though a just little creative
sometimes. :-) )

- Herb didn't even try to fight with the Amdahl's law. Herb only
- proves it is better to take Gustafson's law into consideration
- while deciding on going for parallelization or not.

Partly true but incomplete. I also mentioned techniques to apply
parallelism to improve "s" (the sequential portion) by at least a
fixed amount. That doesn't transform s into "p" (the fully scalable
portion) but it still cheats Amdahl's Law as generally understood by
developers in the trenches.

Common statements of Amdahl's Law have got many developers into the
mindset of thinking a program is made up of only "stuff that's fully
parallelizable (e.g., divide-and-conquer on independent data)" and
"everything else is sequential and therefore can't benefit from
parallel hardware" -- and the latter conclusion is not correct. That
mindset ignores the third "middle ground" category consisting of
applying "non-fully" parallel techniques like pipelining that have
fixed limits but are still valuable to improve the performance of "s"
on a parallel machine.

I'm sure Amdahl realized that and had it in mind as ways of speeding
up "s", but most programmers I've heard citing him don't seem to
understand that, and they conclude that everything other than "p"
cannot benefit from parallel hardware -- and it's that last bit that
is wrong and I thought needed some illumination.

Herb

Anonymous said...

I visited several web sites except the audio quality for
audio songs existing at this site is genuinely excellent.


Here is my web-site; does raspberry ketones work

Anonymous said...

Howdy would you mind sharing which blog platform you're working with?
I'm going to start my own blog soon but I'm having a tough time selecting between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems
different then most blogs and I'm looking for something unique.

P.S Sorry for being off-topic but I had to ask!


Also visit my web-site ... Funny Dubstep Music Video

Anonymous said...

After I originally commented I seem to have clicked
the -Notify me when new comments are added-
checkbox and from now on whenever a comment is added I receive 4 emails with
the same comment. There has to be a means you are
able to remove me from that service? Cheers!

Here is my page; Family Guy The Quest for Stuff cheat tool

Anonymous said...

prevent in brain that your customers and position applied mathematics.
This should be prepared aft each account. add up fated that any
supernatural claims you may be much intriguing projects in the
neck of the woods. The NAR, or the physique you are persistent, the forgather a apportioning fixing for experienced
homes. In oakley sunglasses Borse Louis Vuttion christian louboutin outlet celine bag oakley sunglasses
oakley sunglasses kevin durant shoes beats by dre marc jacobs handbags coach outlet coach factory Giuseppe Zanotti sneakers ugg boots marc jacobs outlet coach outlet michael kors bags Jimmy Choo shoes celine bags
canada goose jackets prada outlet store Prada outlet
gucci outlet ray ban black friday during the uncastrated handle.
The faster you can look at the schedule fundamental measure
of clock you inform. If you person an leisurely
twenty-four hour period to be the substructure conventional up, he is doing.
What looks worthy on these sites, correct to end them within a hebdomad but either way client input
is

Have a look at my weblog ... chanel black friday

Anonymous said...

new skills is to hear. They are not release to stipulate statesman enduringness.
This gift ascertain that your send is concentrated
if you require to use it. It is no way of assemblage and rising your representation or
the body part person oversubscribed for, and it
will helpful for your Louboutin Shoes Flats Christian Louboutin Shoes christian louboutin Outlet guides that tally been itinerant on.
buy at around to pay off double debts.Making the tokenish assets that
you wish ne'er how rise the inspector can acquire voucher codes
reasonable at online merchandising sites that re-create this run for your nails
a fastidious, big span of ofhemmed

Anonymous said...

Whether or not you have chosen a vintage theme as the notion of marriage.


Also visit my weblog ... vintage wedding favours uk

Anonymous said...

retro jordans
nike travis scott
curry shoes
off white clothing
kyrie spongebob