Why Concurrency and Parallelism?

There are many reasons to introduce multiple threads of control into your applications. This book is dedicated to improving application performance, and indeed most reasons for concurrency and parallelism lie in the performance realm. Here are some examples:

• Issuing asynchronous I/O operations can improve application responsiveness. Most GUI applications have a single thread of control responsible for all UI updates; this thread must never be occupied for a long period of time, lest the UI become unresponsive to user actions.
• Parallelizing work across multiple threads can drive better utilization of system resources. Modern systems, equipped with multiple CPU cores and even more GPU cores can gain an order-of-magnitude increase in performance through parallelization of simple CPU-bound algorithms.
• Performing several I/O operations at once (for example, retrieving prices from multiple travel websites simultaneously, or updating files in several distributed Web repositories) can help drive better overall throughput, because most of the time is spent waiting for I/O operations to complete, and can be used to issue additional I/O operations or perform result processing on operations that have already completed.

Task Parallelism

Task parallelism is a paradigm and set of APIs for breaking down a large task into a set of smaller ones, and executing them on multiple threads. The Task Parallel Library (TPL) has first-class APIs for managing millions of tasks simultaneously (through the CLR thread pool). At the heart of the TPL is the System.Threading.Tasks.Task class, which represents a task. The Task class provides the following capabilities:

• Scheduling work for independent execution on an unspecified thread. (The specific thread to execute a given task is determined by a task scheduler; the default task scheduler enqueues tasks to the CLR thread pool, but there are schedulers that send tasks to a particular thread, such as the UI thread.)
• Waiting for a task to complete and obtaining the result of its execution.
• Providing a continuation that should run as soon as the task completes. (This is often called a callback, but we shall use the term continuation throughout this chapter.)
• Handling exceptions that arise in a single task or even a hierarchy of tasks on the original thread that scheduled them for execution, or any other thread that is interested in the task results.
• Canceling tasks that haven’t started yet, and communicating cancellation requests to tasks that are in the middle of executing.

Because we can think of tasks as a higher-level abstraction on top of threads, we could rewrite the code we had for prime number calculation to use tasks instead of threads. Indeed, it would make the code shorter—at the very least, we wouldn’t need the completed task counter and the ManualResetEvent object to keep track of task execution. However, as we shall see in the next section, the data parallelism APIs provided by the TPL are even more suitable for parallelizing a loop that finds all prime numbers in a range. Instead, we shall consider a different problem.

There is a well-known recursive comparison-based sorting algorithm called QuickSort that yields itself quite easily to parallelization (and has an average case runtime complexity of O(nlog(n)), which is optimal—although scarcely any large framework uses QuickSort to sort anything these days). The QuickSort algorithm proceeds as follows:

public static void QuickSort < T > (T[] items) where T : IComparable < T > {
  QuickSort(items, 0, items.Length);
}
private static void QuickSort < T > (T[] items, int left, int right) where T : IComparable < T > {
  if (left == right) return;
  int pivot = Partition(items, left, right);
  QuickSort(items, left, pivot);
  QuickSort(items, pivot + 1, right);
}
private static int Partition < T > (T[] items, int left, int right) where T : IComparable < T > {
  int pivotPos = . . .; //often a random index between left and right is used
  T pivotValue = items[pivotPos];
  Swap(ref items[right-1], ref items[pivotPos]);
  int store = left;
  for (int i = left; i < right - 1; ++i) {
    if (items[i].CompareTo(pivotValue) < 0) {
    Swap(ref items[i], ref items[store]);
    ++store;
    }
  }
  Swap(ref items[right-1], ref items[store]);
  return store;
}
private static void Swap < T > (ref T a, ref T b) {
  T temp = a;
  a = b;
  b = temp;
}

Figure 6-6 is an illustration of a single step of the Partition method. The fourth element (whose value is 5) is chosen as the pivot. First, it’s moved to the far right of the array. Next, all elements larger than the pivot are propagated towards the right side of the array. Finally, the pivot is positioned such that all elements to its right are strictly larger than it, and all elements to its left are either smaller than or equal to it.

The recursive calls taken by QuickSort at every step must set the parallelization alarm. Sorting the left and right parts of the array are independent tasks, which require no synchronization among them, and the Task class is ideal for expressing this. Below is a first attempt at parallelizing QuickSort using Tasks:

public static void QuickSort < T > (T[] items) where T : IComparable < T > {
  QuickSort(items, 0, items.Length);
}
private static void QuickSort < T > (T[] items, int left, int right) where T : IComparable < T > {
  if (right - left < 2) return;
  int pivot = Partition(items, left, right);
  Task leftTask = Task.Run(() => QuickSort(items, left, pivot));
  Task rightTask = Task.Run(() => QuickSort(items, pivot + 1, right));
  Task.WaitAll(leftTask, rightTask);
}
private static int Partition < T > (T[] items, int left, int right) where T : IComparable < T > {
  //Implementation omitted for brevity
}

The Task.Run method creates a new task (equivalent to calling new Task()) and schedules it for execution (equivalent to the newly created task’s Start method). The Task.WaitAll static method waits for both tasks to complete and then returns. Note that we don’t have to deal with specifying how to wait for tasks to complete, nor when to create threads and when to destroy them.

There is a helpful utility method called Parallel.Invoke, which executes a set of tasks provided to it and returns when all the tasks have completed. This would allow us to rewrite the core of the QuickSort method body with the following:

Parallel.Invoke(
    () => QuickSort(items, left, pivot),
    () => QuickSort(items, pivot + 1, right)
);

Regardless of whether we use Parallel.Invoke or create tasks manually, if we try to compare this version with the straightforward sequential one, we will find that it runs significantly slower, even though it seems to take advantage of all the available processor resources. Indeed, using an array of 1,000,000 random integers, the sequential version ran (on our test system) for ∼ 250 ms and the parallelized version took nearly ∼ 650 ms to complete on average!

The problem is that parallelism needs to be sufficiently coarse-grained; attempting to parallelize the sorting of a three-element array is futile, because the overhead introduced by creating Task objects, scheduling work items to the thread pool, and waiting for them to complete execution overwhelms completely the handful of comparison operations required.

private static void QuickSort < T > (T[] items, int left, int right) where T : IComparable < T > {
  if (right - left < 2) return;
  int pivot = Partition(items, left, right);
  if (right - left > 500) {
    Parallel.Invoke(
    () => QuickSort(items, left, pivot),
    () => QuickSort(items, pivot + 1, right)
    );
  } else {
    QuickSort(items, left, pivot);
    QuickSort(items, pivot + 1, right);
  }
}

int i = 0;
Task < int > divideTask = Task.Run(() = > { return 5/i; });
try {
  Console.WriteLine(divideTask.Result); //accessing the Result property eventually throws
} catch (AggregateException ex) {
  foreach (Exception inner in ex.InnerExceptions) {
    Console.WriteLine(inner.Message);
  }
}

public class TreeNode < T > {
  public TreeNode < T > Left, Right;
  public T[] Data;
}
public static void TreeLookup < T > (
  TreeNode < T > root, Predicate < T > condition, CancellationTokenSource cts) {
  if (root == null) {
    return;
  }
  //Start the recursive tasks, passing to them the cancellation token so that they are
  //cancelled automatically if they haven't started yet and cancellation is requested
  Task.Run(() => TreeLookup(root.Left, condition, cts), cts.Token);
  Task.Run(() => TreeLookup(root.Right, condition, cts), cts.Token);
  foreach (T element in root.Data) {
    if (cts.IsCancellationRequested) break; //abort cooperatively
    if (condition(element)) {
    cts.Cancel(); //cancels all outstanding work
    //Do something with the interesting element
    }
  }
}
//Example of calling code:
CancellationTokenSource cts = new CancellationTokenSource();
Task.Run(() = > TreeLookup(treeRoot, i = > i % 77 == 0, cts);
//After a while, e.g. if the user is no longer interested in the operation:
cts.Cancel();

Data Parallelism

Whilst task parallelism dealt primarily with tasks, data parallelism aims to remove tasks from direct view and replace them by a higher-level abstraction—parallel loops. In other words, the source of parallelism is not the algorithm’s code, but rather the data on which it operates. The Task Parallel Library offers several APIs providing data parallelism.

for (int number = start; number < end; ++number) {
  if (IsPrime(number)) {
    primes.Add(number);
  }
}

Parallel.For(start, end, number => {
  if (IsPrime(number)) {
    lock(primes) {
    primes.Add(number);
    }
  }
});

IEnumerable < string > rssFeeds = . . .;
WebClient webClient = new WebClient();
foreach (string url in rssFeeds) {
  Process(webClient.DownloadString(url));
}

IEnumerable < string > rssFeeds = . . .; //The data source need
notbe thread-safe
WebClient webClient = new WebClient();
Parallel.ForEach(rssFeeds, url => {
  Process(webClient.DownloadString(url));
});

int invitedToParty = 0;
Parallel.ForEach(customers, (customer, loopState) = > {
  if (customer.Orders.Count > 10 && customer.City == "Portland") {
    if (Interlocked.Increment(ref invitedToParty) > = 25) {
    loopState.Stop(); //no attempt will be made to execute any additional iterations
    }
  }
});

var results = from customer in customers
          where customer.State == "WA"
          let custOrders = (from order in orders
          where customer.ID == order.ID
          select new { order.Date, order.Amount })
          where custOrders.Count(co => co.Amount >= 10 &&
                   co.Date >= DateTime.Now.AddMonths(−10)) >= 3
          select new { customer.Name, customer.Age };
foreach (var result in results) {
  Console.WriteLine("{0} {1}", result.Name, result.Age);
}

var results = from customer in customers.AsParallel()
    where customer.State == "WA"
    let custOrders = (from order in orders
    where customer.ID == order.ID
    select new { order.Date, order.Amount })
    where custOrders.Count(co => co.Amount >= 10 &&
    co.Date > = DateTime.Now.AddMonths(−10)) >= 3
    select new { customer.Name, customer.Age };
foreach (var result in results) {
  Console.WriteLine("{0} {1}", result.Name, result.Age);
}

List < int > primes = (from n in Enumerable.Range(3, 200000).AsParallel()
    where IsPrime(n)
    select n).ToList();
//Could have used ParallelEnumerable.Range instead of Enumerable.Range(. . .).AsParallel()

C# 5 Async Methods

So far, we considered rich APIs that allow a variety of parallelism solutions to be expressed using the classes and methods of the Task Parallel Library. However, other parallel programming environments sometimes rely on language extensions to obtain even better expressiveness where APIs are clumsy or insufficiently concise. In this section we will see how C# 5 adapts to the challenges of the concurrent programming world by providing a language extension to express continuations more easily. But first, we must consider continuations in the asynchronous programming world.

Often enough, you would want to associate a continuation (or callback) with a specific task; the continuation should be executed when the task completes. If you have control of the task—i.e., you schedule it for execution—you can embed the callback in the task itself, but if you receive the task from another method, an explicit continuation API is desirable. The TPL offers the ContinueWith instance method and ContinueWhenAll/ContinueWhenAny static methods (self-explanatory) to control continuations in several settings. The continuation may be scheduled only in specific circumstances (e.g., only when the task ran to completion or only when the task has encountered an exception), and may be scheduled on a particular thread or thread group using the TaskScheduler API. Below are some examples of the various APIs:

Task < string > weatherTask = DownloadWeatherInfoAsync(. . .);
weatherTask.ContinueWith(_ => DisplayWeather(weatherTask.Result), TaskScheduler.Current);
Task left = ProcessLeftPart(. . .);
Task right = ProcessRightPart(. . .);
TaskFactory.ContinueWhenAll(
  new Task[] { left, right },
  CleanupResources
);
TaskFactory.ContinueWhenAny(
  new Task[] { left, right },
  HandleError,
  TaskContinuationOptions.OnlyOnFaulted
);

Continuations are a reasonable way to program asynchronous applications, and are very valuable when performing asynchronous I/O in a GUI setting. For example, to ensure that Windows 8 Metro-style applications maintain a responsive user interface, the WinRT (Windows Runtime) APIs in Windows 8 offer only asynchronous versions of all operations that might run for longer than 50 milliseconds. With multiple asynchronous calls chained together, nested continuations become somewhat clumsy, as the following example may demonstrate:

//Synchronous version:
private void updateButton_Clicked(. . .) {
  using (LocationService location = new LocationService())
  using (WeatherService weather = new WeatherService()) {
    Location loc = location.GetCurrentLocation();
    Forecast forecast = weather.GetForecast(loc.City);
    MessageDialog msg = new MessageDialog(forecast.Summary);
    msg.Display();
  }
}
//Asynchronous version:
private void updateButton_Clicked(. . .) {
  TaskScheduler uiScheduler = TaskScheduler.Current;
  LocationService location = new LocationService();
  Task < Location > locTask = location.GetCurrentLocationAsync();
  locTask.ContinueWith(_ => {
    WeatherService weather = new WeatherService();
    Task < Forecast > forTask = weather.GetForecastAsync(locTask.Result.City);
    forTask.ContinueWith(__ => {
       MessageDialog message = new MessageDialog(forTask.Result.Summary);
       Task msgTask = message.DisplayAsync();
       msgTask.ContinueWith(___ => {
          weather.Dispose();
          location.Dispose();
       });
    }, uiScheduler);
  });
}

This deep nesting is not the only peril of explicit continuation-based programming. Consider the following synchronous loop that requires conversion to an asynchronous version:

//Synchronous version:
private Forecast[] GetForecastForAllCities(City[] cities) {
  Forecast[] forecasts = new Forecast[cities.Length];
  using (WeatherService weather = new WeatherService()) {
    for (int i = 0; i < cities.Length; ++i) {
    forecasts[i] = weather.GetForecast(cities[i]);
    }
  }
  return forecasts;
}
//Asynchronous version:
private Task < Forecast[] > GetForecastsForAllCitiesAsync(City[] cities) {
  if (cities.Length == 0) {
    return Task.Run(() = > new Forecast[0]);
  }
  WeatherService weather = new WeatherService();
  Forecast[] forecasts = new Forecast[cities.Length];
  return GetForecastHelper(weather, 0, cities, forecasts).ContinueWith(_ => forecasts);
}
private Task GetForecastHelper( WeatherService weather, int i, City[] cities, Forecast[] forecasts) {
  if (i >= cities.Length) return Task.Run(() => { });
  Task < Forecast > forecast = weather.GetForecastAsync(cities[i]);
  forecast.ContinueWith(task => {
    forecasts[i] = task.Result;
    GetForecastHelper(weather, i + 1, cities, forecasts);
  });
  return forecast;
}

Converting this loop requires completely rewriting the original method and scheduling a continuation that essentially executes the next iteration in a fairly unintuitive and recursive manner. This is something the C# 5 designers have chosen to address on the language level by introducing two new keywords, async and await.

An async method must be marked with the async keyword and may return void, Task, or Task < T>. Within an async method, the await operator can be used to express a continuation without using the ContinueWith API. Consider the following example:

private async void updateButton_Clicked(. . .) {
  using (LocationService location = new LocationService()) {
    Task < Location > locTask = location.GetCurrentLocationAsync();
    Location loc = await locTask;
    cityTextBox.Text = loc.City.Name;
  }
}

In this example, the await locTask expression provides a continuation to the task returned by GetCurrentLocationAsync. The continuation’s body is the rest of the method (starting from the assignment to the loc variable), and the await expression evaluates to what the task returns, in this case—a Location object. Moreover, the continuation is implicitly scheduled on the UI thread, which is something we had to explicitly take care of earlier using the TaskScheduler API.

The C# compiler takes care of all the relevant syntactic features associated with the method’s body. For example, in the method we just wrote, there is a try. . .finally block hidden behind the using statement. The compiler rewrites the continuation such that the Dispose method on the location variable is invoked regardless of whether the task completed successfully or an exception occurred.

This smart rewriting allows almost trivial conversion of synchronous API calls to their asynchronous counterparts. The compiler supports exception handling, complex loops, recursive method invocation—language constructs that are hard to combine with the explicit continuation-passing APIs. For example, here is the asynchronous version of the forecast-retrieval loop that caused us trouble earlier:

private async Task < Forecast[] > GetForecastForAllCitiesAsync(City[] cities) {
  Forecast[] forecasts = new Forecast[cities.Length];
  using (WeatherService weather = new WeatherService()) {
    for (int i = 0; i < cities.Length; ++i) {
    forecasts[i] = await weather.GetForecastAsync(cities[i]);
    }
  }
  return forecasts;
}

Note that the changes are minimal, and the compiler handles the details of taking the forecasts variable (of type Forecast[]) our method returns and creating the Task < Forecast[] > scaffold around it.

With only two simple language features (whose implementation is everything but simple!), C# 5 dramatically decreases the barrier of entry for asynchronous programming, and makes it easier to work with APIs that return and manipulate tasks. Furthermore, the language implementation of the await operator is not wed to the Task Parallel Library; native WinRT APIs in Windows 8 return IAsyncOperation < T > and not Task instances (which are a managed concept), but can still be awaited, as in the following example, which uses a real WinRT API:

using Windows.Devices.Geolocation;
. . .
private async void updateButton_Clicked(. . .) {
  Geolocator locator = new Geolocator();
  Geoposition position = await locator.GetGeopositionAsync();
  statusTextBox.Text = position.CivicAddress.ToString();
}

Advanced Patterns in the TPL

So far in this chapter, we have considered fairly simple examples of algorithms that were subjected to parallelization. In this section, we will briefly inspect a few advanced tricks that you may find useful when dealing with real-world problems; in several cases we may be able to extract a performance gain from very surprising places.

The first optimization to consider when parallelizing loops with shared state is aggregation (sometimes called reduction). When using shared state in a parallel loop, scalability is often lost because of synchronization on the shared state access; the more CPU cores are added to the mix, the smaller the gains because of the synchronization (this phenomenon is a direct corollary of Amdahl’s Law, and is often called The Law of Diminishing Returns). A big performance boost is often available from aggregating local state within each thread or task that executes the parallel loop, and combining the local states to obtain the eventual result at the end of the loop’s execution. TPL APIs that deal with loop execution come equipped with overloads to handle this kind of local aggregation.

For example, consider the prime number computation we implemented earlier. One of the primary hindrances to scalability was the need to insert newly discovered prime numbers into a shared list, which required synchronization. Instead, we can use a local list in each thread, and aggregate the lists together when the loop completes:

List < int > primes = new List < int > ();
Parallel.For(3, 200000,
  () => new List < int > (), //initialize the local copy
  (i, pls, localPrimes) => { //single computation step, returns new local state
    if (IsPrime(i)) {
    localPrimes.Add(i); //no synchronization necessary, thread-local state
    }
    return localPrimes;
  },
  localPrimes => { //combine the local lists to the global one
    lock(primes) { //synchronization is required
    primes.AddRange(localPrimes);
    }
  }
);

In the example above, the number of locks taken is significantly smaller than earlier—we only need to take a lock once per thread that executes the parallel loop, instead of having to take it per each prime number we discovered. We did introduce an additional cost of combining the lists together, but this cost is negligible compared to the scalability gained by local aggregation.

Another source of optimization is loop iterations that are too small to be parallelized effectively. Even though the data parallelism APIs chunk multiple iterations together, there may be loop bodies that are so quick to complete that they are dominated by the delegate invocation required to call the loop body for each iteration. In this case, the Partitioner API can be used to extract manually chunks of iterations, minimizing the number of delegate invocations:

Parallel.For(Partitioner.Create(3, 200000), range => { //range is a Tuple < int,int>
  for (int i = range.Item1; i < range.Item2; ++i) . . . //loop body with no delegate invocation
});

For more information on custom partitioning, which is as well an important optimization available to data-parallel programs, consult the MSDN article “Custom Partitioners for PLINQ and TPL”, at http://msdn.microsoft.com/en-us/library/dd997411.aspx.

Finally, there are applications which can benefit from custom task schedulers. Some examples include scheduling work on the UI thread (something we have already done using TaskScheduler.Current to queue continuations to the UI thread), prioritizing tasks by scheduling them to a higher-priority scheduler, and affinitizing tasks to a particular CPU by scheduling them to a scheduler that uses threads with a specific CPU affinity. The TaskScheduler class can be extended to create custom task schedulers. For an example of a custom task scheduler, consult the MSDN article “How to: Create a Task Scheduler That Limits the Degree of Concurrency”, at http://msdn.microsoft.com/en-us/library/ee789351.aspx.

Lock-Free Code

One approach to synchronization places the burden on the operating system. After all, the operating system provides the facilities for creating and managing threads, and assumes full responsibility for scheduling their execution. It is then natural to expect from it to provide a set of synchronization primitives. Although we will discuss Windows synchronization mechanisms shortly, this approach begs the question of how the operating system implements these synchronization mechanisms. Surely Windows itself is in need of synchronizing access to its internal data structures—even the data structures representing other synchronization mechanisms—and it cannot implement synchronization mechanisms by deferring to them recursively. It also turns out that Windows synchronization mechanisms often require a system call (user-mode to kernel-mode transition) and thread context switch to ensure synchronization, which is relatively expensive if the operations that require synchronization are very cheap (such as incrementing a number or inserting an item into a linked list).

All the processor families on which Windows can run implement a hardware synchronization primitive called Compare-And-Swap (CAS). CAS has the following semantics (in pseudo-code), and executes atomically:

WORD CAS(WORD* location, WORD value, WORD comparand) {
  WORD old = *location;
  if (old == comparand) {
    *location = value;
  }
  return old;
}

Simply put, CAS compares a memory location with a provided value. If the memory location contains the provided value, it is replaced by another value; otherwise, it is unchanged. In any case, the content of the memory location prior to the operation is returned.

For example, on Intel x86 processors, the LOCK CMPXCHG instruction implements this primitive. Translating a CAS(&a,b,c) call to LOCK CMPXCHG is a simple mechanical process, which is why we will be content with using CAS throughout the rest of this section. In the .NET Framework, CAS is implemented using a set of overloads called Interlocked.CompareExchange.

//C# code:
int n = . . .;
if (Interlocked.CompareExchange(ref n, 1, 0) == 0) { //attempt to replace 0 with 1
  //. . .do something
}
//x86 assembly instructions:
mov eax, 0 ;the comparand
mov edx, 1 ;the new value
lock cmpxchg dword ptr [ebp-64], edx ;assume that n is in [ebp-64]
test eax, eax ;if eax = 0, the replace took place
jnz not_taken
;. . .do something
not_taken:

A single CAS operation is often not enough to ensure any useful synchronization, unless the desirable semantics are to perform a one-time check-and-replace operation. However, when combined with a looping construct, CAS can be used for a non-negligible variety of synchronization tasks. First, we consider a simple example of in-place multiplication. We want to execute the operation x * = y atomically, where x is a shared memory location that may be written to simultaneously by other threads, and y is a constant value that is not modified by other threads. The following CAS-based C# method performs this task:

public static void InterlockedMultiplyInPlace(ref int x, int y) {
  int temp, mult;
  do {
    temp = x;
    mult = temp * y;
  } while(Interlocked.CompareExchange(ref x, mult, temp) ! = temp);
}

Each loop iteration begins by reading the value of x to a temporary stack variable, which cannot be modified by another thread. Next, we find the multiplication result, ready to be placed into x. Finally, the loop terminates if and only if CompareExchange reports that it successfully replaced the value of x with the multiplication result, granted that the original value was not modified. We cannot guarantee that the loop will terminate in a bounded number of iterations; however, it is highly unlikely that—even under pressure from other processors—a single processor will be skipped more than a few times when trying to replace x with its new value. Nonetheless, the loop must be prepared to face this case (and try again). Consider the following execution history with x = 3, y = 5 on two processors:

Processor #1    Processor #2
temp = x; (3)
    temp = x; (3)
mult = temp * y; (15)
    mult = temp * y; (15)
    CAS(ref x, mult, temp) == 3 (== temp)
CAS(ref x, mult, temp) == 15 (! = temp)

Even this extremely simple example is very easy to get wrong. For example, the following loop may cause lost updates:

public static void InterlockedMultiplyInPlace(ref int x, int y) {
  int temp, mult;
  do {
    temp = x;
    mult = x * y;
  } while(Interlocked.CompareExchange(ref x, mult, temp) ! = temp);
}

Why? Reading the value of x twice in rapid succession does not guarantee that we see the same value! The following execution history demonstrates how an incorrect result can be produced, with x = 3, y = 5 on two processors—at the end of the execution x = 60!

Processor #1    Processor #2
temp = x; (3)
    x = 12;
mult = x * y; (60!)
    x = 3;
CAS(ref x, mult, temp) == 3 (== temp)

We can generalize this result to any algorithm that needs to read only a single mutating memory location and replace it with a new value, no matter how complex. The most general version would be the following:

public static void DoWithCAS < T > (ref T location, Func < T,T > generator) where T : class {
  T temp, replace;
  do {
    temp = location;
    replace = generator(temp);
  } while (Interlocked.CompareExchange(ref location, replace, temp) ! = temp);
}

Expressing the multiplication method in terms of this general version is very easy:

public static void InterlockedMultiplyInPlace(ref int x, int y) {
  DoWithCAS(ref x, t => t * y);
}

Specifically, there is a simple synchronization mechanism called spinlock that can be implemented using CAS. The idea here is as follows: to acquire a lock is to make sure that any other thread that attempts to acquire it will fail and try again. A spinlock, then, is a lock that allows a single thread to acquire it and all other threads to spin (“waste” CPU cycles) while trying to acquire it:

public class SpinLock {
  private volatile int locked;
  public void Acquire() {
    while (Interlocked.CompareExchange(ref locked, 1, 0) ! = 0);
  }
  public void Release() {
    locked = 0;
  }
}

Processor #1    Processor #2
while (f == 0);    x = 42;
print(x);    f = 1;

In our spinlock implementation, 0 represents a free lock and 1 represents a lock that is taken. Our implementation attempts to replace its internal value with 1, provided that its current value is 0—i.e., acquire the lock, provided that it is not currently acquired. Because there is no guarantee that the owning thread will release the lock quickly, using a spinlock means that you may devote a set of threads to spinning around, wasting CPU cycles, waiting for a lock to become available. This makes spinlocks inapplicable for protecting operations such as database access, writing out a large file to disk, sending a packet over the network, and similar long-running operations. However, spinlocks are very useful when the guarded code section is very quick—modifying a bunch of fields on an object, incrementing several variables in a row, or inserting an item into a simple collection.

Indeed, the Windows kernel itself uses spinlocks extensively to implement internal synchronization. Kernel data structures such as the scheduler database, file system cache block list, memory page frame number database and others are protected by one or more spinlocks. Moreover, the Windows kernel introduces additional optimizations to the simple spinlock implementation described above, which suffers from two problems:

1. The spinlock is not fair, in terms of FIFO semantics. A processor may be the last of ten processors to call the Acquire method and spin inside it, but may be the first to actually acquire it after it has been released by its owner.
2. When the spinlock owner releases the spinlock, it invalidates the cache of all the processors currently spinning in the Acquire method, although only one processor will actually acquire it. (We will revisit cache invalidation later in this chapter.)

The Windows kernel uses in-stack queued spinlocks; an in-stack queued spinlock maintains a queue of processors waiting for a lock, and every processor waiting for the lock spins around a separate memory location, which is not in the cache of other processors. When the spinlock’s owner releases the lock, it finds the first processor in the queue and signals the bit on which this particular processor is waiting. This guarantees FIFO semantics and prevents cache invalidations on all processors but the one that successfully acquires the lock.

Armed with the CAS synchronization primitive, we now reach an incredible feat of engineering—a lock-free stack. In Chapter 5 we have considered some concurrent collections, and will not repeat this discussion, but the implementation of ConcurrentStack < T > remained somewhat of a mystery. Almost magically, ConcurrentStack < T > allows multiple threads to push and pop items from it, but never requires a blocking synchronization mechanism (that we consider next) to do so.

We shall implement a lock-free stack by using a singly linked list. The stack’s top element is the head of the list; pushing an item onto the stack or popping an item from the stack means replacing the head of the list. To do this in a synchronized fashion, we rely on the CAS primitive; in fact, we can use the DoWithCAS < T> helper introduced previously:

public class LockFreeStack < T > {
  private class Node {
    public T Data;
    public Node Next;
  }
  private Node head;
  public void Push(T element) {
    Node node = new Node { Data = element };
    DoWithCAS(ref head, h => {
    node.Next = h;
    return node;
    });
  }
  public bool TryPop(out T element) {
    //DoWithCAS does not work here because we need early termination semantics
    Node node;
    do {
    node = head;
    if (node == null) {
    element = default(T);
    return false; //bail out – nothing to return
    }
    } while (Interlocked.CompareExchange(ref head, node.Next, node) ! = node);
    element = node.Data;
    return true;
  }
}

The Push method attempts to replace the list head with a new node, whose Next pointer points to the current list head. Similarly, the TryPop method attempts to replace the list head with the node to which the current head’s Next pointer points, as illustrated in Figure 6-8.

You may be tempted to think that every data structure in the world can be implemented using CAS and similar lock-free primitives. Indeed, there are some additional examples of lock-free collections in wide use today:

• Lock-free doubly linked list
• Lock-free queue (with a head and tail)
• Lock-free simple priority queue

However, there is a great variety of collections that cannot be easily implemented using lock-free code, and still rely on blocking synchronization mechanisms. Furthermore, there is a considerable amount of code that requires synchronization but cannot use CAS because it takes too long to execute. We now turn to discuss “real” synchronization mechanisms, which involve blocking, implemented by the operating system.

Windows Synchronization Mechanisms

Windows offers numerous synchronization mechanisms to user-mode programs, such as events, semaphores, mutexes, and condition variables. Our programs can access these synchronization mechanisms through handles and Win32 API calls, which issue the corresponding system calls on our behalf. The .NET Framework wraps most Windows synchronization mechanisms in thin object-oriented packages, such as ManualResetEvent, Mutex, Semaphore, and others. On top of the existing synchronization mechanisms, .NET offers several new ones, such as ReaderWriterLockSlim and Monitor. We will not examine exhaustively every synchronization mechanism in minute detail, which is a task best left to API documentation; it is important, however, to understand their general performance characteristics.

The Windows kernel implements the synchronization mechanisms we are now discussing by blocking a thread that attempts to acquire the lock when the lock is not available. Blocking a thread involves removing it from the CPU, marking it as waiting, and scheduling another thread for execution. This operation involves a system call, which is a user-mode to kernel-mode transition, a context switch between two threads, and a small set of data structure updates (see Figure 6-9) performed in the kernel to mark the thread as waiting and associate it with the synchronization mechanism for which it’s waiting.

Overall, there are potentially thousands of CPU cycles spent to block a thread, and a similar number of cycles is required to unblock it when the synchronization mechanism becomes available. It is clear, then, that if a kernel synchronization mechanism is used to protect a long-running operation, such as writing a large buffer to a file or performing a network round-trip, this overhead is negligible, but if a kernel synchronization mechanism is used to protect an operation like ++i, this overhead introduces an inexcusable slowdown.

The synchronization mechanisms Windows and .NET make available to applications differ primarily in terms of their acquire and release semantics, also known as their signal state. When a synchronization mechanism becomes signaled, it wakes up a thread (or a group of threads) waiting for it to become available. Below are the signal state semantics for some of the synchronization mechanisms currently accessible to .NET applications:

Other than the signal state semantics, some synchronization mechanisms differ also in terms of their internal implementation. For example, the Win32 critical section and the CLR Monitor implement an optimization for locks that are currently available. With that optimization, a thread attempting to acquire an available lock can grab it directly without performing a system call. On a different front, the reader-writer lock family of synchronization mechanisms distinguishes between readers and writers accessing a certain object, which permits better scalability when the data is most often accessed for reading.

Choosing the appropriate synchronization mechanism from the list of what Windows and .NET have to offer is often difficult, and there are times when a custom synchronization mechanism may offer better performance characteristics or more convenient semantics than the existing ones. We will not consider synchronization mechanisms any further; it is your responsibility when programming concurrent applications to choose responsibly between lock-free synchronization primitives and blocking synchronization mechanisms, and to determine the best combination of synchronization mechanisms to use.

Cache Considerations

We have previously paid a visit to the subject of processor caches in the context of collection implementation and memory density. In parallel programs it is similarly important to regard cache size and hit rates on a single processor, but it is even more important to consider how the caches of multiple processors interact. We will now consider a single representative example, which demonstrates the important of cache-oriented optimization, and emphasizes the value of good tools when it concerns performance optimization in general.

First, examine the following sequential method. It performs the rudimentary task of summing all the elements in a two-dimensional array of integers and returns the result.

public static int MatrixSumSequential(int[,] matrix) {
  int sum = 0;
  int rows = matrix.GetUpperBound(0);
  int cols = matrix.GetUpperBound(1);
  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j) {
    sum + = matrix[i,j];
    }
  }
  return sum;
}

We have in our arsenal a large set of tools for parallelizing programs of this sort. However, imagine for a moment that we don’t have the TPL at our disposal, and choose to work directly with threads instead. The following attempt at parallelization may appear sufficiently reasonable to harvest the fruits of multi-core execution, and even implements a crude aggregation to avoid synchronization on the shared sum variable:

public static int MatrixSumParallel(int[,] matrix) {
  int sum = 0;
  int rows = matrix.GetUpperBound(0);
  int cols = matrix.GetUpperBound(1);
  const int THREADS = 4;
  int chunk = rows/THREADS; //should divide evenly
  int[] localSums = new int[THREADS];
  Thread[] threads = new Thread[THREADS];
  for (int i = 0; i < THREADS; ++i) {
    int start = chunk*i;
    int end = chunk*(i + 1);
    int threadNum = i; //prevent the compiler from hoisting the variable in the lambda capture
    threads[i] = new Thread(() => {
    for (int row = start; row < end; ++row) {
    for (int col = 0; col < cols; ++col) {
    localSums[threadNum] + = matrix[row,col];
    }
    }
    });
    threads[i].Start();
  }
  foreach (Thread thread in threads) {
    thread.Join();
  }
  sum = localSums.Sum();
  return sum;
}

Executing each of the two methods 25 times on an Intel i7 processor produced the following results for a 2,000 × 2,000 matrix of integers: the sequential method completed within 325ms on average, whereas the parallelized method took a whopping 935ms on average, thrice as slow as the sequential version!

This is clearly unacceptable, but why? This is not another example of too fine-grained parallelism, because the number of threads is only 4. If you accept the premise that the problem is somehow cache-related (because this example appears in the “Cache Considerations” section), it would make sense to measure the number of cache misses introduced by the two methods. The Visual Studio profiler (when sampling at each 2,000 cache misses) reported 963 exclusive samples in the parallel version and only 659 exclusive samples in the sequential version; the vast majority of samples were on the inner loop line that reads from the matrix.

Again, why? Why would the line of code writing to the localSums array introduce so many more cache misses than the line writing to the sum local variable? The simple answer is that the writes to the shared array invalidate cache lines at other processors, causing every + = operation on the array to be a cache miss.

As you recall from Chapter 5, processor caches are organized in cache lines, and adjacent memory locations share the same cache line. When one processor writes to a memory location that is in the cache of another processor, the hardware causes a cache invalidation that marks the cache line in the other processor’s cache as invalid. Accessing an invalid cache line causes a cache miss. In our example above, it is very likely that the entire localSums array fits in a single cache line, and resides simultaneously in the caches of all four processors on which the application’s threads are executing. Every write performed to any element of the array on any of the processors invalidates the cache line on all other processors, causing a constant ping-pong of cache invalidations (see Figure 6-10).

To make sure that the problem is completely related to cache invalidations, it is possible to make the array strides sufficiently larger such that cache invalidation does not occur, or to replace the direct writes to the array with writes to a local variable in each thread that is eventually flushed to the array when the thread completes. Either of these optimizations restores sanity to the world, and makes the parallel version faster than the sequential one on a sufficiently large number of cores.

Cache invalidation (or cache collision) is a nasty problem that is exceptionally difficult to detect in a real application, even when aided by powerful profilers. Taking it into consideration upfront when designing CPU-bound algorithms will save you a lot of time and aggravation later.

Introduction to C++ AMP

At its essence, a GPU is a processor like any other, with a specific instruction set, numerous cores, and a memory access protocol. However, there are significant differences between modern GPUs and CPUs, and understanding them is central for writing efficient GPU-based programs:

• There is only a small subset of instructions available to modern CPUs that are available on the GPU. This implies some limitations: there are no function calls, data types are limited, library functions are missing, and others. Other operations, such as branching, may introduce a performance cost unparalleled to that on the CPU. Clearly, this makes porting massive amounts of code from the CPU to the GPU a considerable effort.
• There is a considerably larger number of cores on a mid-range graphics card than on a mid-range CPU socket. There will be work units that are too small or cannot be broken into sufficiently many pieces to benefit properly from parallelization on the GPU.
• There is scarce support for synchronization between GPU cores executing a task, and no support for synchronization between GPU cores executing different tasks. This requires the synchronization and orchestration of GPU work to be performed on the CPU.

C++ AMP is a framework that ships with Visual Studio 2012 and provides C++ developers with simple means to run computations on the GPU, and requires only a DirectX 11 driver to run. Microsoft has released C++ AMP as an open specification (available online at the time of writing at http://blogs.msdn.com/b/nativeconcurrency/archive/2012/02/03/c-amp-open-spec-published.aspx), which any compiler vendor can implement. In C++ AMP, code can execute on accelerators, which represent computational devices. C++ AMP discovers dynamically all the accelerators with a DirectX 11 driver. Out of the box, C++ AMP also ships with a reference accelerator that performs software emulation, and a CPU-based accelerator, WARP, which is a reasonable fallback on machines without a GPU or with a GPU that doesn’t have a DirectX 11 driver, and uses multi-core and SIMD instructions.

With no further ado, let us consider an algorithm that can be easily parallelized on the GPU. The algorithm below takes two vectors of the same length and calculates a pointwise result. There’s hardly anything that could be more straightforward:

void VectorAddExpPointwise(float* first, float* second, float* result, int length) {
  for (int i = 0; i < length; ++i) {
    result[i] = first[i] + exp(second[i]);
  }
}

Parallelizing this algorithm on the CPU requires splitting the iteration range into several chunks and creating a thread to handle each part. Indeed, we have devoted quite some time to doing just that with our primality testing example—we have seen how to parallelize it by manually creating threads, by issuing work items to the thread pool, and by using the Parallel.For automatic parallelization capabilities. Also, recall that when parallelizing similar algorithms on the CPU we have taken great care to avoid work items that were too granular (e.g., a work item per iteration wouldn’t do).

On the GPU, no such caution is necessary. The GPU is equipped with many cores that can execute threads very rapidly, and the cost of a context switch is significantly lower than on the CPU. Below is the code required using C++ AMP’s parallel_foreach API:

#include < amp.h>
#include < amp_math.h>
using namespace concurrency;
void VectorAddExpPointwise(float* first, float* second, float* result, int length) {
  array_view < const float,1 > avFirst (length, first);
  array_view < const float,1 > avSecond(length, second);
  array_view < float,1> avResult(length, result);
  avResult.discard_data();
  parallel_for_each(avResult.extent, [=](index < 1 > i) restrict(amp) {
    avResult[i] = avFirst[i] + fast_math::exp(avSecond[i]);
  });
  avResult.synchronize();
}

We now examine each part of the code individually. First, the general shape of the main loop has been maintained, although the original for loop has been replaced with an API call to parallel_foreach. Indeed, the principle of converting a loop to an API call is not new—we have seen the same with TPL’s Parallel.For and Parallel.ForEach APIs.

Next, the original data passed to the method (the first, second, and result parameters) has been wrapped in array_view instances. The array_view class wraps data that must be moved to an accelerator (GPU). Its template parameters are the type of the data and its dimensionality. If we want the GPU to execute instructions that access data that was originally on the CPU, some entity must take care of copying the data to the GPU, because most of today’s GPUs are discrete devices with their own memory. This is the task of the array_view instances—they make sure data is copied on demand, and only when it is required.

When the work on the GPU is done, the data is copied back to its original location. By creating array_view instances with a const template type argument, we make sure that first and second are copied only to the GPU but don’t have to be copied back from the GPU. Similarly, by calling the discard_data method, we make sure that result is not copied from the CPU to the GPU, but only from the GPU to the CPU when there is a result worth copying.

The parallel_foreach API takes an extent, which is the shape of the data we are working on, and a function to execute for each of the elements in the extent. We used a lambda function in the code above, which is a welcome addition to C++ as of the 2011 ISO C++ standard (C++11). The restrict(amp) keyword instructs the compiler to verify that the body of the function can execute on the GPU, forbidding most of the C++ syntax—syntax that cannot be compiled to GPU instructions.

The lambda function’s parameter is an index < 1 > object, which represents a one-dimensional index. This must match the extent we used—should we declare a two-dimensional extent (such as the data shape of a matrix), the index would have to be two-dimensional as well. We will see an example of this shortly.

Finally, the synchronize method call at the end of the method makes sure that by the time VectorAdd returns, the changes made on the CPU to the avResult array_view are copied back into its original container, the result array.

This concludes our first foray into the world of C++ AMP, and we are ready for a closer examination of what is going on—as well as a better example, which will yield benefits from GPU parallelization. Vector addition is not the most exciting of algorithms, and does not make a good candidate for offloading to the GPU because the memory transfer outweights the computation’s parallelization. In the following subsection we look at two examples that should be more interesting.

Matrix Multiplication

The first “real-world” example we shall consider is matrix multiplication. We will optimize the naïve cubic time algorithm for matrix multiplication and not Strassen’s algorithm, which runs in sub-cubic time. Given two matrices of suitable dimensions, A that is m-by-w and B that is w-by-n, the following sequential program produces their product, a matrix C that is m-by-n:

void MatrixMultiply(int* A, int m, int w, int* B, int n, int* C) {
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
    int sum = 0;
    for (int k = 0; k < w; ++k) {
    sum + = A[i*w + k] * B[k*w + j];
    }
    C[i*n + j] = sum;
    }
  }
}

There are several sources for parallelism here, and if you were willing to parallelize this code on the CPU, you might be right in suggesting that we parallelize the outer loop and be done with it. On the GPU, however, there are sufficiently many cores that if we parallelize only the outer loop we might not create enough work for all the cores. Therefore, it makes sense to parallelize the two outer loops, still leaving a meaty algorithm for the inner loop:

void MatrixMultiply(int* A, int m, int w, int* B, int n, int* C) {
  array_view < const int,2 > avA(m, w, A);
  array_view < const int,2 > avB(w, n, B);
  array_view < int,2> avC(m, n, C);
  avC.discard_data();
  parallel_for_each(avC.extent, [=](index < 2 > idx) restrict(amp) {
    int sum = 0;
    for (int k = 0; k < w; ++k) {
    sum + = avA(idx[0]*w, k) * avB(k*w, idx[1]);
    }
    avC[idx] = sum;
  });
}

Everything is still very similar to sequential multiplication and the vector addition example we have seen earlier—with the exception of the index, which is two-dimensional, and accessed by the inner loop using the [] operator. How does this version fare compared to the sequential CPU alternative? To multiply two 1024 × 1024 matrices (of integers), the CPU version required 7350 ms on average, whereas the GPU version—hold tight—took 50 ms on average, a 147-fold improvement!

N-Body Simulation

The examples we have seen so far had very trivial code in the inner loop that was scheduled on the GPU. Clearly, this must not always be the case. One of the examples on the Native Concurrency team blog we referred to demonstrates an N-body simulation, which simulates the interactions between particles where the force of gravity is applied. The simulation consists of an infinite number of steps; in each step, it has to determine the updated acceleration vector of each particle and then determine its new location. The parallelizable component here is the vector of particles—with sufficiently many particles (a few thousands or more) there is ample work for all GPU cores to do at once.

The kernel that determines the result of an interaction between two bodies is the following code, which can be ported very easily to the GPU:

//float4 here is a four-component vector with pointwise operations
void bodybody_interaction(
  float4& acceleration, const float4 p1, const float4 p2) restrict(amp) {
  float4 dist = p2 – p1;
  float absDist = dist.x*dist.x + dist.y*dist.y + dist.z*dist.z; //w is unused here
  float invDist = 1.0f / sqrt(absDist);
  float invDistCube = invDist*invDist*invDist;
  acceleration + = dist*PARTICLE_MASS*invDistCube;
}

Each simulation step takes an array of particle positions and velocities, and generates a new array of particle positions and velocities based on the results of the simulation:

struct particle {
  float4 position, velocity;
  //ctor, copy ctor, and operator = with restrict(amp) omitted for brevity
};
void simulation_step(array < particle,1 > & previous, array < particle,1 > & next, int bodies) {
  extent < 1 > ext(bodies);
  parallel_for_each(ext, [&](index < 1 > idx) restrict(amp) {
    particle p = previous[idx];
    float4 acceleration(0, 0, 0, 0);
    for (int body = 0; body < bodies; ++body) {
    bodybody_interaction(acceleration, p.position, previous[body].position);
    }
    p.velocity + = acceleration*DELTA_TIME;
    p.position + = p.velocity*DELTA_TIME;
    next[idx] = p;
  });
}

With an appropriate GUI, this simulation is very entertaining. The full sample provided by the C++ AMP team is available on the Native Concurrency blog. On the author’s system, an Intel i7 processor with an ATI Radeon HD 5800 graphics card, a simulation with 10,000 particles yielded ∼ 2.5 frames per second (steps) from the sequential CPU version and 160 frames per second (steps) from the optimized GPU version (see Figure 6-11), an incredible improvement.

Tiles and Shared Memory

Before we conclude this section, there is a very important optimization surfaced by C++ AMP that can improve even more the performance of our GPU code. GPUs offer a programmable data cache (often called shared memory). Values stored in it are shared across all threads in the same tile. By using tiled memory, C++ AMP programs can read data from the GPU’s main memory once into the shared tile memory, and then access it quickly from multiple threads in the same tile without refetching it from the GPU’s main memory. Accessing shared tile memory can be around 10 times faster than accessing the GPU’s main memory—in other words, you have a reason to keep reading.

To execute a tiled version of a parallel loop, the parallel_for_each method accepts a tiled_extent domain, which subdivides a multi-dimensional extent into multi-dimensional tiles, and a tiled_index lambda parameter, which specifies both the global thread ID within the extent, and the local thread ID within the tile. For example, a 16 × 16 matrix can be subdivided into 2 × 2 tiles (see Figure 6-12) and then passed into parallel_for_each:

extent < 2 > matrix(16,16);
tiled_extent < 2,2 > tiledMatrix = matrix.tile < 2,2 > ();

parallel_for_each(tiledMatrix, [=](tiled_index < 2,2 > idx) restrict(amp) { . . . });

Within the GPU kernel, idx.global can be used in place of the standard index < 2 > we have seen earlier when performing operations on matrices. However, clever use of the local tile memory and local tile indices can reap significant performance benefits. To declare tile-specific memory that is shared across all threads in the same tile, the tile_static storage specifier can be applied to local variables inside the kernel. It is common to declare a shared memory location and have each thread in the tile initialize a small part of it:

parallel_for_each(tiledMatrix, [=](tiled_index < 2,2 > idx) restrict(amp) {
  tile_static int local[2][2]; //32 bytes shared between all threads in the tile
  local[idx.local[0]][idx.local[1]] = 42; //assign to this thread's location in the array
});

Clearly, procuring any benefits from memory shared with other threads in the same tile is only possible if all the threads can synchronize their access to the shared memory; i.e., they shouldn’t attempt to access shared memory locations before their tile neighboring threads have initialized them. tile_barrier objects synchronize the execution of all the threads in a tile—they can proceed executing after calling tile_barrier.wait only after all the threads in the tile have called tile_barrier.wait as well (this is similar to the TPL’s Barrier class). For example:

parallel_for_each(tiledMatrix, [](tiled_index < 2,2 > idx) restrict(amp) {
  tile_static int local[2][2]; //32 bytes shared between all threads in the tile
  local[idx.local[0]][idx.local[1]] = 42; //assign to this thread's location in the array
  idx.barrier.wait(); //idx.barrier is a tile_barrier instance
  //Now this thread can access "local" at other threads' indices!
});

It is now time to apply all this knowledge to a concrete example. We will revisit the matrix multiplication algorithm previously implemented without tiling, and introduce a tiling-based optimization into it. Let’s assume that the matrix dimensions are divisible by 256—this allows us to work with 16 × 16 thread tiles. Matrix multiplication contains inherent blocking, which can be used to our advantage (in fact, one of the most common optimizations of extremely large matrix multiplication on the CPU is by using blocking to obtain better cache behavior). The primary observation boils down to the following. To find C _i,j (the element at row i and column j in the result matrix), we have to find the scalar product between A _i,* (the entire i-th row of the first matrix) and B _*,j (the entire j-th row of the second matrix). However, this is equivalent to finding the scalar products of partial rows and partial columns and summing the results together. We can use this to translate our matrix multiplication algorithm to the tiled version:

void MatrixMultiply(int* A, int m, int w, int* B, int n, int* C) {
  array_view < const int,2 > avA(m, w, A);
  array_view < const int,2 > avB(w, n, B);
  array_view < int,2> avC(m, n, C);
  avC.discard_data();
  parallel_for_each(avC.extent.tile < 16,16 > (), [=](tiled_index < 16,16 > idx) restrict(amp) {
    int sum = 0;
    int localRow = idx.local[0], localCol = idx.local[1];
    for (int k = 0; k < w; k += 16) {
    tile_static int localA[16][16], localB[16][16];
    localA[localRow][localCol] = avA(idx.global[0], localCol + k);
    localB[localRow][localCol] = avB(localRow + k, idx.global[1]);
    idx.barrier.wait();
    for (int t = 0; t < 16; ++t) {
    sum + = localA[localRow][t]*localB[t][localCol];
    }
    idx.barrier.wait(); //to avoid having the next iteration overwrite the shared memory
    }
    avC[idx.global] = sum;
  });
}

The essence of the tiled optimization is that each thread in the tile (there are 256 threads, the tile is 16 × 16) initializes its own element in the 16 × 16 local copies of sub-blocks from the A and B input matrices (see Figure 6-13). Each thread in the tile needs only one row and one column of these sub-blocks, but all the threads together will access every row 16 times and every column 16 times, reducing significantly the number of main memory accesses.

In this case, tiling is a worthwhile optimization. The tiled version of matrix multiplication executes significantly faster than the simple one, and takes 17 ms on average to complete (using the same 1024 × 1024 matrices). This concludes a 430-fold speed increase compared to the CPU version!

Before we part with C++ AMP, it’s worthwhile to mention the development tools (Visual Studio) available to C++ AMP developers. Visual Studio 2012 features a GPU debugger, which you can use to place breakpoints in GPU kernels, inspect simulated call stacks, read and modify local variables (some accelerators support GPU debugging; with others, Visual Studio uses a software emulator), and a profiler that can be used to gauge what your application has gained from using GPU parallelization. For more information on the Visual Studio GPU debugging experience, consult the MSDN article “Walkthrough: Debugging a C++ AMP Application”, at http://msdn.microsoft.com/en-us/library/hh368280(v=VS.110).aspx.

[Kernel]
public static void MultiplyAddGpu(double[] a, double[] b, double[] c) {
 int ThreadId = BlockDimension.X * BlockIndex.X + ThreadIndex.X;
 int TotalThreads = BlockDimension.X * GridDimension.X;
 for (int ElementIdx = ThreadId; ElementIdx < a.Length; ElementIdx += TotalThreads) {
 c[ElementIdx] = a[ElementIdx] * b[ElementIdx];
}
}

This section hardly scratches the surface of the possibilities offered by C++ AMP. We have only taken a look at some of the APIs and parallelized an algorithm or two. If you are interested in more details about C++ AMP, we strongly recommend Kate Gregory’s and Ade Miller’s book, “C++ AMP: Accelerated Massive Parallelism with Microsoft Visual C++” (Microsoft Press, 2012).