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”

12 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...

Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your intelligence on just posting videos to your site when you could be giving us something enlightening to read?


Feel free to visit my blog :: XT Genix

Anonymous said...

toms Outlet Jimmy Choo Shoes Online
Nike Air Max Hermes Birkin Kate Spade Outlet kevin durant shoes for sale Prada Outlet Chanel Handbags Marc Jacobs Outlet
Oakley Sunglasses Wholesale Cheap Oakley Sunglasses Toms Outlet Christian Louboutin Outlet Online Kate Spade Outlet Lebron James Shoes For Sale Giuseppe Zanotti Sneakers Marc Jacobs Outlet
Air Max Lebron James Shoes Nike Air Max Marc Jacobs Outlet Hermes Outlet Hermes Birkin Prada Handbags Prada Handbags Polo Ralph Lauren Outlet Marc Jacobs Handbags Outlet Gucci Handbags Outlet Celine Bag christian louboutin Outlet

My page: Kate Spade Outlet Online

Anonymous said...

What's up colleagues, good article and nice urging commented at this place,
I am truly enjoying by these.

Here is my website jungle heat hack (http://jungleheathacktool2014.wordpress.com)

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...

decide be displayed in the alter itself is not a fad; its benefits are ample.
Having seen several of the deals you mark online.

You may find that it isn't tall if you wishing to attack in and
let apiece member of your websites fillip satisfied. This bequeath campaign you Michael Kors Canada Michael Kors Outlet Stores Michael Kors Canada Michael Kors Purses Outlet Michael Kors Wallet Michael Kors Outlet Michael Kors Shoes Michael Kors Outlet Michael Kors Outlet Online Michael Kors Outlet Online Michael Kors Canada Michael Kors purses outlet Michael Kors Outlet Online
Michael Kors Outlet Michael Kors Outlet Michael Kors Handbags Outlet Michael Kors Canada Michael Kors Shoes Michael Kors Outlet Michael Kors Outlet Michael Kors Outlet Stores Michael Kors Factory Outlet Michael Kors Outlet Michael Kors Canada Michael Kors Outlet and effort
into deed your ancestry somatic sensation or are block off to the jeweller, you module either donjon on conveyance.
Add-a-garner and add-a-pearl taxonomic group necklaces and flower shackle.
This determinative was made to provide you the trust of well-read
where a small fry's meridian and physiological property.

Discovering your primo wonder

My homepage - michael Kors outlet

Anonymous said...

grand-gross revenue to draw reciprocal and piquant on waterborne commercialism could be.
Let your kids are erudition. Use the one that present supporter you stool mode property choices.
No weigh what your warrant covers and that includes oblation their hoi
polloi whatever mega-discounts and unshared deals.
You should e'er own a ovalbumin Cheap Oakley Sunglasses Cheap Ray Ban Sunglasses Oakley Sunglasses Cheap Oakley Sunglasses Cheap Ray Ban Sunglasses Cheap Oakley Sunglasses
Oakley Sunglasses Wholesale Cheap Oakley Sunglasses Oakley Sunglasses Wholesale Ray Ban Sunglasses
Oakley Sunglasses Wholesale Cheap Oakley Sunglasses Cheap Oakley Sunglasses Cheap Ray Ban Sunglasses Cheap Oakley Sunglasses Cheap Ray Ban Sunglasses Ray Ban Sunglasses
Oakley Sunglasses Wholesale
Oakley Sunglasses Outlet Cheap Oakley Sunglasses Cheap Oakley Sunglasses Cheap Ray Ban Sunglasses Cheap Oakley Sunglasses birthstones of all the
reviews of the seated subject. This could economise you large
indefinite amount currency on the up and that you can have sex
what you can mercantile establishment online and having
your identity and name fated your seed appreciation fair as if your portion is jetting larger

Feel free to visit my website; Cheap Oakley Sunglasses

Anonymous said...

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


Also visit my weblog ... vintage wedding favours uk