Bananas

If you live in Europe or the Americas, every banana you have ever eaten was probably a variety known as the Cavendish. This are other varieties of bananas, but they look so different (for one thing, they may have large, hard seeds, something bred out of the Cavendish) that you may not even recognize them as the same fruit you slice up on your breakfast cereal. And that's a problem. There is so little genetic diversity in the Cavendish that a single disease could wipe the long, yellow, conveniently self-packaged fruit we all know right off the planet.

Alarmist rhetoric? Not so much. That's exactly what happened to its similarly monogenetic predecessor, the Gros Michel banana.

Michael Osinski argues that a similar lack of diversity nearly led to the collapse of Western Civilization. Conspiracy theory? Again, not so much. Osinski, in an article in New York Magazine, admits that the latest global economic meltdown might have been at least partly his fault.

Osinski wrote the software that was used by nearly every investment bank on the planet to bundle mortgages into a kind of bond known as a collateralized debt obligation or CDO, and to compute an asking price for the result. A user of Osinski's software package would pour thousands of individual mortgages into one end, puree them into a smooth consistency, then parcel the results out into many different investment vehicles, each vehicle containing a tiny portion of each of those mortgages. Then many individual investors bought a portion of those investment vehicles. Investors like your 401(k), your mutual fund, and your pension plan. His software computed the value of the CDO based on many factors including the risk of the mortgages that went into it.

Because each mortgage was blended together with thousands of other mortgages, the risk of default of any one individual mortgage was spread out. Because the resulting smoothie of mortgages was distributed into many different investment vehicles, even if many mortgage holders were to default, those bad mortgages would be a tiny portion of each investment vehicle. And because the ownership of each investment vehicle was spread out among many investors, the tiny risk was shared among many. In the case of your 401(k), your mutual fund, and your pension plan, the investor itself was in fact made up of money from many different individuals.

The only way it could possibly go wrong would be if the entire housing market suddenly collapsed. And what were the chances of that happening?

How do you determine the worth of something? As someone who has bought and sold a used motorcycle or two, I can tell you that this isn't the easiest question to answer. My Honda CB700SC that was a basket case (that is, it had been separated into its component parts, and would take some work to get it running again), I sold it for a fraction of its book value, which is, after all, just someone's opinion based on what others have actually paid for a particular model of vehicle. My Harley-Davidson FLHS, on the other hand, I sold years later for more than I paid for it. See, in a free market, the worth of something isn't what some piece of paper or blue book says it is. Its worth is what someone else is actually willing to pay for it. Once you grasp that, it becomes clear why touchy-feely factors like investor confidence suddenly become really important, because the idea of value has a significant psychological component.

When the housing industry collapsed and house prices were suddenly severely deflated, people discovered that they owed far more on their mortgages than their homes were worth, because their homes were worth only what someone else was willing to pay for them.

That may not seem like such an issue if you've never owned a home. When you take out a loan to buy a car (or a motorcycle) for example, the vehicle is probably worth less than you owe on it as soon as you drive it off the lot. But houses are different. When your job transfers you to another state, or you graduate from college, or you lose your job and have to move to where your employment prospects are better, you can take your vehicle with you. But typically you'll have to sell your house, if for no other reason than to take the money you make on the sale to use as a down payment on a house in your new town.

That is, if you make any money on your house. But if you find you owe more on your home than someone else is willing to pay for it, you are seriously underwater. You can no longer afford to sell your home, because you can't afford to pay off the balance of the mortgage. You can't afford a new home, because you don't have the down payment from the sale of your previous home. You can't afford to move, even though your job depends on it.

The solution for many people was to just walk away from their old homes, to default on their mortgages, and leave the mortgage holder holding the bag. And by mortgage holder, I mean, ultimately, your 401(k).

The risk of default of each of those pureed mortgages was among the parameters supplied by the users of Osinski's software package. It took these risks into account when computing the value of the CDOs. The sudden default of so many mortgages more or less simultaneously was not a risk factor that the users of Osinski's software had anticipated. They had seriously underestimated the risk, and hence the software package had seriously overvalued the CDOs. Investor confidence in mortgage-backed securities eroded; taking all of that risk (which had in fact always been there) into account devalued the CDOs, which now found themselves owning toxic assets in the form of defaulted mortgages. And because of the incredibly broad distribution of the ownership of the CDOs, we all ended up owning parts of defaulted mortgages that were worth virtually nothing.

In a talk he gave at a recent conference I attended in Santa Fe, computer scientist and financial software guru Arthur Whitney (who, by the way, decades ago worked with Kenneth Iverson on the programming language APL) estimates that in a matter of days the valuation of these CDOs fell from around US$33 trillion to US$8 trillion.

Let me make this clear: almost overnight, twenty-five trillion dollars in wealth evaporated. It didn't get spent. It wasn't stolen. It simply ceased to exist because thousands of investors suddenly decided not to buy into the consensual hallucination that was the housing bubble.

So what, if anything, does this have to do with the kinds of topics I usually write about? And what the heck does it have to do with bananas?

Here's the thing: just about every investment bank on the planet was using Osinski's software package. For sure, they were all putting in the wrong parameters, and using it for far more complex investment vehicles than Osinski ever intended. But still, it was all the same software package, with the same input formats, the same calculations, the same menus, the same bugs, the same output formats, the same pop-ups, the same errors and warnings. It is possible, just possible, if there had been other software packages being used for this same purpose, that some investment houses might have come to a different conclusion about the risk inherent in mortgage backed securities? Even if the answer is no, the fact that everyone was using the same software package means they were all exposed to the same software bugs, the same design flaws, the same systemic errors.

They were all eating the same variety of banana. Except in this case, instead of losing a much beloved fruit, they ran the risk of a systemic error leading to the collapse of the world economy. Each of us is, in a very real sense, a victim of the success of Osinski's software package.

I recently helped develop an product in which we worked very hard to make the system recoverable in the field by the end-user. If the disk-based system failed, the user could boot up a flash-based system and recover the disk. If the flash-based system failed, the user could boot up the boot loader and recover the flash-based system. If the boot loader failed, the box had to be shipped back.

All three systems ran on the same processor. Much of the very low level code, that which would be typically described as part of the board support package, could have been common between the disk system, the flash system, and the boot loader. It was just a matter of time until someone suggested just that. I argued (vehemently I'm told) against it. Even if the code were exactly the same, I argued against sharing the same source files in the source code control system. Otherwise, a single error in a single source file could lead to a systemic flaw that caused the same defect to occur in all three tiers of the product, rendering the product not just inoperable but unrecoverable in the field.

I understand -- better than most -- the economics of software reuse. And I understand how free markets drive companies to adopt what they perceive to be the best practices, including the software tools, of their competitors (whether they are really the best or not). Economies of scale drive this too. Do all of your employees use the same brand and model of desktop or laptop? Running the same operating system? All purchased about the same time because of a volume discount? And then there's people. Do you hire people that look like you? That share your opinions? That think the same as you so that you feel comfortable around them?

Whether you are talking about software, hardware, bananas, or people, a lack of diversity can lead to dire and unforeseen consequences.

Cache Coherency and Memory Models

Sometime around 2002 I was working on an object-oriented multi-threading framework in C++ for an embedded project and the most remarkable thing happened. I had an object that represented a thread. My application created the object via the usual new operator and started the thread. The first thing the thread did was access its own thread object. It core dumped. Core dump analysis using gdb revealed that the virtual pointer in the object was null.

I know what you're thinking.

That's impossible.

That's what I thought too. That event led to a personal research project that consumed many of hours of my free time and led to my putting together a presentation on the Implications of Memory Models (or Lack of Them) for Software Developers. In it, I describe the research of others that reveals that modern processor memory subsystems have broken the memory models implicit in the software.

This includes software written in higher level languages like C, C++, and Java (prior to Version 6 anyway) and as well as that written in assembler. It includes multi-processors, multi-core uniprocessors, and even those single core uniprocessors that are hyper-threaded. The upshot is that, thanks to various processor, memory, and compiler optimizations, memory may not be read or written when you think it is from looking at your code. Or even the compiled code.

Java addressed this issue in Version 6, providing you use volatile or the language's built-in synchronization mechanisms. But C and C++ developers dealing with variables shared among threads must still resort to the appropriate use of the volatile and explicit memory barrier instructions, which may be provided by your threading library's synchronization functions, providing you use them.

Fortunately, at least gcc offers the generic __sync_synchronize() built-in that performs a platform-specific memory barrier with full fence semantics. Unfortunately, in their paper Volatiles are Miscompiled, and What to Do about It, Eric Eide and John Regehr at University at Utah reveal that code containing the volatile keyword is frequently miscompiled. The life of a systems programmer is seldom simple.

Recently I discovered Ulrich Drepper's lengthy white paper on What Every Programmer Should Know About Memory. He gives a detailed explanation of how the hardware architecture of cache and memory subsystems can affect performance and correctness of software. I recommend it to every one that does embedded or systems development.

(Actually, I recommend it to all developers. But my Java buddies have pointed out on more than one occasion that they don't really care to know how things work under the hood. That's an attitude that I can't relate to. But I was one of those kids who took clocks apart to see what made them tick.)

It took me a couple of weeks to read Drepper's 114 page paper cover to cover. The entire time I was reading his description of the MESI cache coherency protocol, I was trying, without much success, to reconcile it with my prior reading on processor memory models. (Briefly, the MESI protocol, which tries to keep the local caches of individual processor cores in sync, places each cache line in a state of Modified, Exclusive, Shared, or Invalid.) 

Then finally I got to section 6.4.2, "Atomicity Operations", page 68:

If multiple threads modify the same memory location concurrently, processors do not guarantee any specific result. This is a deliberate decision made to avoid costs which are unnecessary in 99.999% of all cases. For instance, if a memory location is in the ‘S’ state and two threads concurrently have to increment its value, the execution pipeline does not have to wait for the cache line to be available in the ‘E’ state before reading the old value from the cache to perform the addition. Instead it reads the value currently in the cache and, once the cache line is available in state ‘E’, the new value is written back. The result is not as expected if the two cache reads in the two threads happen simultaneously; one addition will be lost.

If this doesn't run chills down your spine, you're not thinking clearly. Drepper goes on to discuss some of the same atomicity operations I talk about in my presentation. His paper also details the write reordering which I suspect was the cause of my null C++ virtual pointer.

Why is all this stuff important?

In the early 1980s I was a computer science graduate student working on my thesis under the direction of my mentor Bob Dixon, in a research group that was looking at programming language and operating system architectures for massively parallel processors. This was when Japan's Fifth Generation project, dataflow architectures, and the massively parallel Connection Machine were big. At the time, it all seemed bleeding edge and, given our budget, largely hypothetical.

But just a few years later I found myself working at a national lab, the National Center for Atmospheric Research, which not only had a Connection Machine, but other exotic highly parallel systems including several Cray Research supercomputers with multiple processors and vector hardware.

A few years later still and I am more than a little surprised to find that I have a four-core Dell server running Linux in my basement. The future has a way of happening.

In The Landscape of Parallel Computing Research: A View from Berkeley, researchers David Patterson et al. describe the future that they see: not just multi-core, but many-core, the equivalent of a massively parallel processor running on your desktop, with the dozens or hundreds of cores sharing memory. Suddenly, understanding concurrency, synchronization, and memory models (or the eventual higher level languages that implement it all without the developer having to worry about it) seems pretty necessary.

For me, it's 1983 all over again.

The Vulnerability of Volatiles

As if having to deal with broken memory models isn't bad enough. In his latest column in Embedded Systems Design magazine, Jack Ganssle points us to research that shows that virtually all C compilers mis-compile code that uses volatiles. Here's the original article and presentation, both by Eric Eide and John Regehr at the University of Utah.