20090917 - Food-For-Thought Supermarket Aisle
This post is to keep the twitter peanut gallery happy ;) Thanks Ivan-Assen Ivanov for the inspiration, sure was a lot more fun then doing something productive like continuing my search for a place to live when I move...
Starting With Some Simple Examples
Q: If you are playing chess with a distant opponent via snail mail, and want to play the game faster than the US postal service can deliver messages, how do you do it?
A: You send not only your next move, but also your response to all of your opponent's possible next moves, under agreement neither player will cheat.
In the above case, latency is the bottleneck, compute time is abused with redundant work to solve the latency problem.
Q: A pre-gunpowder age general wants to communicate a real-time updates of highly complex battle field commands to distant field officers but only has a limited set of flags, how is this done?
A: General and field officers pre-agree upon a complex battle plan option (or meaning) per flag.
Bandwidth is the bottleneck, solved by taking advantage of local memory using the ultimate form of compression.
Q: A manager has 12 phone meetings in a given very busy day, how is this handled efficiently?
A: A secretary pre-schedules each phone meeting.
This is a rough example of the problem of task preemptive scheduling (interrupted phone calls) when there are dependencies (communication) between nodes.
Humans Are Natural Parallel Programmers
Ironically, humans as a group are great at solving problems with distributed memory, as individuals have only a subset of the knowledge stored in the continuation of the species. Many of us, myself included, couldn't possibly remember everything we need to know on a daily basis. In fact, often we get better at remembering where we can find information (indexes or addresses) than we are at remembering the information itself. Humans organize into hierarchies to solve problems, as well as pipeline processes, think about manufacturing (thanks Mike Acton), supply chain management, etc.
The point I am getting at here, is that going parallel is natural and is easy to think about when grounding the problem in terms of something real.
Human Species Machine
How about something more crazy...
Massively parallel programming gets rather interesting when thinking about distributed memory, non-coherent redundancy, the problem of node failure, message passing, latency, and compression, all together.
One fantastic quality of humans is that we all have different memories of similar events or ideas, a kind of distributed non-coherent redundancy. The memory of an event (or idea) is physically distributed across many nodes, with great overlap in the "important" data and less overlap in details which are more important to individual nodes.
People live and die (node failure) and pass on ideas though ripples left in the fabric of this non-coherent distributed memory. Human language and culture provides a huge distributed context as to which to compress data for message passing. A single phrase can draw upon this giant context for meaning.
Stability Without Coherent Memory
Simple patterns can serve to generate intrinsic randomness (divergence), or can serve to maintain and safely transmit information (convergence). Digital computation is a great example of this (given the underlining "analog" flow of electrons).
With the human species machine, constant message passing serves to shape and change the distributed memory. Ideas and information become stable when replicated across many nodes. The more parallel the machine, and the more non-coherent, distributed, and redundant the memory gets, the less a single node failure matters. In fact, given the amount of message passing, the information is constantly in flux at the scale of individual nodes, but as a global whole, a stable idea is highly coherent collectively.
BTW, if you are still reading this post, I would highly suggest reading Stephen Wolfram's New Kind of Science (at least twice)!