Threads are Dead

Gary Smith, Gary Smith EDA

"DAC always makes you walk away with many impressions. Sometimes one stands out more than the others. Last year we were happy to hear that “It’s the Software Stupid” resonated with many engineers. This year the one that stuck in my mind was a statement made by Professor Wen-mei Hwu from the University of Illinois at Urbana –Champaign, during the Thousand-Core Chips panel. He said, 'Threads are dead.'

Of course there is the nondeterministic feature of threading. The fact that threaded programs are almost unverifiable is a nuisance in EDA tool development but it is a critical issue in Embedded multi-core programming; and yes software engineers are entering the wonderful world of verification. That of course is why Professor Hwu pronounced threads dead.

Of course the best of all would be a concurrent language with all of the programming infrastructure needed for parallel architectures."

The Challenges of Synthesizing Hardware from C-like Languages

Prof. Stephen Edwards, Columbia, IEEE Design Test Comput., pp. 375-386, Sept-Oct 2006

"The main reason people have proposed C-like languages for hardware synthesis is familiarity. Proponents claim that by synthesizing hardware from C, we can effectively turn every C programmer into a hardware designer. Another common motivation is hardware-software codesign: Designers often implement today’s systems as a mix of hardware and software, and it’s often unclear at the outset which portions can be hardware and which can be software. The claim is that using a single language for both simplifies the migration task. 

I argue that these claims are questionable and that pure C is a poor choice for specifying hardware. On the contrary, the semantics of C and similar imperative languages are distant enough from hardware that C-like thinking might be detrimental to hardware designers."  

The Problem with Threads

Prof. Edward Lee, UC Berkeley, Jan 10 2006, Technical Report No. UCB/EECS-2006-1

"Concurrency in software is difficult. However, much of this difficulty is a consequence of the abstractions for concurrency that we have chosen to use. The dominant one in use today for general- purpose computing is threads. But non-trivial multi-threaded programs are incomprehensible to humans. It is true that the programming model can be improved through the use of design patterns, better granularity of atomicity (e.g. transactions), improved languages, and formal methods. 

However, these techniques merely chip away at the unnecessarily enormous nondeterminism of the threading model. The model remains intrinsically intractable. If we expect concurrent programming to be mainstream, and if we demand reliability and predictability from programs, then we must discard threads as a programming model. Concurrent programming models can be constructed that are much more predictable and understandable than threads. They are based on a very simple principle: deterministic ends should be accomplished with deterministic means. Nondeterminism should be judiciously and carefully introduced where needed, and should be explicit in programs. This principle seems obvious, yet it is not accomplished by threads. Threads must be relegated to the engine room of computing, to be suffered only by expert technology providers."

Quo Vadis, SLD?

Prof. Alberto Sangiovanni-Vincentelli, UC Berkeley, Proceedings of the IEEE, Vol. 95, No. 3, March 2007

"Because of the popularity and the efficiency of C, several approaches for raising the levels of abstraction for hardware design are based on C and its variants. C has been used successfully to represent the high-level functional behavior of hardware systems and to simulate its behavior. A simulation amounts to running the compiled C code and hence is very fast, limited by the speed of the simulation host and by the quality of the compiler.

The main problem with this approach is the lack of concurrency and of the concept of time in C. In fact, hardware is inherently concurrent and time is essential to represent its behavior accurately. In addition, C has been designed with standard programming application in mind and in its constructs, it relies upon standard communication mechanisms through memory that are inadequate, to say the least, for hardware representation."

ANSI C won't work for ESL

Mike Meredith, Forte Design Systems, EETimes May 10 2007

"The unsuitability of existing software-oriented C or C++ source code for creation of hardware implementation stems from the origin of these languages. Dennis Richie, the developer of the C language has described it and its predecessor BCPL as "close to the machine" in that the abstractions they introduce are readily grounded in the concrete data types and operations supplied by conventional computers. C and C++ naturally implement:

•  
  • A single process with sequential execution 
  • Variables of only a few specific sizes 
  • A single, relatively large, addressable memory 
  • Communication through subroutine parameters, function call return values, and by passing a pointer to data stored in memory

Contrast this with the characteristics of an efficient hardware implementation:

•  
  • Multiple blocks executing in parallel for maximum throughput 
  • Variables with bit-widths carefully tuned to conserve every flip-flop 
  • Dedicated point-to-point communication channels and hierarchical bus structures to maximize parallelism and available bandwidth"

Programming Models for Parallel Systems: The Programmers Perspective

"There has been much work on compiling C or C-like languages to hardware. With a few notable exceptions, there has been limited progress in this area. The author believes that starting from C one has already introduced so much unnecessary sequentiality that it is often impossible to recover the potential parallelism in the original algorithm. Furthermore, C does not have explicit constructs for expressing concurrency or parallelism and this makes it even more difficult to devise automatic parallelization flows."

The free lunch is over: A fundamental turn to concurrency in software

"Concurrency is the next major revolution in how we write software. Different experts still have different opinions on whether it will be bigger than OO, but that kind of conversation is best left to pundits. For technologists, the interesting thing is that concurrency is of the same order as OO both in the (expected) scale of the revolution and in the complexity and learning curve of the technology. 

Programming languages and systems will increasingly be forced to deal well with concurrency. The Java language has included support for concurrency since its beginning, although mistakes were made that later had to be corrected over several releases in order to do concurrent programming more correctly and efficiently. The C++ language has long been used to write heavy-duty multithreaded systems well, but it has no standardized support for concurrency at all (the ISO C++ standard doesn’t even mention threads, and does so intentionally), and so typically the concurrency is of necessity accomplished by using nonportable platform-specific concurrency features and libraries. (It’s also often incomplete; for example, static variables must be initialized only once, which typically requires that the compiler wrap them with a lock, but many C++ implementations do not generate the lock.) Finally, there are a few concurrency standards, including pthreads and OpenMP, and some of these support implicit as well as explicit parallelization. Having the compiler look at your single-threaded program and automatically figure out how to parallelize it implicitly is fine and dandy, but those automatic transformation tools are limited and don’t yield nearly the gains of explicit concurrency control that you code yourself. The mainstream state of the art revolves around lock-based programming, which is subtle and hazardous. We desperately need a higher-level programming model for concurrency than languages offer today."