Modeling the Mythical Man-Month

---

This article was originally posted in 2007. When I updated the image today (in 2014), it reappeared with the more recent date and I don't know how to override that (wrong) timestamp. This seems to be a bug in Blogger.

---

In the aftermath of a discussion about software management, I looked up the Mythical Man-Month concept on Wikipedia. The main thesis of Fred Brooks, often referred to as "Brooks's law [sic]," can simply be stated as:

Adding manpower to a late software project makes it later.

In other words, some number of cooks are necessary to prepare a dinner, but adding too many cooks in the kitchen can inflate the delivery schedule.

Sex, Lies and Log Plots

From time to time, at the Hotsos conferences on Oracle performance, I've heard the phrase, "battle against any guess" (BAAG) used in presentations. It captures a good idea: eliminate guesswork from your decision making process. Although that's certainly a laudable goal, life is sometimes not so simple; particularly when it comes to performance analysis. Sometimes, you really can't seem to determine unequivocally what is going on. Inevitably, you are left with nothing but making a guess—preferably an educated guess, not a random guess (the type BAAG wants to eliminate). As I say in one of my Guerrilla mantras: even wrong expectations (or a guess) are better than no expectations. In more scientific terms, such an educated guess is called a hypothesis and it's a major way of making scientific progress.

Of course, it doesn't stop there. The most important part of making an educated guess is testing its validity. That's called hypothesis testing, in scientific circles. To paraphrase the well-known Russian proverb, in contradistinction to BAAG: Guess, but justify^*. Because all hypothesis testing is a difficult process, it can easily get subverted into reaching the wrong conclusion. Therefore, it is extremely important not to set booby traps inadvertently along the way. One of the most common visual booby trap arises from the inappropriate use of logarithmically-scaled axes (hereafter, log axes) when plotting data.

Linear scale:

Each major interval has a common difference $(d)$, e.g., $200, 400, 600, 800, 1000$ if $d=200$:

Log scale:

Each major interval has a common multiple or base $(b)$, e.g., $0.1, 1, 10, 100, 1000$ if $b=10$:

The general property of a log axis is to stretch out the low end of the axis and compress the high end. Notice the unequal minor interval spacings. Hence, using a log scaled axis (either $x$ or $y$) is equivalent to applying a nonlinear transformation to the data. In other words, you should be aware that introducing a log axis will distort the visual representation of the data^†, which can lead to entirely wrong conclusions.

USL Fine Point: Sub-Amdahl Scalability

As discussed in Chapter 4 of my GCaP book, Amdahl's law is defined by a single parameter called the serial fraction, denoted by the symbol α and signifying the proportion of the total workload (W) that is serialized during execution. From the standpoint of parallel processing (where reference to Amdahl's law is most frequent) serialization means that portion of the workload can only execute on a single processor out of N parallel processors. The parallel speedup or relative capacity C_A(N) performance metric is given by: \begin{equation} C_A(N) = \frac{N}{1 + \alpha \, (N-1)} \end{equation} If there is no serialization in the workload, i.e., α = 0, then C_A(N) = N, which signifies that the workload scales linearly with the number of physical processors. The important observation made by Gene Amdahl (more than 40 years ago) is that even if α is relatively small, viz., a few percent of the execution time, scalability cannot continue to increase linearly. For example, if α = 5%, then C_A(N) will eventually reach a scalability ceiling given by 20 effective processors (1/α), even if there are hundreds of physical processors available in the system.

Prime Parallels for Load Balancing

Having finally popped the stack on computing prime numbers with R in Part II and Part III, we are now in a position to discuss their relevance for computational scalability.

Playing with Primes in R (Part II)

Popping Part III off the stack—where I ended up unexpectedly discovering that the primes and primlist functions are broken in the schoolmath package on CRAN—let's see what prime numbers look like when computed correctly in R. To do this, I've had to roll my own prime number generating function.

Primes in R (Part III): Schoolmath is Broken!

Here we are in Part III. Wait!? What happened to Parts I and II? Well, I started to write an article about Amdahl's law, parallelism and prime numbers, but found myself buried three levels deep trying to resolve problems with prime numbers in R. My normal inclination is to use Mathematica for such things, but I happened to already be using R for another reason so, I thought I'd see what it had to offer for calculating with primes. It now looks like that might have been a mistake.

Parallelism in PDQ

All so-called "analytic solvers" for queueing models, including PDQ, assume that the queueing system being modeled is in steady state. Steady state means that in the long run, the number of arrivals into a service facility, e.g., customers arriving at a grocery checkout, will be identical to the number of customers departing. Why is this important?

Dr. Dobb's is Dying

My colleague Jim Holtman just informed me that, according to embedded.com, the illustrious software developer magazine Dr. Dobb's Journal will now be embedded(pun intended) in InformationWeek. Both are owned by United Business Media LLC.

Jim and I have been following the series of articles by Herb Sutter on multicore concurrency, starting with the one entitled "Break Amdahl", where he discovers Gustafson's law (see Section 4.3.5 of my GCaP book, Springer 2007). As expected, that title looks slightly optimistic in light of the recently observed lack of scalability on Sandia Labs supercomputers. Of course, the universal law of scalability accounts for all these effects and, unlike Sutter's articles, we are able to quantify them based on actual measurements.

Anyway, as with print newspapers, I suppose all this means that even though Dr. Dobb's is not exactly dead yet, it is getting buried alive.

Scalability Theorems Paper Now Available

As promised, my paper containing the proofs that the universal scalability law is equivalent to the synchronous throughput bound of a machine repairman model of a multiprocessor with state-dependent service rate, is now available from the arXiv preprint server under the title "A General Theory of Computational Scalability Based on Rational Functions," and covers the following topics:

Mr. Amdahl Calls the Repairman

Back in January, I reported that my Universal Scalability Law (USL) had been proven to be equivalent to the synchronous throughput of the load-dependent machine repairman queueing model. Although I wasn't lying, what I really had was what we call a "sketch" for a proof. The details needed to be filled in, but that was just a question of finding the time to do it. In May, I found time to write the first draft and thought I would be finished shortly thereafter. That attempt ground to a halt for two reasons (you might want to refer to Appendix A in my GCaP book for the background):

1. Simulations that supported the theorem involved a barrier synchronizer, and for this to work continuously, my colleague Jim Holtman, discovered that the distribution of parallel execution times (with mean 'think' time Z) could only be deterministic (D). That's a special case of the repairman: D/M/1//N, whereas the equations in my proof show quite clearly that it must work for M/M/1//N.
   
2. There's a theorem in queueing theory (Bunday and Scraton, 1980) which states that what holds for the repairman (M/M/1//N) also holds for a more general source of requests viz., G/M/1//N. Since G is a superset of the distributions D and M, this theorem suggests that our simulations probably shouldn't be restricted to D-distributed think/execution times as observed in (1). Or should they?
   

Scalability Law as Queueing Model Proven

It never rains in California, it just pours. Not only have we had a lot of seasonal rain lately but it seems to be the season for proofs. In 2002, I proved that Amdahl's law is equivalent to a special kind of queueing behavior. This particular connection with queueing theory had not been made before. Here's a restatement of that theorem.