Concurrency

With the arrival of LINQ, I wondered what happened to the concurrency features of COmega (formerly Polyphonic C). Apparently, the concepts of asynchronous methods and chords weren’t proven enough to incorporate as a language feature.

Then, I noted via Channel 9 that a small incubation team, the Concurrency and Coordination Runtime team was formed from the COmega project to deliver the technology in the form of a library targeting .NET v2.0. While the library introduces the notion of ports, the concepts, based on join calculus, remain essentially the same. Channel 9 points to additional papers and a CCR wiki.

Additionally, Microsoft demonstrated at the PDC two other more distant research projects. All of these technologies introduce new declarative constructs that eliminate the cognitive burden that prevent widespread use of concurrency.

• CONCUR — a set of extensions to C++ to provide for higher-level abstraction for concurrent programming such as active objects, messages, futures, parallel loops and parallel STL algorithms.
  
  CONCUR is the baby of Herb Sutter, who earlier published Dr. Dobbs articles “The Free Lunch is Over” and a followup, ACM Queue paper, on the imminent slowdown of Moore’s Law and the upcoming concurrency revolution with the rise of multicore.  Single-threaded applications will no longer experience substantial performance boosts from future technological advancements. Languages and software tools must evolve to meet the concurrency need. Herb presented CONCUR during his PDC talk, TLN309, as a possible way to introduce heavy parallelism into traditional applications.
  
  
• Software Transactional Memory (SXM) — uses transactions instead of locks to synchronize shared data, thereby avoiding deadlocks, priority inversion and fault-intolerance. SXM provides composable “atomic” blocks and also the ability to “retry” a transaction. SXM has been successfully implemented in Haskell language. Microsoft Research has released an experimental project illustrating how SXM might be applied to C# through the use of attributes, tools and libraries.

Other projects mentioned at the Concurrency Futures PDC talk (FUN323) were RaceTrack and Spec#, both of which attempt to verify that multithreaded code is written correctly.

CCR and SXM only run under the .NET platform. CONCUR, built on C++, will probably supports both native and managed implementations; if successful, the technology will probably migrate to the other .NET languages.

All of these concurrency technologies are complementary. SXM provides a simplified, lock-free and correct mechanism for atomicity using a transactional model, doing for concurrency what garbage collection does for memory. CCR introduces declarative coordination via asynchronous methods (messages) that replace the need for low-level event objects. CONCUR makes it easier to introduce high-levels of parallelism to code that is normally written within a single thread.  To take advantage of multicore processors, one can simply add an “active” keyword to a choice body of code such as a loop or simply makes a function call asynchronous and capture the return value as a “future,” whose evaluation is deferred until needed. Herb Sutter wants to see typical applications, running with hundreds of threads active.

Some of the ideas of CONCUR, such as futures and parallel foreach loops, are actually easy to replicate in a library. One could mimic a parallel foreach loop by writing a static method, ParallelForEach, that takes an IEnumerable<T> collection and an Action<T>, representing the body; the function would return as soon as the actions of all elements have completed.

 

Comments

[Chris Nahr]

Concurrent for/next loops have been in Fortran for quite a while (Fortran 90 standard, and some special parallel versions).

The problem is data interdependency. What if the value of x(n) depends on the value of one or more x(m|m < n) in some fashion? x(m) might be required to calculate x(n), or x(m) might cause the loop to break and return a value while x(n) is still being computed.

Do you attempt to detect these conditions? And if so, do you attempt to automatically synchronize such dependencies, or do you simply turn off parallelization for such loops?

Parallelizing loops without any sort of data dependency between cycles is an old hat (that's what Fortran does). The problem is, that's not terribly useful outside of matrix calculations.

Parallelizing loops with arbitrary data dependency is an unsolved problem AFAIK. I would certainly be nice if one of these new technologies could solve it, though!

[Mike Gale]

I've heard suggestions that SQL Server can run slower on hyperthreaded processors!!

As time goes on the issue becomes code that can handle the CPU config...

One issue is how does that impact development time. The conventional techniques are bogged down with all sorts of cross cutting concerns, that make the gap between idea and running software a very big gap indeed.

With clean effective language / CLR design it might be possible to annihilate much of that gap!! I'm not convinced we're there yet. What I also see is long lead times in language development (C Omega, Mondrian, IronPython, F# seem to take forever to impact production languages).