Now with 100% less calculus.
In my previous column I mentioned Amdahl’s Law. Before you click away, rest assured I have no intention to talk specifically about Amdahl’s Law and I promise not to place a single equation or derivation in this column. Often times people are put off by Amdahl’s law. Such discussions usually start with an equation and talk of the limit as N
goes to infinity. Not to worry. There are no formulas, no esoteric terms (sorry, no big words), just the skinny on the limits of parallel computing. I’ll even go one further, I’ll hardly mention parallel computers, multicore, and other such over worked topics. This month’s I’ll discuss lawn care.
Like most home owners, I have a lawn. A mostoftheyear green thing that provides a large bathroom for my dog and lots of work for me. Having recently climbed the lawn care ladder, I am now a the proud owner of a John Deere lawn tractor/mower. My new ride has given me the luxury of sitting while mowing and the opportunity for deep thought. Yes, there is much to ponder while riding upon the pinnacle of suburban achievement. Ah, but I digress.
While my green and yellow lawn Harley makes quick work of my grass and weeds, I often think, while mowing, how could I do this faster? Of course, the obvious answer is get a bigger mower. There are those larger tripleblade units that would work much faster by cutting a bigger swath. They still only cut one swath at a time, so the speedup would not be all that great. Then it hits me, what I need is a swarm of these green machines and crew of experienced yardmen like myself. But wait, what about the edges. I use a push mower for the edges after I am done with the big area. And, there is no sense in doing the edges until the big areas are done, just in case some tight spots were missed by the riding mower. I am also going to make a perfectly valid, but nonsensical, assumption that there is only one push mower available.
How fast can I mow the lawn with a team of riding mowers and one push mower? Let’s take a look at some numbers. Assume it takes me 60 minutes to do the entire yard (riding and pushing). The push mower takes 20 minutes and the riding takes 40 minutes. If I get ten riding mowers and drivers, I should be able to give everyone equal areas to cut and get the big area done in a remarkable 4 minutes. But then, I have to do the edges with the push mower. That adds 20 minutes for a total of 24 minutes. Much better than 60 minutes, but still I could do better. Let’s suppose I use 40 riding mowers. Using the same analysis, I get the yard done in 21 minutes. What if I use 100 mowers? As you can see the slow step is limiting my speedup. The result sounds familiar to something that Gene Amdahl proposed: The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program.
Indeed, just as with parallel processors, there is a point of diminishing return. Adding the first 10 riding mowers reduced the time by 36 minutes. Adding another 30 only saved me 4 minutes. Adding 100 mowers makes little sense since I’ll never get below 20 minutes. (Although I would love to see such a lawn mowing demolition derby — in my neighbors yard of course.)
Taking a closer look, I think I have been too generous with my speedup estimates. In reality, there is task of coordinating the team of parallel lawnmowers. The coordination includes getting them to onto the lawn and in to the right starting position, telling them where to mow, and then getting them off the lawn. Thus, there is going to be some overhead required. The overhead takes time, lets assume 1 minute per additional riding mower. Therefore, adding 10 mowers will require 10 minutes of overhead and using 40 mowers will require 40 minutes of overhead. The new numbers look like this:
Riding Mowers 
1 
10 
40

Parallel mow time 
40 
4 
1 
Parallel setup time 
0 
10 
40 
Push mower time 
20 
20 
20 
Total time 
60 
34 
61 
Wait a minute (pun intended). Using 40 riding mowers takes longer than using one! How can this happen. Simple, the overhead adds to the sequential portion of the job. A sequential portion that was not there when one mower was used. Remember that little tidbit when thinking about parallel programming. Even though the 40 riding mowers get done in one minute, they still need to be “setup” to mow.
Based on the above analysis, one may think that this whole parallel thing is a waste of time. In some cases it is. I doubt I’ll never need more than one riding mower. If I had to mow an entire golf course, then 40 riding mowers might make sense because the problem is now bigger. (And, yes they use huge gang mowers on golf courses. I used to pull such a device. It would take 23 days for two people with two tractors to do the entire course. We each pulled a 9way gang mower unit. That is about the equivalent of 18 riding mowers working at the same time.)
Finally, I assume you are wondering, What is the Lawnmower Law? It has nothing to with what I have been talking about. The above discussion is Amdahl’s law. The amount of speedup you can expect is limited to the sequential portion of your code plus the parallel overhead. It turns out it is general rule that can be applied to almost multiworker situation. What about the Lawnmower Law? Glad you asked. Here it is: When you need to mow the lawn, get the neighbor kid to do it.
Comments on "The Lawnmower Law"
Excellent article– Describing Amdahl’s law in terms of mowing lawns was most enlightening!
Thanks!
“donpar”
That is such a good analogy â€“ it makes the subject clear: thanks!
Nicely done.
I love these parallel articles, and I understood Amdahl’s law quite alright previous to this article…but, now I fully understand why I must keep on mowing the lawn by myself. In addition to hitting the wall with mowing time, you also run into monetary problem. With each lawnmower you add your mowing cost increases substantially. It might take you 60 minutes to mow the lawn, but you already own the push mower and the riding mower…how much do you have to pay the 240 kids who are going to help?
I’m excited to find this great site. I wanted to thank you
for your time just for this fantastic read!! I definitely really liked every part of it and
i also have you bookmarked to see new stuff on your site.