Improving the Correct Things: Amdahl’s Law

Improving the Correct Things: Amdahl’s Law

I see a lot of people in the world trying to optimise the wrong things.

During one of the undergraduate Computer Science courses at Cambridge (about parallelisation of processes) we learnt about Amdahl’s law. Essentially, it helps you improve the efficiency of a project by identifying the parts that can cause the best speedup.

The law demonstrates that improving the most time consuming tasks by a little can cause more benefit than improving smaller tasks a lot. Something that can be quite obvious when you think about it, but people rarely consider when trying to complete a project.

This is probably better understood with a real life example:

A group of my friends were organising a dinner at a nice pub offering a deal on a burger and chips for £7.50 instead of the £10.50 it would normally cost. One friend said he didn’t want to go because it was too expensive. I then suggested McDonald’s instead, but he retorted saying that it was too expensive. Burger King was where he wanted to go, apparently for the price.

It is probably about £4 for a meal deal from Burger King and around the same price at McDonald’s, if not cheaper.

Obviously I have no issue with people wanting to save money. In actual fact I think more people should think of the long term and save more than they do – but that is a separate topic.

My problem is that this particular person would then go to the bar and spend A LOT on alcohol. He would do this regularly – I mean about £20-£25 a night in the student bar. If he just took one night off the drinking he would easily be able to come to the much nicer pub with his friends (only an extra £3.50! – but of course we haven’t talked about the return that he gets from drinking which perhaps is part of the issue).

(non-geeks look away) Amdahl’s law states that the maximum speedup of a computation is limited by the amount of the algorithm that must be serial. That is to say, if you must put some time into one bit, then it will limit how quickly you could get the whole task done.

The law extends to the summation of all of the sub-task’s time, indicating that an improvement is best applied to the most time consuming task.

Amdahl's Law Speedup
B is the fraction of the algorithm that is strictly serial.
n is the number of threads
T(n) is the time it takes to complete with n threads.

I extend this to real life with respect to many things. For example, getting 10% off your rent for a year saves you a lot more money than getting 50% off one meal. It might be easier to haggle a 10% discount from your landlord than searching for vouchers online for hours to get 50% off a meal in a restaurant.

Assume that a task has two independent parts, A and B. B takes roughly 25% of the time of the whole computation. By working very hard, one may be able to make this part 5 times faster, but this only reduces the time for the whole computation by a little. In contrast, one may need to perform less work to make part A be twice as fast. This will make the computation much faster than by optimizing part B, even though B's speed-up is greater by ratio, (5× versus 2×).
Assume that a task has two independent parts, A and B. B takes roughly 25% of the time of the whole computation. By working very hard, one may be able to make this part 5 times faster, but this only reduces the time for the whole computation by a little. In contrast, one may need to perform less work to make part A be twice as fast. This will make the computation much faster than by optimizing part B, even though B’s speed-up is greater by ratio, (5× versus 2×).

It actually quite upsets me when people are inconsistent in this respect. This law can help to explain my frustration where people focus too much on trying to make the small things more efficient, but forget about the bigger picture.

There are many examples I can think of when people spend a lot of money during a night out: on food, drink and cigarettes, but will not share a cab home for £5 each; instead taking the tube for £2. The £3 saving being very little in comparison to the money they spent earlier in the evening.

Another clear example is when people go on vacation, usually spending in the region of £500-£1000 for a week’s holiday; then insisting on spending hours haggling at a street market over 20 pence for a piece of tourist memorabilia. I enjoy haggling as much as anyone else, but I wouldn’t walk away from a cheap gift because a market seller wouldn’t move on 20 pence which means a lot to them, but not as much to me. I certainly wouldn’t be upset if the guy didn’t actually sell me the item for the price I wanted, considering the amount I just paid for the whole trip!

Bottom line: don’t worry about trying to improve the smaller things by a lot – they won’t give you anywhere near as good a result as improving the bigger things by a little.

Comments are closed.