Gene Amdahl and Albert Einstein

Gene Amdahl was a hardware architect from the age of Big Iron. His company, Amdahl, manufactured mainframes that were plug-compatible with those sold by IBM. In the 1960s there was a trend towards multiprocessor architectures, and towards the parallelization of software applications to take advantage of such multi-headed systems. Amdahl coined what would become known as Amdahl's Law, a rule of thumb that can be used to estimate the actual performance improvement you might expect from parallelization.

Amdahl's Law most frequently takes the form of

1/(F + ((1-F) / N))

where F is the fraction of the computation that is by nature serial, (1-F) is the fraction that can be parallelized, and N is the number of processors you can spread the (1-F) portion across. What Amdahl was saying is: no matter how many processors you have, the speed up due to parallelization is proportional to that fraction of the computation that can actually take advantage of all those processors. Like all the best rules of thumb, this is kind of glaringly obvious and at the same time subtle. It all depends on making (1-F) big. If (1-F) is small, you can waste a lot of money on making N as large as you want to no avail.

As many people are learning today with the new multi-core microprocessors, and as my mainframe and supercomputer friends could have told you thirty years ago, designing a software application to take advantage of multiple processors is no small feat. Typically in all but a handful of very specialized applications, the kind that seem to occur only if you are doing classified research for the Department of Energy, only a portion, sometimes a small portion, of a program lends itself to the kind of fine-grained parallelization needed to take advantage of large numbers of processors. The programs that do lend themselves to massively parallel processors tends to be composed many independent computations. Otherwise the communications overhead or the serialization required for synchronization kills you.

Google has made stunningly effective use of large numbers of clustered processors using their MapReduce software architecture. I got a little verklempt with nostalgia when I read the paper by Dean and Ghemawat on MapReduce, because it reminded me of my days in graduate school decades ago, working on software designs for the kind of massively parallel hardware architectures envisioned by the Japanese and their Fifth Generation research. But as clever as MapReduce is, the applications that map well to it are still far too limited for just the same reasons.

Just to make matters worse, as folks like David Bacon, Scott Meyers, and Andrei Alexandrescu are quick to point out, even coarse-grained parallelization, like the kind you find in multi-threaded applications, is fraught with subtle peril, thanks to hardware memory models that bear little resemblance to how most developers think memory actually works. I sometimes find myself thinking of the thousands and thousands of lines of embedded C, C++ and Java code I have written in the past decade, wondering if any of it would actually work reliably on a modern multi-core processor.

But the beauty of Amdahl's Law is that it is very broadly applicable way beyond just making effective use of lots of processors. My favorite is latency in distributed applications.

When you try to send data from one computer to another, whether it's a book order to Amazon.com in the form of a SOAP message, or a pirated movie from your favorite peer-to-peer site, it takes a while to get there. If you try to speed things up by getting a faster network, you find out that what constitutes faster is not so simple. Network latency occurs in lots of places between the time that first bit leaves the near end and the last bit arrives at the far end. There's the software processing latency that takes place in the application, in the network protocol stack, and in the NIC device driver, before the data even gets on the wire. There's the bandwidth of the wire itself. There's the same software processing latency at the far end.

And then, as Albert Einstein would tell you, there's the speed of light.

See, when you upgrade your unbearably slow ten megabit per second network interface card with that shiny new gigabit per second card, all you have really done is affect just one small (1-F) of the total network latency equation, the transmission latency. In fact, if your computer is not capable of feeding that NIC with data at a gigabit per second, you might not have really accomplished anything. But even if it can, each bit is still governed by the ultimate speed limit: the rate at which a signal can propagate across the wire, and that rate is never faster than 300 million meters per second. No matter how fast your network is, that first bit is still going to take some time to travel end to end. 300 million meters per second sounds fast, until you start looking at Serious Data, then you start to realize that the propagation latency is going to kill you.

How do different network technologies actually achieve ever higher bandwidths? Sometimes they really do make data travel faster down the wire (but never faster than the speed of light). The now defunct Cray Research Corp. wrapped their signal wires in Gore-Tex insulation because it lowered the dielectric constant, which actually decreased the propagation delay. The speed of signal propagation in fiber-optic cable is faster than it is in copper wire. But mostly, whether using copper or fiber, they cleverly encode a bunch of bits in such a way that a single signal carries multiple bits of data, all of which arrive at the same time. The signal may take the same time to arrive at the far end, but once it gets there, you get more for your money.

Of course, on Star Trek, they were always using tachyon beams, Einstein be damned.

There are other ways to slow down even infinitely high bandwidth networks, some of which impact software designs at the application level. If you send a byte of data to the far end and have to wait for a reply before sending any more, you are going to take double the signal propagation hit on every single byte. You will have to wait for the byte to get to the far end, then wait for the reply to come back, so that you know your transmission was successful and you do not have to resend your byte. Network protocols and the applications that use them get around this latency by sending honking big packets of data at a time, and sending many packets before they have to stop and wait for an acknowledgement.

You can compute how much out-going data you have to buffer in memory in order to make effective use of your network pipe. Network protocols typically call this the window size. It is computed from the bandwidth-delay product. Take the size of your network pipe in terms of, say, bits per second, and multiply it by the round trip propagation delay in seconds for sending a bit down the wire and getting a reply bit back. The result is the number of bits you have to buffer in memory waiting for an acknowledgement from the far end.

The nasty part about this is that the higher the bandwidth of the network, the larger the bandwidth-delay product is, and you can never reduce the round trip propagation delay below that implied by the speed of light. I once worked on a project to send data between two supercomputers on an OC-3 link via a geosynchronous satellite. The bandwidth was 155 megabits per second. The round trip propagation delay was half a second. Do the math. We had to buffer nine megabytes of data at both ends of the socket. And this was on manly high speed SRAM memory, not wimpy DRAM with a virtual backing store. This was surely one expensive distributed application.

So before resorting to the easy trick of upgrading to a faster network technology, do some back of the envelope calculations to see if your investment will pay off. And do the same before buying that shiny new multi-processor/multi-core server.

Sources

David Bacon et al., The "Double-Checked Locking Pattern is Broken" Declaration

Jeffrey Dean and Sanjay Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters", OSDI 2004

Scott Meyers and Andrei Alexandrescu, "C++ and the Perils of Double-Checked Locking", Dr. Dobb's Journal, July and August 2004

J. L. Sloan, "Introduction to TCP Windows and Window Shifting/Scaling", Digital Aggregates Corp., 2005

J. L. Sloan, "Vaster Than Empires and More Slow: The Dimensions of Scalability", Digital Aggregates Corp., 2006

Wikipedia, "Amdahl's Law", October 2006

1890: A Tipping Point

Some years ago I inherited a Browning model 1955 Pocket Pistol. Like most of John Browning's designs, the model number was also the year it was introduced. This is a tiny little hammerless smooth-cornered semi-automatic pistol designed for a gentleman of that era to carry in his suit coat or pants pocket. It was a nice piece, and it still shoots just fine.

Being my usual anal-retentive self, I began researching the 1955. While it is not nearly as famous as an earlier Browning design, the 1911 (which is known by most as the iconic ".45 Automatic") it does have some interesting claims to fame. The 1955 was a re-release of an earlier design, the 1910, which itself was an earlier version of what evolved into the 1911. And the tiny Browning 1910 was the handgun used to assassinate Archduke Franz Ferdinand in 1914, an event which sparked off the First World War.

Author and television host James Burke, through his PBS shows such as Connections and The Day the Universe Changed, was always taking his viewers down a long contorted path of history to show how inventions and events were improbably linked together. And so shall I. WWI lead to the collapse of Germany under the leadership of Kaiser Wilhelm II. The collapse of Germany lead to the rise of the Nazi party and of Adolph Hitler. This lead to WWII (which unlike WWI really was a global conflict). And WWII lead to the Atomic Age.

So you could argue that 1914 was a tipping point in history, and that the assassination of an archduke with a Browning 1910 Pocket Pistol led to the Atomic Age. But I'm going to argue that there was an even more interesting tipping point connected to this chain of events: the year 1890.

Wilhelm II was an ambitious, impatient, and it turns out maybe a little brain-damaged, emperor of Germany and King of Prussia. In 1890, just two years after ascending to the throne, Wilhelm fired his Chancellor, Otto von Bismarck, because Bismarck just wasn't getting with the program for the conquest of Europe. Now by all accounts, Bismarck was a Prussian's Prussian. He has been described as brilliant. And by all accounts, although he may not have been the nicest guy, he really understood that diplomacy was a whole lot cheaper than warfare. So clearly he had to go. The canning of Bismarck in 1890 was a pivotal point in history as part of a chain events that eventually led to the Atomic Age.

The year 1890 was an interesting one for other reasons. In that year, the United States Census Bureau declared, based on the 1880 census, that the western frontier was closed. All the unclaimed land had been claimed, most of it had been settled, and thanks to the Transcontinental Railroad, the western United States was safe from incursion by foreign powers. (Just as Eisenhower saw the need for the Interstate Highway System for moving troops based on his experience with the German autobahns during WWII, Lincoln saw the need for the Transcontinental Railroad to move troops to the west coast to secure it from invasion by the European powers via Canada or Mexico). Because of this, most historians consider 1890 as the end of the era we think of as the "Old West".

I think it must be hard for folks from outside of the United States to appreciate the mythic quality the Old West has in our country. The period lasted barely a generation, from the end of the American Civil War in 1865 until 1890. If you added up all of the western films and television shows ever made (including the spaghetti westerns made in Italy), the total viewing hours might be longer than the Old West period actually lasted. But today, we're still making western movies and television series, still writing western novels, and millions of us (including me) still own at least one pair of cowboy boots that are likely to never set foot in a stirrup. I might own a couple of cowboy hats too.

The U.S. Census Bureau played another crucial role in the year 1890. The 1880 census took so long to tabulate, seven years, that the Bureau was seriously worried that the 1890 census might take longer than a decade to complete. They turned to a recent Ph.D. graduate, Herman Hollerith, for help. Hollerith had designed a mechanical tabulating machine that could sort and collate information stored in the form of holes punched on paper cards the size of the 1890-era U.S. dollar. The Bureau adopted Hollerith's invention, and the 1890 Census was completed in two and a half years. Hollerith went on to found the Tabulating Machine Company, which in the fullness of time became IBM.

So here's the crux of it: 1890 was the year in which the U.S. Census Bureau ended the Old West and began the Information Age. And it was the year in which the sacking of Otto von Bismarck would lead to two World Wars and the Atomic Age.

Living in Denver Colorado and working in information technology, I find it remarkable, and very resonant, that the Old West ended and the Information Age began in the same year, and through the same agency of the U.S. Government. And actions taking place that same year led to a chain of events that so thoroughly defined our current world.

In Defense of Misbehavior

Some years ago I read Robert Austin’s 1996 book Measuring and Managing Performance in Organizations. It’s not the kind of book I would have normally chosen to read at that point in my life. But I was on a tear reading books on software engineering methodology and people management, and I kept stumbling across references to it. Reading it changed my whole perspective on Life, the Universe, and Everything. The recent death of Enron chairman Kenneth Lay inspired me to try to organize my thoughts on Austin’s topic of measurement dysfunction.

Austin’s thesis can be summed up as follows:

• To be effective, incentive plans must be tied to objective measurements of employees’ performance against objectives.
  
• To incent employees to produce the optimal desired results and avoid unintended negative consequences, all possible aspects of their performance must be objectively measured.
  
• In any but the most trivial of tasks, such complete measurement is at worst impossible, or at best too expensive to be practical.

The implications of this should be terrifying to managers trying to steer the ship of industry, because it says that the helm is at best only loosely coupled to the rudder. Steering inputs may have little effect, the opposite effect, or no effect at all. The linkage may be so complicated as to appear non-deterministic. Or, perhaps worst of all, the lack of complete objective measures may lull the person at the helm into thinking everything is fine when in fact they are steering blindly in a field of icebergs.

In my experience, this seems unbelievable to some, obvious to others. What Austin did, though, was apply agency theory to demonstrate this mathematically. Agency theory is an application of game theory, the very same branch of mathematics that made Nobel laureates of folks like Robert Aumann, John Nash, and Thomas Schelling. It is the basis of much of modern contract law and employment practices. Common employment practices, such as overtime pay for hourly employees, is based on the math behind agency theory.

What is so compelling about Austin’s work is that while you can disagree with his premise when stated as a bold fact, it is a lot harder to argue with the math. Okay, so you don’t like his results; what part of the math don’t you agree with? That the less free time employees have, the more valuable is their remaining free time? That employees’ production is a mixture of results measurable by different metrics (for example, quality, functionality, time to market)? That there is some specific mix of results that is optimal? That some metrics are expensive or impossible to measure?

We have all heard of examples of measurement dysfunction, possibly under different terminology in other contexts. Incentive distortion, unintended consequences, perverse incentives, and moral hazard are just a few I have come across in reading articles on economics, law, management, and ethics. Measurement dysfunction is so fundamental that once you grasp the basic idea, you start seeing it in the news (or experiencing it first hand) everywhere.

Amazon.com’s call center agents were measured by the number of calls they processed per hour, inciting them to hang up on customers in the middle of conversations.

Gateway’s technical support agents shipped whole new computers to customers with relatively minor (but time consuming) problems in order to make their monthly bonuses.

The incentives for corporate executives like Kenneth Lay and Jeffrey Skilling to lie, cheat and steal were so great that they overcame the intrinsic motivators towards honesty and good behavior and the extrinsic disincentives like heavy fines and jail time. In fact, if you can make tens of millions of dollars deceiving your employees, your shareholders, and your government, mightn’t some jail time seem worth the risk? When you face the prospect of forty million dollars in the bank and a few years in jail, paying off the Aryan Brotherhood for protection and bribing a few prison guards suddenly seems doable (whether it really is or not). It may not be until such corporate officers face the prospect of getting letters from their families written on toilet paper from the community soup kitchen, describing how they were sleeping in cardboard boxes because federal agencies froze all their assets, will the disincentives towards crime appear adequate. The incentives for finding loopholes even in the 2002 Sarbanes-Oxley Act are great.

Software developers and the organizations that employ them seem particularly prone to measurement dysfunction. As Joel Spolsky has pointed out (and as has been my personal experience), if you incent developers to write bug-free code, they will go out of their way to cover up the bugs they can’t find, which will hence be shipped with the product. If you incent developers to fix bugs, they will inflate their metrics by introducing more bugs for them to find. If you measure programmer productivity on lines of code delivered, don’t expect any efforts at code reuse or code optimization to succeed; you’re not rewarding them for the lines of code they didn’t write. If you reward developers for customer support, subtle bugs will increasingly appear in production code so that developers can take heroic action. Nelson Repenning has written much on the topic of how rewarding fire fighting in organizations leads to more fires to fight.

I recall talking to the head of a large software development organization who was asking for a magic quality filter through which code could be run in order to add that objective measure to the incentive program. Folks, software developers solve problems and reverse engineer complex systems for a living. If they’re good at it, it is like their brains are hardwired to the task. And they love a challenge. I am completely confident that the developers I work with on a daily basis are perfectly capable of gaming any incentive system that their employer puts in place, without necessarily actually achieving any stated goal of the program. Plus, some aspects of software algorithm quality, such as it does not contain an infinite loop, are actually proveably impossible to detect in all cases (the so-called "halting problem" from my graduate school days).

Which, finally, brings me to the real points of this article.

First: any incentive program is bound to drive dysfunction into an organization. If you must have an incentive program, expect to spend large sums of money and much time tuning it to minimize the dysfunction. Don’t expect to even recognize that dysfunction is occurring. When I have worked in an organization that employed forced-distribution of ranking of employees, and have brought the topic of measurement dysfunction up to managers, every single one of them said “Yes, I understand that this is a risk, but so far it isn’t happening here.” Folks, of course it’s happening here. You have merely provided incentives for your employees to hide it from you. Or maybe you’re in denial. Either way, I see the dysfunction every single day as suboptimal results are delivered in order to improve objective, but partial, metrics.

Second: don’t blame your employees for responding to your incentive program. It is the incentive program that is at fault, not the employee. Upper management says all sorts of things that come under the heading of “motherhood and apple pie”. The only way an employee really knows what upper management truly values is via the incentive program. You may say “quality is job one”. But if you can’t measure quality (and you cannot measure all dimensions of it), but you continue to terminate employees that don’t make their dates, then it is clear to everyone that “quality is job seven, or maybe nine, and besides anything past job four isn’t really important”.

At the time of his dissertation, Austin, now a faculty member at the Harvard Business School, was an executive with the Ford Motor Company Europe. The insight his work gave me motivated me to go so far as to order his Ph.D. dissertation on which his very readable book is based. One wonders what insight from his personal experience managing both technology and people was Austin able to bring to his research.

Sources

Douglas Adams, Life, the Universe, and Everything, Del Rey, 2005

Robert Austin, Measuring and Managing Performance in Organizations, Dorset House, 1996

Robert Daniel Austin, Theories of measurement and dysfunction in organizations, (dissertation), Carnegie Mellon University, University Microfilm, #9522945, 1995

Robert Cenek, "Forced Ranking Forces Fear", Cenek Report, 2006

Robert Cenek, "Forced Ranking Forces Fear: An Update", Cenek Report, 2006

Tom DeMarco and Timothy Lister, Peopleware: Productive Projects and Teams, 2nd edition, Dorset House, 1999

W. Edwards Deming, Out of the Crisis, MIT Press, 2000, p. 23

Jena McGregor, "The Struggle to Measure Performance", BusinessWeek, January 9, 2006

Jena McGregor, "Forget Going With Your Gut", BusinessWeek, March 20, 2006

Jefffrey Pfeffer and Robert I. Sutton, Hard Facts, Dangerous Half-Truths, & Total Nonsense, Harvard Business School Press, 2006

Nelson Repenning et al., "Past the Tipping Point: The Persistence of Firefighting in Product Development", California Management Review, 43, 4:44-63, 2001

Nelson Repenning et al., "Nobody Ever Gets Credit For Fixing Defects that Didn't Happen: Creating and Sustaining Process Improvement", California Management Review, 43, 4:64-68, 2001

Joel Spolsky, "Measurement", Joel On Software, July 15, 2002