Massive Parallelism and the Duality of Humpty Dumpty
Disclaimer: Some of the following has been so over simplified that it is hardly recognizable by those that have been truly instructed in the black arts. But the oversimplification is necessary in order to put me, Tracey, these AI-complete problems, and this multicore business in proper context.If we can just look past the controversy over true identity and nature of Humpty Dumpty to see him as the conflicted fellow he was. Then we won't have far to go. For those that don't remember here's one rendition of the poem:
Sat on a wall
Had a great fall
All the kings horses and
All the kings men couldn't put Humpty back together again.
In this rendition of the poem, Humpty is some kind of egg. I remember when I first read it as a child, I pictured one of those large Pterodactyl eggs from the Flintstones. The rumor has it that Humpty was huge. For some reason most of my mates at the time thought it was a chicken egg, but in either case the dilemma would be the same. You see, Humpty was both complicated and complex at the same time. That fact is what would make any attempt by the king's horses and men to put Humpty back together totally futile. Herein lies the rub, I know it seems kind of weird to describe Humpty as a system, but he was. He was a system that could be described as both complicated and complex. And it is important that we distinguish the two.
In very loose terms:
A complicated system is a system made of many interrelated and interacting parts in which the system's functioning as a whole can be understood and predicted as a sum of its parts. That is, we can look at each part's functionality and combine the functionalities together, and although difficult and painstaking we can explain and predict why the system functions the way it does.
A complex system is a system made of many interrelated and interacting parts in which the system's functioning as a whole cannot be understood or predicted simply as a sum of its parts. Some how the whole system is greater or different than the sum of its parts. Although we may be able to understand the functioning of the parts individually, somehow when they are combined they produce functionality that cannot be understood, explained or predicted simply by looking at the original parts.
Humpty Dumpty as a snapshot of an egg (source code if you will) can be understood from a physics and biological point of view with enough effort. Egg shells, egg yolk, all made of molecules and the molecules are all consisting of massive amounts of atoms, and the atoms consisting of kinds of particles, that get stripped down into all of these vibrating strings (so they say). The biological view could explain the cell growth cycle and the synergy happening between the egg shell, the egg yolk, DNA, and the function of the nurturing parent. All this is very complicated indeed. But with enough work we can explain in a general sense what Humpty is and make a few predictions about how his source code works. But Humpty, the dynamic living process of an egg (runtime object if you will) is another story altogether. Although we can describe, explain, and predict Humpty's functional parts from a physics or biological point of view, somehow there is something more to the living egg that escapes us. That's why if we shatter a living egg, the prospects of putting it back together as it was with the life unaffected is a very, very, tough (if not impossible) row to hoe, which makes Humpty a complex system. An egg is more than the sum of its parts (at the least the parts that we understand at this time).
Excuse me while I stretch, but Humpty Dumpty's duality is very similar to one of the dualities found in software. Especially software that involves massive parallelism, and deep concurrency among agents or tasks. Take the notion of a complicated class definition and hierarchy that implements, tasks, threads, mutexes, locking, interprocess communication, semaphores, shared memory constructs processes, etc.,vif we look at the design of the entire system and how it fits together and we deconstruct the hierarchy, operating system functionality, network functionality (on paper), and study the functionality of the parts of the class hierarchy, although complicated, we can still explain and from a software design point of view predict the software's behavior. But if you look at that same class hierarchy as a collection of runtime instances within the context of an executing operating system and network, then we find the system is complex. That is somehow the system is greater or different than the sum of its parts. Our ability to predict, or even totally explain its behavior becomes difficult.
If we run with the analogy a little longer, the complicated nature of Humpty can be dealt with using solid software design and engineering methodology. However, the complex nature of Humpty requires a paradigm shift in order for us to be able to understand, explain, predict and thus control his behavior. We are certain that constructing and controlling true massively parallel systems will require such a paradigm shift. The reality of massively parallel computers, and the trend toward goal driven, emergent software will produce systems that have this dual nature. With extreme effort we'll understand the class definitions, but the runtime instances will escape us. Which brings us back to me and Tracey's adventure along the yellow brick road of AI-complete problems.
Most of the problems that Tracey and I are working on right now, are suspiciously complex. We naively believe that access to cheap multicore soon to be massively multicore computers will some how help us on our way to see the wizard. To be honest, we can hear some of our mates laughing at us at the symposiums and colloquiums. But we have a paradigm shift in our pockets and we are comforted with two things.
- First, is a statement by a famous and often laughed at physicist:
Problems cannot be solved at the same level of thinking that created them.
- Second is a well-known fact:
He who laughs last, laughs best.