Tuesday, September 18, 2007

Don’t Like Deadlocks, Data Races and Traffic Accidents? Kill the Threads

All Multicore and Parallel Programming Related Articles

Bad Software Model

If we want to get rid of all the nasty problems that plague concurrent software, then we must get rid of the threads. Multithreading is the second worst thing to have happened to computing. The worst is the algorithm proper, the mother of all threads and of everything that is bad with software. We have become addicted to a hopelessly flawed paradigm. Our multithreaded software systems are full of bugs (hidden or otherwise) and they are hard to program. But the problem is far more serious than this. The algorithmic model is the reason that we can’t prevent over 43,000 people from dying in traffic accidents every year. And that's just the US statistics. There is a better way to do things. Let me explain.

Non-Deterministic Timing

If there is anything more unpredictable and prone to errors than a complex algorithmic program, it is a bunch of algorithms running concurrently, communicating with each other and accessing the same data in memory. That is what threads are, concurrent algorithms. Algorithms are inherently non-deterministic. By this, I mean that the precise timing of the actions (operations) in a complex algorithm cannot be predicted. Why? Because of an inherently non-deterministic construct used in algorithms for decision making (I am talking about the if-then construct). As a result, it is hard to determine when a call to a subroutine, for example, will return. Threads are far worse because context switching and varying CPU load introduce even more uncertainties into the mix.

The Thread Monkeys

So why do the multicore CPU manufacturers want to force thread-based parallelism down our throats even though multithreaded software is bug-prone and hard to develop? The answer is three-fold. First, they don’t know how to make a fine-grain multicore CPU for a MIMD parallel environment; second, they don’t know how to build a non-algorithmic OS and the required development tools, and last but not least, they make a lot of money supporting legacy software and tools. In sum, all they really know is threads. It is up to us, the consumers, to demand better products for our money.

The Solution

The only way to build rock-solid, complex software systems is to use deterministic processes. This means we must change over to a non-algorithmic, synchronous, reactive software model. You may ask, how can one build a parallel system without threads? Consider that programmers of video games, cellular automata, neural networks and simulation-type applications have been doing it for years. We now have cellular automata with thousands and even millions of cells running in parallel. In a fine-grain parallel computer, the cells are the elementary operators (add, subtract, compare, etc…). The only problem is that such a system would be too slow because current CPUs are not designed and optimized for true parallel software. This is the reason that we must design a new kind of multicore CPU, one that is self-balancing and auto-scalable.

How to Prevent Traffic Accidents

The unreliability of the algorithmic software model puts an upper limit on the complexity of our software systems. The real cost of unreliability is much higher than we might suppose. As I wrote elsewhere on this blog, we could conceivably be riding in self-driving vehicles right now (yes, it can be done without AI), but concern over safety and reliability will not allow it. In addition, the cost of developing safety-critical software rises exponentially with the level of complexity. What will it take to get the Intels, AMDs, IBMs, Googles and Microsofts of the world to do the right thing and switch to the right software model? I really don’t know. All I can do is write articles on my blog and hope that somebody important will take notice and realize the error of our ways. It’s a big task but it must be done. The right model will solve the BIG problem of parallel computing and unreliable software. The world cannot wait any longer. Thousands of people are dying needlessly.

No comments: