The Parallel Programming Earthquake
by
Herbert Schildt
There is something of an earthquake occurring in the programming world that will ultimately be felt by nearly all programmers. The effects of this "quake" will cause us to restructure our code, streamline certain operations, and change the way that we think about several commonplace programming tasks. What is this quake? It is the rising importance of parallelism in the modern computing environment.
As most readers will know, multicore processors are becoming commonplace. In such an environment it is possible for two or more tasks to execute concurrently (i.e., simultaneously), rather than simply sharing a single CPU via timeslicing. Until recently, it has not been easy to utilize the power of a multiple processor environment. One of the problems has been the difficulty of building generalized solutions that automatically scale to take advantage of available processors. In other words, it has been challenging to create programs that can adapt their degree of parallelism based on the number of processors in the execution environment. Fortunately, this situation is changing.
At the time of this writing, one major programming environment, the .NET Framework 4.0, has already added features, such as the Task Parallel Library and PLINQ, that greatly simplify parallel programming. Therefore, through the use of C# 4.0 (or other .NET 4.0 compatible languages) you can create scalable, parallel solutions today for .NET applications.
Another major programming environment, Java, is also expected to add parallel programming support in the near future. It is anticipated that the next Java release, which will be JDK 7, will include the fork-join framework. At the time of this writing, the pre-release version of the fork-join framework is similar in concept to .NET's TPL, but uses a somewhat different approach. (It is important to understand that until JDK 7 is released, its feature set is subject to change. Therefore, the fork-join framework may or may not be part of JDK 7 when it is released.)
Traditional Multithreading vs Parallelism
Before we continue, it is useful to point out the difference between traditional multithreading and parallel programming. In the past, most computers had a single CPU and multithreading was used to take advantage of idle time, such as when a program blocks for user input. Using this approach, one thread can execute when another is waiting. In other words, on a single-CPU system, multithreading is used to allow two or more tasks to share the CPU. Although this type of multithreading will always remain useful, it was not designed for situations in which two or more CPUs are available.
When multiple CPUs are present, a second type of multithreading capability is needed because it is possible to execute portions of a program simultaneously, with each part executing on its own CPU. This can be used to significantly speed up the execution of some types of operations, such as sorting, transforming, or searching a large array. In many cases, these types of operations can be broken down into smaller pieces (each acting on a portion of the array), and each piece can be run on its own CPU. As you can imagine, in some cases the gain in execution speed can be quite significant.
Parallel Support in the .NET Framework 4.0
Since parallel programming support in the .NET Framework 4.0 is available now, a brief overview of its features will help put the subject into concrete terms.
As mentioned, the .NET Framework 4.0 provides support for parallel programming through two major new features. The first is the Task Parallel Library (TPL). The TPL enhances multithreaded programming in two ways:
 | It simplifies the creation and use of multiple threads |
| It automatically makes use of multiple processors. |
Of these, the latter is the most important because it enables you to create scalable solutions that automatically utilize the processors available in the execution environment. This means that you can write your parallel code once, and it will adjust as needed at runtime. The second new .NET 4.0 parallel programming feature is PLINQ, which stands for Parallel Language INtegrated Query. PLINQ makes it easy to write parallelized queries, such as those used to access a database.
When using the TPL (or PLINQ) there are two basic ways in which you can add parallelism to a program. The first is called data parallelism. With this approach, an operation on a collection of data (such as an array) is broken into two or more concurrent threads of execution, each operating on a portion of the data simultaneously. For example, if a transformation is applied to each element in an array, then through the use of data parallelism, it is possible for two or more threads of execution to be operating on different ranges of the array concurrently. As you can imagine, such parallel actions could result in substantial increases in speed over a strictly sequential approach.
The second way to add parallelism is through the use of task parallelism. This approach executes two or more sections of code concurrently. Thus, task parallelism is the type of parallelism that has been accomplished in the past in the .NET Framework via the Thread class. The advantages that the TPL adds in this regard is ease of use and the ability to automatically scale execution to multiple processors.
The Task Parallel Library
The Task Parallel Library was added by version 4.0 of the .NET Framework. At the core of the TPL is the Task class. With the TPL, the basic unit of execution is encapsulated by Task, not Thread (which has been part of the .NET Framework from the start). Task differs from Thread in that Task is an abstraction that represents an asynchronous operation. Thread encapsulates a thread of execution. Of course, at the system level, a thread is still the basic unit of execution that can be scheduled by the operating system. However, the correspondence between a Task instance and a thread of execution is not necessarily one-to-one. Furthermore, task execution is managed by a task scheduler, which works with a thread pool. This means that several tasks might share the same thread, for example.
A second important TPL class is Parallel. It facilitates the execution of concurrent code and provides methods that streamline both task and data parallelism. Perhaps its most important members are the For( ) and ForEach( ) methods. They offer an easy-to-use way to create parallel loops, which are loops in which iterations over different regions of a data source can occur concurrently. Furthermore, such parallelization occurs automatically, based on the number of processors in the execution environment. This makes For( ) and ForEach( ) excellent choices where data parallelism is desired. Parallel also includes the Invoke( ) method, which supports the concurrent execution of two or more methods or lambda expressions. Thus, Invoke( ) supports task parallelism. Collectively, these three methods offer the advantage of providing easy ways to utilize common parallel programming techniques without the need to manage tasks or threads explicitly.
As a point of interest, although the goal of any parallel programming technique is to increase the speed or efficiency of a program, there is no guarantee that parallelizing a section of code will result in a performance boost. Improvements depend both on the execution environment, and on the actions performed. Obviously, if the execution environment has only one processor, then no parallelism will occur. For example, executing a loop via For( ) in a single processor system will not result in any performance boost. (Of course, if that same loop is executed on a different system that supports multiple processors, then the benefits of For( ) will be realized.) Perhaps more importantly, because of the overhead involved, some loops, such as those with few iterations or those that perform very simple actions, may not benefit from parallelization at all. The reason is that the overhead incurred by parallelization is greater than the time that is saved by the parallel execution. Of course, when used wisely, and when executed in a multiprocessor environment, parallel programming solutions can lead to significant increases in program speed.
PLINQ
PLINQ is the parallel version of LINQ, and it is closely related to the TPL. A primary use of PLINQ is to achieve data parallelism within a query. At the foundation of PLINQ is the ParallelEnumerable class. This is a static class that defines many extension methods that support parallel operations. Perhaps the single most convenient feature of PLINQ is how easy it is to create a parallel query. To do this, you simply call AsParallel( ) on the data source. Once this is done, the query will partition the data source and operate on each partition in parallel if possible, and if the query is likely to benefit from parallelization. (If parallelization is not possible or reasonable, the query is simply executed sequentially.) Therefore, with the addition of a single call to AsParallel( ), a sequential LINQ query is transformed into a parallel PLINQ query. Furthermore, for simple queries, this is the only step necessary.
Don't Be Left Behind
With the rise of multicore systems, parallel programming is no longer a specialized discipline, practiced by a few. It has entered the mainstream, and it is something that nearly all programmers will need to deal with in one way or another. Simply put: parallel programming has become part of the landscape. Now is the time to gain mastery over this important aspect of programming. Fortunately, features such as .NET's TPL or the anticipated fork-join framework for Java will help make the process of adding parallelism to your programs both easier and safer.