I recently spent an hour on the phone to talk concurrency with DevX’s Alexa Weber Morales. Part 1 of that interview just went live on the web, and focuses mostly on what concurrency and parallelism are, how to take advantage of multicore chips, and whether concurrency will ever be really accessible to mainstream developers. The site seems to be having intermittent problems displaying the pages; just hit the link a few more times if it doesn’t work right away.

Disclaimer: I am not responsible for the article title (yikes! “whisperer”?! my goodness gracious) and Alexa’s intro blurb is way too kind. But it is true that it’s important for us-the-industry to bring concurrency to the mainstream in a grokkable way, as we have already successfully done with OO and GUIs in the past.

Many of you have kindly sent mail about my Effective Concurrency columns and asking when there’ll be a course. Well, I’m happy to announce that the answer is: May 19-21, 2008.

Here’s the brief information (more details below):

3-Day Seminar: Effective Concurrency

May 19-21, 2008
Bellevue, WA, USA
Developed and taught by Herb Sutter

This course covers the fundamental tools that software developers need to write effective concurrent software for both single-core and multi-core/many-core machines. To use concurrency effectively, we must identify and solve four key challenges:

• Leverage the ability to perform and manage work asynchronously
• Build applications that naturally run faster on new hardware having more and more cores
• Manage shared objects in memory effectively to avoid races and deadlocks
• Engineer specifically for high performance

This seminar will equip attendees to reason correctly about concurrency requirements and tradeoffs, to migrate existing code bases to be concurrency-enabled, and to achieve key success factors for a concurrent programming project. Most code examples in the course can be directly translated to popular platforms and concurrency libraries, including Linux, Windows, Java, .NET, pthreads, and the forthcoming ISO C++0x standard.

Note on class size limit and possible waitlist: There is a hard limit on attendance at this first one (really). But if the registration site says you’ll get waitlisted, don’t give up: Go ahead and sign up anyway because we may be able to put together a second installment of the seminar a week or two later if there’s enough interest.

Finally, here’s a summary of what we’ll cover during the three days.

Fundamentals

• Define basic concurrency goals and requirements
• Understand applications’ scalability needs
• Key concurrency patterns

Isolation: Keep Work Separate

• Running tasks in isolation and communicate via async messages
• Integrating multiple messaging systems, including GUIs and sockets
• Building responsive applications using background workers
• Threads vs. thread pools

Scalability: Re-enable the Free Lunch

• When and how to use more cores 
• Exploiting parallelism in algorithms 
• Exploiting parallelism in data structures 
• Breaking the scalability barrier

Consistency: Don’t Corrupt Shared State

• The many pitfalls of locks–deadlock, convoys, etc.
• Locking best practices
• Reducing the need for locking shared data
• Safe lock-free coding patterns
• Avoiding the pitfalls of general lock-free coding
• Races and race-related effects

Migrating Existing Code Bases to Use Concurrency

Near-Future Tools and Features

High Performance Concurrency

• Machine architecture and concurrency
• Costs of fundamental operations, including locks, context switches, and system calls
• Memory and cache effects
• Data structures that support and undermine concurrency
• Enabling linear and superlinear scaling

I hope to get to meet some of you here in the Seattle area!

There are two main ways to achieve superlinear scalability, or to use P processors to compute an answer more than P times faster…:

• Do disproportionately less work.
• Harness disproportionately more resources.

Last month, we focused on the first point by illustrating parallel search and how it naturally achieves superlinear speedups when matches are not distributed evenly because some workers get "rich" subranges and will find a match faster, which benefits the whole search because we can stop as soon as any worker finds a match.

This month, we’ll conclude examining the first point with a few more examples, and then consider how to achieve superlinear speedups by harnessing more resources—quite literally, running on a bigger machine without any change in the hardware. …

In "Break Amdahl’s Law!", I described ways to enable scalable applications, and wrote in part:

But don’t show me ray-traced bouncing balls or Mandelbrot graphics or the other usual embarrassingly parallel but niche (or downright useless) clichés—what we’re looking for are real ideas of real software we could imagine real kids and grandmothers using that could become possible on manycore machines. Here’s a quick potential example: Researchers know how to do speech recognition with near-human-quality accuracy in the lab, which is astonishingly good and would enable breakthrough user interfaces if it could be done that reliably in real time. The only trouble is that the software takes a week to run…on a single core. Can it be parallelized, and if so how many cores would we need to get a useful answer in a useful time? Bunches of smart people (and the smart money behind them) are investing hard work not only to find out the answer to that question, but also to find more questions like it.

Just to be clear, in the first sentence above I didn’t mean to say that the standard demos are useless — far from it (see below). This was intended to be a challenging call to action to not be satisfied with demos alone, but for us as an industry to imagine and develop compelling mainstream end applications that are multicore- and manycore-scalable. (To make that clearer, I’m going to ditch and rewrite the first sentence above for the Effective Concurrency book.)

The standard demos are indeed important — not only as proofs of concept, that the technology really does enable scalable parallel code, but at least as importantly as helpful tools in helping us to understand how a given parallel technology or runtime works.

To understand concurrency mechanics/characteristics

For example, consider a standard Mandelbrot-rendering demo, but with the twist that each worker thread (core) renders its portion of the work in a different color. On a traditional runtime with static scheduling, some workers with easy-to-compute sections will be done early and wait idly while the other workers finish their harder-to-compute sections, and we can see visually that each colored section is the same size and some colored sections appear faster than others. But on a runtime with dynamic scheduling, and especially one that supports Cilk-style work stealing, we get efficient load balancing where workers who are assigned "easy" sections and are done early can contribute to remaining work in harder-to-compute areas — and visually some sections fill in with one color but then the same color starts to add to other yet-unfinished sections. The bands of color let us see which worker did what work and helped out in what other areas, and the overall visual progress of the whole image lets us see that the system as a whole is doing useful work the whole time. So the colored Mandelbrot demo is a very useful tool to let us understand what’s going on quickly and clearly, in a way that presenting the results in a numerical table can’t.

To illustrate a path to future applications

Similarly, ray-tracing may well make multicore and manycore CPUs the future of photorealistic graphics in a way that may not be applicable to standard GPUs (time will tell). As shown in the blogs below, ray-tracing makes a qualitative difference in the nature of lighting models. But can’t we do this already with GPUs? Interestingly, not necessarily; ray-tracing seems to represent an algorithm that is hard to accelerate with GPUs with limited abilities to do the fine-grain scheduling that runtimes based on techniques like work stealing are well suited to do. Some links:

• Intel’s ray-tracing summary and why it’s important
• Followup addressing caveats, why ray-tracing isn’t necessarily the best choice for everything, but still important

Yes, demos are useful

My point in the original quote above (which I see I could have stated more clearly) was simply this: Once we’ve achieved the demos, we shouldn’t sit back and declare victory. The demos aren’t the end goal; we still need the applications.

Concurrency demos are useful to help prove a technology can scale and to understand how it works, and some of them show potentially fruitful and exciting paths to real and compelling manycore-exploiting applications, but it’s still up to us as an industry to continue to imagine and build those applications. I believe that we can and will.

We spend most of our scalability lives inside a triangular box, shown in Figure 1. It reminds me of the early days of flight: We try to lift ourselves away from the rough ground of zero scalability and fly as close as possible to the cloud ceiling of linear speedup. Normally, the Holy Grail of parallel scalability is to linearly use P processors or cores to complete some work almost P times faster, up to some hopefully high number of cores before our code becomes bound on memory or I/O or something else that means diminishing returns for adding more cores. As Figure 1 illustrates, the traditional shape of our "success" curve lies inside the triangle.

Sometimes, however, we can equip our performance plane with extra tools and safely break through the linear ceiling into the superlinear stratosphere. So the question is: "Under what circumstances can we use P cores to do work more than P times faster?" There are two main ways to enter that rarefied realm:

• Do disproportionately less work.
• Harness disproportionately more resources.

This month and next, we’ll consider situations and techniques that fall into one or both of these categories. …