Sunday, April 27, 2008

Parallel Computing: Why the Future Is Reactive

Reactive vs. Non-Reactive Systems

A reactive system is one in which every stimulus (discrete change or event) triggers an immediate response within the next system cycle. That is to say, there is no latency between stimulus and response. Algorithmic software systems are only partially reactive. Even though an operation in an algorithmic sequence reacts immediately to the execution of the preceding operation, it often happens that a variable is changed in one part of the system but the change is not sensed (by calling a comparison operation) until later. In other words, in an algorithmic program, there is no consistent, deterministic causal link between a stimulus and its response.

The End of Blind Code

Algorithmic systems place a critical burden on the programmer because he or she has to remember to manually add code (usually a call to a subroutine) to deal with a changed variable. If an application is complex or if the programmer is not familiar with the code, the probability that a modification will introduce an unforeseen side effect (bug) is much higher. Sometimes, even if the programmer remembers to add code to handle the change, it may be too late. I call blind code any portion of an application that does not get automatically and immediately notified of a relevant change in a variable.

Potential problems due to the blind code problem are so hard to assess and can have such catastrophic effects that many system managers would rather find alternative ways around a deficiency than modify the code, if at all possible. The way to cure blind code is to adopt a reactive, non-algorithmic software model. In a reactive programming system, a change in a variable is sensed as it happens and, if necessary, a signal is broadcast to every part of the system that depends on the change. It turns out that the development tools can automatically link sensors and effectors at design time so as to eliminate blind code altogether. See Automatic Elimination of Blind Code in Project COSA for more info on the use of sensor/effector association for blind code elimination.

Conclusion

The synchronous reactive software model is the future of parallel computing. It enforces temporal determinism and eliminates blind code and all the reliability problems that plague conventional algorithmic software. In addition, it is ideally suited to the creation of highly stable and reusable plug-compatible software modules. Drag’m and drop’m. These easy to use, snap-together modules will encourage the use of a plug-and-play, trial-and-error approach to software construction and design. Rapid application development will never be the same. This is what Project COSA is all about. Unfortunately, a truly viable reactive system will have to await the development of single and multicore processors that are designed from the ground up to support the non-algorithmic software model. Hopefully, the current multicore programming crisis will force the processor industry to wake up and realize the folly of its ways.

In my next article, I will explain why future computers will be non-algorithmic.

See Also:

How to Solve the Parallel Programming Crisis
Nightmare on Core Street
Parallel Computing: The End of the Turing Madness
Parallel Programming: Why the Future Is Synchronous
Parallel Computing: Why the Future Is Non-Algorithmic
Why Parallel Programming Is So Hard
Parallel Programming, Math and the Curse of the Algorithm
The COSA Saga

PS. Everyone should read the comments at the end of Parallel Computing: The End of the Turing Madness. Apparently, Peter Wegner and Dina Goldin of Brown University have been ringing the non-algorithmic/reactive bell for quite some time. Without much success, I might add, otherwise there would be no parallel programming crisis to speak of.

Wednesday, April 23, 2008

D-Wave’s Quantum Computing Crackpottery

A Sucker Born Every Minute

A little over a year ago, D-Wave Systems, a Canadian company based in Burnaby, British Columbia, announced to the world that it had perfected a 16-qbit working prototype of a (supposedly) quantum computer. This January, D-Wave secured $17 million worth of financing from a Dublin based investment firm called International Investment and Underwriting (IIU). Did anybody say, sucker? Did I hear anybody say, snake oil? Does IIU really stand for ‘Idiotic Investment and Underwriting’? I am being facetious, of course. It’s my way of saying that anybody who invests in quantum computing is throwing money out the window. And by anybody, I don’t mean just private investors but public institutions as well. It does not bother me so much that private investors lose their money in QC (they’re in the risk business by choice) but, when I see government agencies like NIST wasting the taxpayer’s money on silly crackpottery, that bothers me.

Zero Evidence

Quantum computing is the only “scientific” field that is not only based on zero evidence but the evidence, if it did exist, can never be observed by definition. The entire quantum computing field is based on the conjecture that certain quantum properties can have multiple states simultaneously, even though the property in question only has room for one. Worse, this property can never be observed in its superposed states because, as soon as you try to observe it, nature does some weird magic called the “collapse of the wave function” and the property instantly takes on one state or another. Amazing, isn’t it? Physicists get away with crap like this because they’ve managed to convince the lay public that it is too stupid to understand physics. This gem is straight from the so-called Copenhagen interpretation of quantum mechanics and Heisenberg’s uncertainty principle. The whole thing is so devoid of logic that Nobel Prize winner Erwin Schrödinger devised a now famous thought experiment (Schrödinger's cat) to illustrate the high strangeness, if not the outright crackpottery of quantum superposition. As Paul Feyerabend once wrote in 'Against Method', "the most stupid procedures and the most laughable results in their domain are surrounded with an aura of excellence".

Quantum Ignorance

The questions that should be on everybody’s mind are the following: Do probabilistic processes necessarily imply superposition? Should one base a field of science on a mere conjecture or interpretation? The answer is no, of course. Consider that physicists are completely ignorant of the underlying reason that quantum interactions are probabilistic. And yet, in spite of this glaring lacuna in their understanding, they want an unsuspecting public to believe that they understand enough about the subject to be certain that superposition is a fact of nature as opposed to a mere interpretation. You don’t believe me? Go ask any physics professor to explain why the decay duration of subatomic particles is probabilistic. They have no clue, really. In view of the absence of evidence and of the incompleteness and inadequacy of their understanding, what makes quantum physicists so sure that superposition is a fact of nature? The answer is that they are not sure at all. Quantum computing is a field based on ignorance, arrogance and wishful thinking.

Crackpottery in High Places

Quantum computing is what I call voodoo science, the sort of field that is sure to attract all kinds of crackpots. Consider its most visible and most ardent promoter, Oxford physicist and professor David Deutsch. Deutsch is not only a quantum computing pioneer, he is also a strong supporter of the many-world interpretation of quantum mechanics. MWI is essentially an attempt by some to explain away the obvious silliness of state superposition by positing that the states exist in multiple universes. This is like borrowing from Peter to pay Paul, however. In other words, MWI proponents merely took away one unobservable outlandish conjecture, only to replace it with another equally unobservable and outlandish conjecture. This is what I call crackpottery in high places. MWI is obviously not anything that should be called science but David Deutsch is not known for being bothered by the Star-Trek quality of his physics. He relishes it. He is also a believer in the physical possibility of time travel (source: NOVA). He believes, along with Kip Thorne and Stephen Hawking that Einstein’s general theory of relativity does not forbid time travel. What is amazing is that, in his book, The Fabric of Reality, Deutsch writes about the famed philosopher of science, Sir Karl Popper, even though Popper once called spacetime, “Einstein’s block universe in which nothing ever happens” (From: Science: Conjectures and Refutations). What Sir Karl was pointing out is the fact (ignored by most physicists but a fact regardless) that nothing can move in spacetime, which means that the spacetime of relativity forbids time travel by definition. The point that I'm driving at is that David Deutsch is a crackpot, pure and simple; and it does not surprise me a bit that time travel crackpots like him would be attracted to Trekkie fairy tales like wormholes, parallel universes and quantum computing.

Conclusion

As I promised in my last post, I was working on a short essay to explain why parallel systems should be reactive but then I got distracted by an article in MIT Technology Review about D-Wave’s exhorbitant claims and I got fired up to write about it. As seen above, I have very strong opinions about quantum computing: I think it is crackpottery at best and fraud at worst. I think that the frequent press announcements claiming progress in the field are pure BS, propaganda designed to secure government grants and attract gullible investors. I have excellent cause to believe that there is a very simple reason that quantum processes are probabilistic and it has nothing to do with superposition or any such silliness. I have written about this before. As always, I tell it like I see it. I guess it's just the rebel in me. Stay tuned.

See also:
Why Quantum Computing Is Bunk, Part I, II
Why Space (Distance) Is an Illusion

Wednesday, April 9, 2008

Parallel Computing: Why the Future Is Synchronous

Synchronous Processing Is Deterministic

I have always maintained (see COSA Software Model) that all elementary processes (operations) in a parallel program should be synchronized to a global virtual clock and that all elementary calculations should have equal durations, equal to one virtual cycle. The main reason for this is that synchronous processing (not to be confused with synchronous messaging) guarantees that the execution order of operations is deterministic. Temporal order determinism goes a long way toward making software stable and reliable. This is because the relative execution order (concurrent or sequential) of a huge number of events in a deterministic system can be easily predicted and the predictions can in turn be used to detect violations, i.e., bugs. Expected events (or event correlations) are like constraints. They can be used to force all additions or modifications to an application under construction to be consistent with the code already in place. The end result is that, in addition to being robust, the application is easier and cheaper to maintain.

Synchronous Processing Is Easy to Understand

The second most important reason for having a synchronous system has to do with the temporal nature of the human brain. There is a direct causal correlation between the temporal nature of the brain and program comprehensibility. Most of us may not think of the world that we sense as being temporally deterministic and predictable but almost all of it is. If it weren’t, we would have a hard time making sense of it and adapting to it. Note that, here, I am speaking of the macroscopic world of our senses, not the microscopic quantum universe, which is known to be probabilistic. For example, as we scan a landscape with our eyes, the relative motion of the objects in our visual field occurs according to the laws of optics and perspective. Our visual cortex is genetically wired to learn these deterministic temporal correlations. Once the correlations are learned, the newly formed neural structures become fixed and they can then be used to instantly recognize previously learned patterns every time they occur.

The point I am driving at is that the brain is exquisitely programmed to recognize deterministic temporal patterns within an evolving sensory space. Pattern predictability is the key to comprehension and behavioral adaptation. This is the main reason that multithreaded programs are so hard to write and maintain: they are unpredictable. The brain finds it hard to learn and understand unpredictable patterns. It needs stable temporal relationships in order to build the corresponding neural correlations. It is partially for this reason that I claim that, given a synchronous execution environment, the productivity of future parallel programmers will be several orders of magnitude greater than that of their sequential programming predecessors.

Synchronous Processing and Load Balancing

An astute reader wrote to me a few days ago to point out a potential problem with parallel synchronous processing. During any given cycle, the cores will be processing a variety of operations (elementary actions). Not all the operations will last an equal number of real time clock cycles. An addition might take two or three cycles while a multiplication might take ten cycles. The reader asked, does this mean that a core that finishes first has to stay idle until all the others are finished? The answer is, not at all. And here is why. Until and unless technology advances to the point where every operator is its own processor (the ultimate parallel system), a multicore processor will almost always have to execute many more operations per parallel cycle than the number of available cores. In other words, most of the times, even in a thousand-core processor, a core will be given dozens if not hundreds of operations to execute within a given parallel cycle. The reason is that the number of cores will never be enough to satisfy our need for faster machines, as we will always find new processor-intensive applications that will push the limits of performance. The load balancing mechanism of a multicore processor must be able to mix the operations of different durations among the cores so as to achieve a near perfect balance overall. Still, even in cases when the load balance is imperfect, the performance penalty will be insignificant compared to the overall load. Good automatic load balancing must be a priority of multicore research. This is the reason that I am so impressed with Plurality’s load-balancing claim for its Hypercore processor. However, as far as I can tell, Plurality does not use a synchronous software model. They are making a big mistake in this regard, in my opinion.

Conclusion

In conclusion, I will reiterate my conviction that the designers of future parallel systems will have to adopt a synchronous processing model. Synchronous processing is a must, not only for reliability, but for program comprehension and programmer productivity as well. Of course, the adoption of a pure, fine-grain, synchronous software model has direct consequences on the design of future multicore processors. In my next article, I will go over the reasons that the future of parallel computing is necessarily reactive.

[This article is part of my downloadable e-book on the parallel programming crisis.]

See Also:

How to Solve the Parallel Programming Crisis
Nightmare on Core Street
Parallel Computing: The End of the Turing Madness
Parallel Computing: Why the Future Is Non-Algorithmic
Parallel Computing: Why the Future Is Reactive
Why Parallel Programming Is So Hard
Parallel Programming, Math and the Curse of the Algorithm
The COSA Saga

PS. Everyone should read the comments at the end of Parallel Computing: The End of the Turing Madness. Apparently, Peter Wegner and Dina Goldin of Brown University have been ringing the non-algorithmic/reactive bell for quite some time. Without much success, I might add, otherwise there would be no parallel programming crisis to speak of.

Sunday, April 6, 2008

Plurality’s HAL: Kicking Ass on Core Street

Misbehaving

I don’t do reviews and I don’t accept advertising. I just tell it like I see it and I try hard to be as brutally honest as possible when I do tell it. So if you contact me and ask me to take a look at your technology, know in advance that I never pull my punches. I will tear your pretty little baby into pieces if it so much as smells a little bit funny. Those of you who are familiar with my views on the multicore crisis already know that I am hard to please. I have strong ideas about how a multicore processor should behave and I will not compromise. And let me tell you, there is a lot of misbehaving going on out there. Right now, the multicore landscape is ugly as sin. Some people need an ass whipping, I swear. I especially dislike the crap being put out by industry leaders like Intel, AMD and the others. Lately I was beginning to despair of catching a glimpse of even a tiny hint of beauty in this dreadful landscape any time soon. That’s when someone brought Plurality Ltd to my attention.

Plurality’s Hypercore Processor

One cannot help being mesmerized by the unusual beauty of the colorful animation on Plurality’s welcome page. One is immediately struck with an irresistible urge to find out more about their technology. But Plurality, a small privately owned Israeli company founded in 2004 and headquartered in Netanya, is beautiful in more ways than one. In my opinion, their product, the Hypercore Processor, is a mixture of hyper beauty and a touch of ugliness. I’ll get to the ugly part in a minute. What caught my attention is that the company seems to have solved several crucial problems in multicore design that a behemoth like Intel, with all the gazillions that it lavishes on multicore research labs around the world, probably never even recognized as being crucial. Plurality’s engineers figured out a way to design a general purpose, fine-grained, self-balancing, auto-scalable, MIMD, 256-core processor! How cool is that?

The Good

The claims made by Plurality regarding the Hypercore’s so-called synchronizer/scheduler sound almost too good to be true. Take a look at the block diagram of their multicore architecture:

They’re claiming that their scheduler is able to perform near perfect load balancing. They’re also claiming that the cores can access shared memory without creating a bottleneck. This means that they are able to deliver fine-grain parallelism in a general purpose MIMD environment! This is incredible stuff. About a year ago I came up with a scheme to do fine-grain, real-time load balancing in a multicore computer. But then I realized that using a central controller to feed instructions one by one into a bunch of cores would not scale up as the number of cores increases. Here's a block diagram of my original design of the COSA multicore processor for comparison:

I also worried that having multiple memory caches would introduce unacceptable latencies if the cores had to frequently access memory in distant caches. In other words, my scheme was not scalable. I eventually thought of a decentralized mechanism (unpublished) that distributes the load-balancing task among the cores while keeping inter-core communication to a minimum. Apparently, Plurality seems to have solved, not only the scheduling problem, but the memory access bottleneck as well. How? I don’t know. It sounds almost like magic. If true, it means that at least one person at Plurality must be fully awake with a humongous thinking cap on.

The Bad

I am not hiding the fact that I am impressed with Plurality’s technology. Them Israeli boys are kicking major ass and taking names on Core Street, there is no doubt about it. They seem to have delivered some of the really nice things that I’ve been craving for, for a long time now. Intel and AMD should be ashamed of themselves. Does this mean that I believe that Plurality has solved the multicore problem? The answer is no. Nobody’s perfect and, as they say, Rome was not built in one day. Still, when I have a bone to pick I must pick it. I don’t like Plurality’s programming model. I think their Task Oriented Programming model is crap. In this respect, they’re making the same mistake that everybody else is making. I understand the motivation behind retaining some similarity and compatibility with the legacy technology. This situation may look somewhat analogous to the time when, more than a century ago, the first horseless carriages had wheels and stepping boards that looked like those of the buggies that they replaced. It’s not the same thing. Plurality's multicore processor may look and sound like a Ferrari or a Lamborghini but it is still attached to a mule because there is no fuel in the tank. Here is their pitch:

Programming the Hypercore, beyond what is required when programming a standard unicore processor, is based on Plurality's unique Task Oriented Programming. The only programmer requirement is to perform a simple partitioning of the algorithm into specific tasks, and compose a task map accordingly.
This is pure BS, of course. There is nothing simple about partitioning a sequential algorithm into parallel tasks and Plurality’s task oriented programming model is no different than breaking a program into threads. Plurality has simply given multithreading a new name in the hope that nobody would notice. Worse, the programmer has to compose a task dependency map on top of it! Come on, guys. You know better than that. I know you worked your butts off to get to where you are but your work is not done yet. Your programming model stinks. Your work will not be done until you come up with a processor that is designed from the ground up to support a truly parallel, synchronous reactive programming model like the COSA software model. Besides, what’s with the linguistic nonsense? Why would you want people to continue to program code like they did in the sequential days? This does not make sense. You either have a parallel processor or you don't. No way you’re going to tell me that you want to jump on board a shiny new 21st century spaceship and bring a pile of putrid 20th century garbage with you. Believe me, you will not be allowed into port until you jettison all that crap overboard. Take a look at Jeff Han's multitouch screen technology. That's the future interface of parallel programming. Just drag them and drop them.

Conclusion

Even though Plurality claims that “the Hypercore programmer needs not be familiar with the details of the machine, nor how its resources are interconnected and managed” (which is a very desirable and cool thing to have) I still think their programming model is crap. Having said that, I think Plurality is light years ahead of everybody else. I am not Jewish but I can tell you guys that, if you play your cards right, all the gentiles will come flocking like migratory birds to worship at your feet. You guys are riding the crest of a revolutionary wave. You have demonstrated that you've got what it takes to design and build a kick-ass multicore processor. You aren't there yet but you are onto something big, something that can potentially catapult your nation, Israel, into an economic and technological powerhouse, the Lion of Judah and all that. And we all know what that means. The correct multicore architecture is the legendary pot of gold at the end of the rainbow. The Israeli government should declare Plurality a national treasure and immediately pump 100 million dollars into its coffers. Ok, it’s kind of a joke, but I’m only half kidding. I’ll have more to say about Plurality in the weeks to come.

PS. Please get rid of that Plurality name. Look, this is a world market. Do you realize that the Japanese will have a hard time pronouncing your name? It sucks. You need something catchy like a cool Biblical Hebrew word or something. And why call your processor the Hypercore? That’s geeky and lame, in my opinion. Call it something like Abraham or Sarah, or Rebbecah or Joshua or Moshe or Elijah or Samson. Or something! Don’t be shy. Everybody already knows you guys are Israeli. So what? One more thing, why limit yourself to the embedded market? Go for the whole pie. That’s what I would do. Shalom.

Related articles:

Transforming the TILE64 into a Kick-Ass Parallel Machine
Tilera's TILE64: The Good, the Bad and the Possible
How to Solve the Parallel Programming Crisis