One of the challenges when designing reusable software that employs hidden parallelism -- such as a BCL API that parallelizes sorts, for-all style data parallel loops, and so forth -- is deciding, without a whole lot of context, whether to run in parallel or not. A leaf level function call running on a heavily loaded ASP.NET server, for example, probably should not suddenly take over all 16 already-busy CPUs to search an array of 1,000 elements. But if there's 16 idle CPUs and one request to process, doing so could reduce the response latency and make for a happier user. Especially for a search of an array of 1,000,000+ elements, for example. In most cases, before such a function "goes parallel," it has to ask: Is it worth it?

Answering this question is surprisingly tough. Running parallel at a high level might be more profitable, such as enabling multiple incoming ASP.NET requests to be processed, but often fine-grained parallelism can lead to better results. And just as often, a combination of the two works best. Consider an extreme case: Imagine that most ASP.NET web requests for a particular site ultimately acquire a mutual exclusive lock on a resource, essentially serializing a portion of all web requests. Of course, this is a design that's going to kill scalability eventually. But regardless, it could be present to a lesser degree, and might actually be an architectural requirement of the system. Executing some finer-grained operations in parallel might lead to better throughput in this case, especially those performed while the lock is held.

And clearly, the act of parallelizing an algorithm is not just based on the static properties of the system itself, but also dynamic capabilities and utilization of the machine. There are some APIs that allow dynamic querying of the machine state, which can aid in this process, e.g.:

• System.Environment.ProcessorCount: This property (new in 2.0) tells you how many hardware threads are on the system. Note that the number includes hyper-threads on Intel architectures, which really shouldn't be counted as a full parallel unit when deciding whether to parallelize your code. GetSystemInfo can give you richer information, albeit with some P/Invoke nonsense. We should give a better interface into this data for the next version of the Framework.
• Processor:% Processor Time performance counter: This gives you the % utilization of a specific processor and allows asynchronous querying. Using it, you could query each processor on the system to figure out what the overall system utilization is, and specifically how many sub-parts to break your problem into. The CLR thread-pool uses this today to decide when to inject or retire threads. You can use it too to determine whether introducing parallelism is a wise thing to do. Although your code may not have a lot of "context," this is often a good heuristic that even leaf level algorithms can use.
• System:Processor Queue Length performance counter: For more sophisticated situations, you can not only key off of the processor utilization, but also off the queue length of processes waiting to be scheduled. For a really deep queue (say, more than 2x the number of processors), introducing additional work is likely to lead to unnecessary waiting.

Using these are apt to lead to statistically good decisions. But clearly this is a heuristic, and as such the state of the system could change dramatically immediately after obtaining the values, perhaps making your deicision look naive and ill-conceived in retrospect. The worst case could be bad, but perhaps not terrible. The worst aspect of this is that performance characteristics could vary dramatically, and your users might respect predictable execution over sometimes-fast execution. The good news is that each of these functions are fairly cheap to call, amounting to less than 0.5ms total in some quick-and-dirty tests I wrote that read from all three.

But spending any time answering the question is tricky business. Assuming the software dynamically executes some code to decide if, and to what degree, we should run in parallel, and assuming these calculations are not done in parallel themselves ;), all of this work amounts to a fixed overhead on some part of the overall system, reducing overall parallel speedup (due to Amdahl's Law). We hope that in the future we can hide a lot of this messy work in the guts of the runtime and WinFX stack, but for now it's mostly up to you to decide.

Databases have utilized parallelism for a long time now to effectively scale-up and scale-out with continuously improving chip and cluster technologies. Consider a few high-level examples:

Parallel query execution is employed by all sophisticated modern databases, including SQL Server and Oracle. This comes in two flavors: (1) execution of multiple queries simultaneously which potentially access intersecting resources, and (2) implicit parallelization of individual queries, to acheive speed-ups even when a large quantity of incoming work is not present (e.g. high-cost queries, lots of data, etc.). Often a combination of both is used dynamically in a production system. I won't say much more, other than to refer to an interesting new query technology on the horizon.

Transactions are used as a simple model for concurrency control, enabling high scalability due to dynamic fine-grained locking techniques and policies, while supplying conveniences such as intelligent contention management and deadlock detection. And of course reliability is improved, because of the all-or-nothing semantics of transactions. Even in the face of asynchronous thread aborts, a transaction can ensure inconsistent state isn't left behind to corrupt a process, greatly improving the reliability of software at a surprisingly low cost. Software transactional memory (STM) borrows directly from the field, and applies it to general purpose parallel programming.

Invariants about data in databases are often modeled as integrity checks and foreign key constraints, which help to maintain reliable and consistent execution even in the face of concurrency. This, coupled with transactions, helps to ensure invariants aren't broken at transaction boundaries, and recent work done by MSR explores how this might be applied to general programming. STM combined with a rich system like Spec# could facilitate highly reliable and consistent systems that don't expose latent race conditions in the face of parallel execution.

Assuming you have (1) a lot of data to process, (2) complex computations to perform, and/or (3) simply a lot of individual tasks to accomodate, this model of parallel programming stretches quite far. With many cores per CPU, TB disks, and 100+-GB memories on desktops just around the corner; an order of magnitude more network bandwith available to consumers; and a continuing explosion of the amount of information humans generate and have to make some sense of, similar approaches could enable the next era of computer applications. I will also observe that surprisingly similar models of computation are precisely what fuel technologies like Google's MapReduce, albeit at a coarser granularity.

Raymond's recent post talks about queueing user-mode APCs in Win32.

When you block in managed code, the CLR is responsible for figuring out the correct style of wait. This ends up in a CoWaitForMultipleHandles (on Win2k+) or MsgWaitForMultipleObjectsEx if you're executing in an STA; else, this ends up in a non-pumping wait, such as WaitForSingleObjectEx/WaitForMultipleObjectsEx. In any case, the wait is alertable, meaning that user-mode APCs will have a chance to run. There are various blocking calls hidden in Win32 and the CLR itself, so it's not guaranteed that all waits are alertable; but any that originate from managed code are, which we hope is a significant percentage.

This code illustrates a simple user-mode APC reentering as we do an alertable wait (via Thread.CurrentThread.Join(0)):

using System;
using System.Runtime.InteropServices;
using System.Threading;

static class Program {

    static void Main() {
        QueueUserAPC(
            delegate { Console.WriteLine("APC fired"); },
            GetCurrentThread(),
            UIntPtr.Zero);

        Console.WriteLine("Doing join");
        Thread.CurrentThread.Join(0);
        Console.WriteLine("Finishing join");
    }

    delegate void APCProc(UIntPtr dwParam);

    [DllImport("kernel32.dll")]
    static extern uint QueueUserAPC(APCProc pfnAPC,
        IntPtr hThread, UIntPtr dwData);

    [DllImport("kernel32.dll")]
    static extern IntPtr GetCurrentThread();

}

While this technique seems like an effective way to reuse a thread while it is blocked -- for example, you might contemplate doing this for thread-pool threads -- a little problem called thread affinity tends to arise. I wrote about this in terms of COM reentrancy before. An APC reentering doesn't perform a context transition, so even if we used a logical context to store such state, the problem would still exist. The simple fact is that user-mode APCs are good for system bookkeeping, but not for running general purpose code that modifies arbitrary program state.

I don't know what's publicly available about our future ship schedules. But regardless, we begin M1 -- our first real coding milestone for the next version of the CLR -- on Monday. There's been some work going on in the meantime, of course, limited mostly to prototyping, design, and prioritization, but it's finally time to get serious, write real product code, and start hitting dates.

One fairly large item on our schedule is revamping our thread-pool. Our primary aim there is to enable fine-grained parallelism, and to supply new scheduling features that many people have asked for in the past. Today, coarse-grained parallelism is more attractive due to the costs associated with scheduling and dispatching work items, but we are going to change that.

This includes these tentative high level items:

• Low performance overhead of queueing and dispatching work
• Deadlock avoidance (surging) due to 100% blocking
• Queue partitioning and isolation
• Prioritization of work items
• Cancellation of work items, possibly with support for Vista IO Cancellation
• NUMA awareness such as CPU affinitization and/or user-hinted node affinitization
• And, of course, enhanced debugging and diagnostics

We'd love any feedback on any of these, including which sound more or less important to you. And if you have an interesting problem or scenario we might not have considered, please, please, please let me know.

A colleague of mine recently referred me to the Cilk work at MIT. This paper supplies a good overview. We've been slowly arriving at a similar design, so it's great to have prior art from which to draw. The idea most important with respect to the thread-pool is how multiple queues can be backed by a single physical thread store, and further the way in which queues are dynamically load balanced via thread leases and work stealing.

By now you’ve probably read things like Herb Sutter’s free lunch paper. And if you follow my blog at all, you’ll know that I do a bit of writing and thinking about how Microsoft can make our platform better suited for the multi-core era that stands in front of us.

Most people, when considering the topic of parallelism vis-à-vis multi-core, start by jumping straight to the bottom of the stack. I’ll admit that I sure did. They think about threads, locks, and the associated headaches. Some even think about the chip architecture and memory hierarchy. They take it for granted that the work exists. But these same people seldom stop to think—or when they do think often hit the same wall—about what workloads will actually substantially benefit from massive amounts of parallelism. This is a difficult topic.

Scientific computing of course has this nailed pretty good already. But how much of the code do you write that actually resembles scientific problems, like n-bodies, heat transfer, fluid dynamics, and the like? My guess is that, for most of Microsoft’s customers, the answer is: Not much. That’s especially true on the client, where data-intensive operations are often shipped to a high-end server for processing, leaving what amounts to quasi-workflow orchestration initiated by UI events, for example. I’m not going to refute the massive gains in CPU scalability we’ve seen over the past 10 years due to superscalar execution, via techniques like pipelining and branch prediction, and the effect that has had on client and server programs alike. But for most application code today, the network and disk are the limiting factors, not the CPU.

Of course, to the extent that there is work the CPU must perform for any problem—even for IO-bound ones—code needs to be architected to separate logical tasks, ensuring that a bunch of otherwise ready-to-run work doesn’t get backed up behind a blocking call unnecessarily. And of course, separating logical work is important for other reasons, like avoiding a hung UI thread. Unfortunately, we don’t make this overly easy today. Win32 and WinFX APIs (nor the associated documentation or tool support) are not overly helpful when it comes to figuring out the performance characteristics of the code they invoke, including latency and blocking. This makes it tricky to architect things as I suggest. New programming models like the CCR provide the infrastructure that could facilitate such a shift, but it will take hard work to get to a reasonable place.

Back to workloads. Consider server applications for a moment. The model of concurrency there is actually quite simple. And in fact I believe the majority of server programs will be equipped to exploit multi-core right away. Each incoming request is considered a logical task and is assigned to an available thread of work, often using the CLR’s thread-pool. Sharing between concurrent requests is (hopefully) minimal, meaning that the one-thread-per-request model leads to naturally good scaling. This works up to a point. Once the average number of available CPUs surpasses the average number of incoming workers, the need to assign multiple CPUs to a single request becomes more important. This is obviously very workload dependent. Databases already do this with individual queries. Their use a single-thread-per-request model, but often use individual query parallelization to get better utilization. SQL Server added support for this in 7.0. I’ve been working quite a bit over the past year on similar techniques for LINQ. I’m almost to the point where I can disclose more information publicly, in the form of a paper.

Search is clearly a workload of recent importance that, whether on the client or server, benefits tremendously from parallel execution. This applies not only to the act of searching, but also to the act of indexing the data in preparation for search. MSN and Google’s current desktop search products are cognizant not to interrupt your primary work by doing indexing while your computer is idle. But given a bunch more cores, they needn’t wait. Further, parallelizing search is a well researched topic. You still need to solve some tough problems like ensuring parallel tasks aren’t contending heavily for the disk (becoming IO bound), but it’s very possible.

There are of course other workloads. Graphics processing on modern computers is extremely parallel, currently handled by the GPU. But I am going to wrap up, and summarize all of this by saying: It remains to be seen whether most mainstream Windows programs can become highly parallel, and if they can, how profitable it will be. We'll also find out over time whether reaching that stage will require radically new programming models and a gradual shift over time. I am optimistic, and confident that parallel execution is the direction we ultimately need to go down. Surely the workloads are there, seemingly obscured by the traditional sequential approach to software.

I'm writing an article for an upcoming MSDN Magazine CLR Inside Out column. And I am looking for topic suggestions.

Of course, my expertise is around concurrency, but I'm also a CLR internals-kinda geek. So, what do you want to read about?

I have some ideas. But I'll post them after I hear yours.

I wrote about torn reads previously, in which, because loads from and stores to > 32-bit data types are not actually "atomic" on a 32-bit CPU, obscure magic values are seen in the program from time to time. This isn't as scary as "out of thin air" values, but can be troublesome nonetheless. I noted that, by using a lock, you can serialize access to the location to ensure safety.

You can of course write such thread-safe code that avoids taking a lock, usually motivated by performance. Vance has a pretty detailed write-up of this on MSDN. Most of the time, you shouldn't try to be so clever, as it will get you in trouble sooner or later, and is even worse to debug than a typical race. But for really hot code-paths, it can make a measurable difference. (Note the key word: measurable. If you've measured a problem, you might consider such techniques... but otherwise, stay far, far away. (Have I made enough qualifications and disclaimers yet?))

If you access individual pointer-sized byte segments of the data structure, such as 32-bit aligned segments (e.g. volatile or __declspec(align(x)) in VC++, all values on the CLR), you can load and store in a known order. Furthermore, you need to use the appropriate types of loads and stores with fences in the appropriate places; load/acquire and store/release are usually adequate. You can then use the intrinsic properties of this order to make statements about the correctness of your algorithm.

For example, imagine you have some code that increments a 64-bit counter on a 32-bit system. Aside from overflow, the value always increases. If you always increment the low 32-bits, followed by the high, and if you always read the high, followed by the low, you'll be guaranteed that, should you read a torn value, it will be too low rather than too high (not counting for overflow, of course). Sometimes it can be really low, such as when the low 32-bits wrap back to 0, in which case the higher 32-bit increment needs to carry one. Depending on your situation, this might be precisely what you are looking for. (I wrote some code last week that needed exactly this.)

For example, your typical code might read and write under a lock, in VC++/Win32:

ULONGLONG ReadCounter_Lock(
    volatile ULONGLONG * pTarget, CRITICAL_SECTION * pCs)
{
    ULONGLONG val;

    EnterCriticalSection(pCs);
    val = *pTarget;
    LeaveCriticalSection(pCs);

    return val;
}

ULONGLONG IncrCounter_Lock(
    volatile ULONGLONG * pTarget, CRITICAL_SECTION * pCs)
{
    ULONGLONG val;

    EnterCriticalSection(pCs);
    val = *pTarget;
    *pTarget = val + 1;
    LeaveCriticalSection(pCs);

    return val;
}

But, using the load/store order described above, it can become lock free:

#define LO_LONG(x) (reinterpret_cast<volatile LONG *>((x)))
#define HI_LONG(x) (reinterpret_cast<volatile LONG *>((x)) + 1)

ULONGLONG ReadCounter_NoLock(volatile ULONGLONG * pTarget)
{
    ULONGLONG val;

#ifdef _Win64

    val = *pTarget;

#else

    // Read high 32-bits first, then low:
    *HI_LONG(&val) = *HI_LONG(pTarget);
    *LO_LONG(&val) = *LO_LONG(pTarget);

#endif

    return val;
}

ULONGLONG IncrCounter_NoLock(
    volatile ULONGLONG * pTarget)
{
    ULONGLONG oldVal;

#ifdef _Win64

    oldVal = static_cast<LONGLONG>(
        InterlockedIncrement64(static_cast<LONGLONG *>(pTarget)));

#else

    // Increment the low 32-bits first, then high:
    if ((*LO_LONG(&oldVal) =
        InterlockedIncrement(LO_LONG(pTarget))) == 0)
    {
        *HI_LONG(&oldVal) = InterlockedIncrement(HI_LONG(pTarget));
    }
    else
    {
        *HI_LONG(&oldVal) = *HI_LONG(pTarget);
    }

#endif

    return oldVal;
}

It's obvious which is simpler to code, understand, and maintain. But the latter technique can come in handy when you're in a pinch.

For information on other similar techniques, including multi-word CAS and object-based STM, Tim Harris's recent "Concurrent programming with locks" paper is an excellent read. Most of it isn't built and ready for you to use today, but the details of the algorithms are in there if you'd like to play around a little. And there's a lot of literature out there about creating lock-free data structures. Interestingly, you can end up worse off than if you'd used a lock in the first place. Many such lock free algorithms are optimistic meaning that they do a bunch of work hoping not to run into contention; when they do, they have to throw away work, rinse, and repeat. Your mileage can vary dramatically based on workload.

I was in Las Vegas for the better part of last week. Aside from winning money (for once), I also ate at some great places: the 5-course prix fixe menu at Michael Mina (northwest seafood, at the Bellagio), Bartolotta (modern Italian, at the Wynn), brunch at the Mesa Grill (southwestern, at Caesar's Palace), Olives (new Mediterranean, at the Bellagio), and the best of all, the 16-course prix fixe at Joël Robuchon at The Mansion (modern French, at the MGM Grand).

In fact, Joël Robuchon's beat my favorite two dining spots to date: Aujourd'hui, and the Herbfarm. Not to mention that they were nice enough to accomodate and craft up an entirely custom 16-course vegetarian tasting menu. Dinner came complete with fancy scroll-like copies of the menus to take home, wrapped in purple silk. But I figured I'd also digitize it to help remember. Here's the non-vegetarian menu:

Joël Robuchon at The Mansion
March 25th, 2006

Menu Dégustation
Tasting Menu

La Pomme
cuillère de perles, de son jus rafraîchi d’un granite de vodka
Apple pearl, vodka granite

Le Caviar Osciètre
dans une délicate gelée recouverte d’une onctueuse crème de chou-fleur
Oscetra caviar topped with a delicate gelée and a smooth cauliflower cream

Le Foie Gras
en mille-feuille caramélise d’anguille fumée aux saveurs orientales
Foie gras, mille-feuille of smoked eel with oriental flavors

Le Thon
en tartare, poivron rouge confit a la bergamote et au jambon sèche
Tuna tartar, cold red bell pepper confit with bergamot and dry cured ham

La Langoustine
truffée et cuite en ravioli a l’étuvée de chou vert
Truffled langoustine ravioli with steamed green cabbage

La Laitue
en fin veloute sur un flan tremblotant a l’oignon doux
Light lettuce cream on top of a delicate sweet onion custard

La Noix de Saint-Jacques
en cannelloni aux courgettes sous un voile de lard d’Arnad et une émulsion de parmigiano
Cannelloni of scallops and zucchini, parmesan emulsion

Le Homard
au coulis de pissenlit avec quelques feuilles crues de barbes-de-capucin relevées d’une vinaigrette coralline
Lobster, pissenlit coulis, capucin leaves and sea urchin vinaigrette

L’Os a Mœlle
de bœuf de Kobe aux légumes printaniers
Kobe beef bone marrow, spring vegetables

L’Ormeau
et l’artichaut poivrade dans un court bouillon au gingembre
Abalone, baby artichokes in a ginger bouillon

Le Bar
pole a la citronnelle avec une étuvée de jeunes poireaux
Pan-fried sea bass with a lemon grass foam and stewed baby leeks

L’Amadai
cuit en écailles et servi sur une nage au yuriné
Amadai in a lily bulb broth

Le Veau
en cote au plat avec un jus gras et escorte de taglierinis de légumes au pistou
Sautéed veal chop with natural jus and vegetable taglierinis flavored with pesto

L’Epeautre
du pays de Sault mitonne et dore a la feuille d’or
Sault wild oatmeal, gold leaf

Le Bahia
en fin crémeaux de papaye, jus de cassis
Guava and papaya granite, cream of cassis and orange macaroon

La Fraise
glacée aux coquelicots, en popcorns caramélises, sirop de cachaça
Poppy sorbet, caramelized popcorns, cachaça syrup

Le Café Express
Espresso

Petits Fours

Yes, this was a tasting menu. It was not a la carte. I ate each of those dishes in the course of about 4 1/2 hours. And had a 2002 Puligny-Montrachet 1er Cru, Les Pucelles to go along with all of it. Yes, just one bottle. Excess was not on the agenda for that night...

Wow, not only does Vance Morrison have a blog--he's a performance architect on the CLR team--but he recently wrote two articles on reader-writer locks:

• Low-lock techniques in action: implementing a reader-writer lock
• Analysis of reader-writer lock

In them, he walks through a custom implementation of a lock, and then does some insightful performance analysis on it. As usual with Vance's writing, it's very detailed and precise.