Yes, mowing ones lawn and HPC have much in common

In many of my previous columns I mentioned Amdahl's Law -- the golden rule of parallel computing. Before you click away, rest assured I have no intention of talking 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, multi-core, and other such over worked topics. In this article, I’ll discuss lawn care.

Like most home owners, I have a lawn. A most-of-the-year green thing that provides a large bathroom for my dogs 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 triple-blade units that would work much faster by cutting a bigger swath. They still only cut one swath at a time, so the speed-up would not be all that great. Then it hits me, what I need is a swarm of these green machines and a crew of experienced yard-men 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 speed-up. 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 speed-up estimates. In reality, there is task of co-ordinating the team of parallel lawnmowers. The co-ordination 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:

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 2-3 days for two people with two tractors to do the entire course. We each pulled a 9-way 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 speed-up 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 multi-worker 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, but don't let him drive your John Deere.

This article was originally published in Linux Magazine. It has been updated and formatted for the web. If you want to read more about HPC clusters and Linux, you may wish to visit Linux Magazine. (Note: Since 2011 Linux Magazine has ceased posting new articles)

You have no rights to post comments