WHAT YOU WILL LEARN IN THIS CHAPTER:
The principle features of the Parallel Patterns Library
How to execute loop iterations in parallel
How to execute two or more tasks concurrently
How to manage shared resources in parallel operations
How to indicate and manage sections in your parallel code that must not be executed by multiple processors
If your PC or laptop is relatively new, in all probability it has a processor chip with two or more cores. If it doesn't, you can skip this chapter and move on to the next chapter. Each core in a multi-core processor chip is an independent processing unit, so your computer can be executing code from more than one application at any given time. However, it is not limited to that. Having multiple cores or multiple processors provides you with the possibility of overlapping computations within a single application by having each processor handling a separate piece of the calculations required in parallel. Because at least some of the calculations in your application are overlapped, your application should execute faster.
This chapter will show you how you can use multiple cores within a single application. You will also get to use what you learned about the Windows API in the previous chapter in a significant parallel computation.
Programming an application to use multiple cores or processors requires that you organize the computation differently from what you have been used to with serial processing. You must be able to divide the computation into a set of sub-tasks that can be executed independently of one another, and this is not always easy, or indeed possible. Sub-tasks that can run in parallel are usually referred to as threads.
Any interdependence between threads places serious constraints on parallel execution. Shared resources are a common limitation. Sub-tasks executing in parallel that access common resources, at best, can slow execution — potentially slower than if you programmed for serial execution — and, at worst, can produce incorrect results or cause the program to hang. A simple example is a shared variable that is accessed and updated by two or more threads. If one thread stored a result in the variable after the other thread has retrieved the value for updating, the result stored by the first thread will be lost and the result will be incorrect. The same kind of problem arises with updating files.
So, what are the typical characteristics of applications that may benefit from using more than one processor? First, these applications will involve operations that require substantial amount of processor time, measured in seconds rather than milliseconds. Second, the heavy computation will involve a loop of some kind. Third, the computation will involve operations that can be divided into discrete but significant units of calculation that can be executed independently of one another.
The Parallel Patterns Library (PPL) that is defined in the ppl.h header provides you with tools for implementing parallel processing in your applications, and these tools are defined within the Concurrency namespace. The PPL defines three kinds of facilities for parallel processing:
In general, the PPL operates on a unit of work or task that is defined by a function object or, more typically, a lambda expression. You don't have to worry about creating threads of execution or allocating work to particular processors because in general the PPL takes care of this automatically. What you do have to do is to make sure your code is organized appropriately for parallel execution.
The PPL provides three algorithms for initiating parallel execution on multiple cores:
These are defined as templates, but I won't go into the details of the definitions of the templates themselves. You can take a look at the ppl.h header file, if you are interested. Let's take a closer look at how you use each of them.
The parallel_for algorithm executes parallel loop iterations on a single task specified by a function object or lambda expression. The loop iterations are controlled by an integer index that is incremented on each iteration until a given limit is reached, just like a regular for loop. The function object or lambda expression that does the work must have a single parameter; the current index value will be passed as the argument corresponding to this parameter on each iteration. Because of the parallel nature of the operation, the iterations will not be executed in any particular order.
There are two versions of the parallel_for algorithm. The first has the form:
parallel_for(start_value, end_value, function_object);
This executes the task specified by the third argument, with index values running from start_value to end_value-1, and the default increment of 1. The first two arguments must be of the same integer type. If they are not, you will get a compile-time error. As I said, because iterations are executed in parallel, they will not be executed in sequence. This implies that each execution of the function object or lambda expression must be independent of the others, and the result must not depend on executing the task in a particular sequence.
Here's a fragment that shows how the parallel_for algorithm works:
const size_t count(100000);
long long squares[count];
Concurrency::parallel_for(static_cast<size_t>(0), count, [&squares](size_t n)
{ squares[n] = (n+1)*(n+1); });The computational task for each loop iteration is defined by the lambda expression, which is the third argument. The capture clause just accesses the squares array by reference. The function computes the square of n+1, where n is the current index value that is passed to the lambda, and stores the result in the nth element of the squares array. This will be executed for values of n, from 0 to count-1, as specified by the first two arguments. Note the cast for the first argument. Because count is of type size_t, the code will not compile without it. Because 0 is a literal of type int, without the cast, the compiler will not be able to decide whether to use type int or type size_t as a type parameter for the parallel_for algorithm template.
Although this fragment shows how the parallel_for algorithm can be applied, the increase in performance in this case may not be great, and indeed, you may find that things run more slowly than serial operations. The computation on each iteration in the example is very short, and inevitably there is some overhead in allocating the task to a processor on each iteration. The overhead may severely erode any reduction in execution time in computations that are relatively short. You should also not be misled by this simple example into thinking that implementing the use of parallel processing is trivial, and that you can just replace a for loop by a parallel_for algorithm. As you will see later in this chapter, all sorts of complications can arise in a more realistic situation.
Although with a parallel_for algorithm the index must always be ascending, you can arrange for descending index values inside the function that is being executed:
const size_t count(100000); long long squares[count];
Concurrency::parallel_for(static_cast<size_t>(0), count,
[&squares, &count](size_t n)
{ squares[count-n-1] = (n+1)*(n+1); });Here, the squares of the index values passed to the lambda will be stored in descending sequence in the array.
The second version of the parallel_for algorithm has the following form:
parallel_for(start_value, end_value, increment, pointer_to_function);
Here, the second argument specifies the increment to use in iterating from start_value to end_value-1, so this provides for steps greater than 1. The second argument must be positive because only increasing index values are allowed in a parallel_for algorithm. The first three arguments must all be of the same integer type. Here's a fragment using this form of the parallel_for algorithm:
size_t start(1), end(300001), step(3);
vector<double> cubes(end/step + 1);
Concurrency::parallel_for(start, end, step, [&cubes](int n)
{ cubes[(n-1)/3] = static_cast<double>(n)*n*n; });This code fragment computes the cubes of integers from 1 to 300001 in steps of 3 and stores the values in the cubes vector. Thus, the cubes of 1, 4, 7, 10, and so on, up to 29998, will be stored. Of course, because this is a parallel operation, the values may not be stored in sequence in the vector.
Note that operations on STL containers are not thread-safe, so you must take great care when using them in parallel operations. Here, it is necessary to pre-allocate sufficient space in the vector to store the results of the operation. If you were to use the push_back() function to store values, the code would crash.
Because parallel_for is a template, you need to take care to ensure that the start_value, end_value, and increment arguments are of the same type. It is easy to get it wrong if you mix literals with variables. For example, the following will not compile:
size_t end(300001);
vector<double> cubes(end/3 + 1);
Concurrency::parallel_for(1, end, 3, [&cubes](size_t n)
{ cubes.push_back (static_cast<double>(n)*n*n); });This doesn't compile because the literals that are the first and third arguments are of type int, whereas count is of type size_t. The effect is that no compatible template instance can be found by the compiler.
The parallel_for_each algorithm works in a similar way to parallel_for, but the function operates on an STL container. The number of iterations to be carried out is determined by a pair of iterators. This algorithm is of the form:
Concurrency::parallel_for_each(start_iterator, end_iterator, function_object);
The function object specified by the third argument must have a single parameter of the type stored in the container that the iterators will access. This will enable you to access the object in the container that is referred to by the current iterator. Iterations run from start_iterator to end_iterator-1.
Here's a code fragment that illustrates how this works:
std::array<string, 6> people = {"Mel Gibson", "John Wayne", "Charles Chaplin",
"Clint Eastwood", "Jack Nicholson", "George Clooney"};
Concurrency::parallel_for_each(people.begin(), people.end(), [](string& person)
{
size_t space(person.find(' '));
std::string first(person.substr(0, space));
std::string second(person.substr(space + 1, person.length() - space - 1));
person = second + ' ' + first;
});
std::for_each(people.begin(), people.end(), [](std::string& person)
{std::cout << person << std::endl; });The parallel_for_each algorithm operates on the people array. Obviously, a real application would have more than 6 elements. The third argument specifies the function that does the work on each iteration. The parameter is a reference to type string because the elements in people are of type string. The function reverses the order of the names in each string. The last statement uses the STL for_each algorithm to list the contents of the people array. You can see that the PPL parallel_for_each algorithm has essentially the same syntax as the STL for_each algorithm.
Note that none of the parallel algorithms provide for premature termination of the operation. With a for loop, for example, you can use a break statement to terminate the loop, but this does not apply with the parallel algorithms. The only way to terminate the operation of a parallel algorithm before all concurrent operations have been completed is to throw an exception from within the function that defines the work to be done. This will stop all parallel operations immediately. Here's an example of how you can do that:
int findIndex(const std::array<string, 6>& people, const std::string& name)
{
try
{
Concurrency::parallel_for(static_cast<size_t>(0), people.size(), [=](size_t n)
{
size_t space(people[n].find(' '));
if(people[n].substr(0, space) == name)
throw n;
});
} catch(size_t index) { return index; }
return −1;
}This function searches the array from the previous fragment to find a particular name string. The parallel_for compares the name, up to the first space in the current people array element, with the second argument to the findIndex() function. If it's a match, the lambda expression throws an exception that will be the current index to the people array. This will be caught in the catch clause in the findIndex() function, and the value that was thrown will be returned. Throwing the exception terminates all current activity with the parallel_for operation. The findIndex() function returns −1 if the parallel_for operation terminates with no exception having been thrown, because this indicates that name was not found. Let's see if it works.
TRY IT OUT: Terminating a parallel_for operation
To exercise the findIndex() function, you can append some code to the previous fragment that uses the parallel_for_each algorithm to reverse the sequence of names. Here's the complete program:
// Ex13_01.cpp Terminating a parallel operation
#include <iostream>
#include "ppl.h"
#include <array>
#include <string>
using namespace std;
using namespace Concurrency;
// Find name as the first name in any people element
int findIndex(const array<std::string, 6>& people, const string& name)
{
try
{
parallel_for(static_cast<size_t>(0), people.size(), [=](size_t n)
{
size_t space(people[n].find(' '));
if(people[n].substr(0, space) == name)
throw n;
});
} catch(size_t index) { return index; }
return −1;
}
int main()
{
array<string, 6> people = {"Mel Gibson", "John Wayne", "Charles Chaplin",
"Clint Eastwood", "Jack Nicholson", "George Clooney"};
parallel_for_each(people.begin(), people.end(), [](string& person)
{
size_t space(person.find(' '));
string first(person.substr(0, space));
string second(person.substr(space+1, person.length()-space-1));
person = second +' ' + first;
});
for_each(people.begin(), people.end(), [](string& person)
{cout << person << endl; });
string name("Eastwood");
size_t index(findIndex(people, name));
if(index == −1)
cout << name << " not found." << endl;
else
cout << name << " found at index position " << index << '.' << endl;
return 0;
}
Executing this example produces the following output:
Gibson Mel Wayne John Chaplin Charles Eastwood Clint Nicholson Jack Clooney George Eastwood found at index position 3.
How It Works
The parallel_for_each algorithm interchanges the first and second names in each element of the people array with operations working in parallel, as I explained in the previous section. The output produced by the STL for_each algorithm shows that this works as described.
You then create the name string that you are looking for. The index variable is initialized with the value returned from the findIndex() function call. The if statement outputs a message depending on the value stored in index, and the last line of output shows that name was indeed found in the people array.
The parallel_invoke algorithm is defined by a template that enables you to execute up to 10 tasks in parallel. Obviously, there is no point in attempting to execute more tasks in parallel than you have processors on your computer. You specify each task to be executed by a function object, which, of course, can be a lambda expression, so the arguments to the parallel_invoke algorithm are the function objects specifying the tasks to be executed in parallel. Here's an example:
std::array<double, 500> squares;
std::array<double, 500> values;
Concurrency::parallel_invoke(
[&squares]
{ for(size_t i = 0 ; i<squares.size() ; ++i)
squares[i] = (i+1)*(i+1);
},
[&values]
{ for(size_t i = 0 ; i<values.size() ; ++i)
values[i] = std::sqrt(static_cast<double>((i+1)*(i+1)*(i+1)));
});The arguments to the parallel_invoke algorithm are two different lambda expressions. The first stores the squares of successive integers in the squares array, and the second stores the square root of the cube of successive integers in the values array. These lambdas are completely independent of one another and therefore can be executed in parallel.
The examples and code fragments that I have used up to now have not been computations that really take advantage of parallel execution. Let's look at something that does.
To explore the practicalities of parallel processing, and to see the advantages, we need a computation that is chunky enough to warrant parallel processing. We also need something we can use to explore some of the pitfalls and problems that can arise with parallel operations.
The problem I have chosen does not involve a lot of code but does involve doing some calculations with complex numbers. In case you have never heard of complex numbers or maybe you did know something about them at one time but have since forgotten, I'll first give you a brief explanation of what they are and how operations on them work — just enough to understand what the calculations are about. Then we will get into the code. Take my word for it: it's not difficult, and the results are interesting.
A complex number is a number of the form a + bi, where i is the square root of −1. Thus, 1 + 2i and 0.5 − 1.2i are examples of complex numbers. The a is referred to as the real part of the complex number, and the b that is multiplied by i is referred to as the imaginary part. Complex numbers are often represented in the complex plane, as Figure 13-1 illustrates.
To add two complex numbers, you just add the real parts and the imaginary parts separately to get the real and imaginary parts for the result. Thus, adding 1 + 2i and 0.5 − 1.2i produces (1 + 0.5) + (2 − 1.2)i, so the result is 1.5 + 0.8i.
Multiplying two complex numbers a + bi and c + di works like this:
| a, c + di. + bi(c + di) |
Remembering that i is the square root of −1, so i2 is −1, you can expand the expression above to:
| ac + adi + bci − bd |
Thus, the final result is the complex number:
| (ac − bd) + (ad + bc)i |
Multiplying the two example numbers that I introduced at the beginning will therefore result in the number (0.5 + 2.4) + (−1.2 + 1.0)i, which is 2.9 − 0.2i. Multiplying a number a + bi by itself results in
| (a2 − b2) + 2abi |
Now let's consider what the problem is about. The Mandelbrot set is a very interesting region of the complex plane that is defined by iterating the equation:
| Zn+1 = Z2n + c where Z0 = c |
for all points c over an area of the complex plane. By iterating, I mean that for any point c in the complex plane, you set Z0 to c and use the equation to calculate Z1 as c2+c You then use Z1 to calculate Z2 using the equation, then Z2 to calculate Z3, and so on, repeating the operation for some large number of iterations. So how does this tell you which points are in the Mandelbrot set? If the distance from the origin (shown in Figure 13-1) of any Zn exceeds 2, then continuing the iterations will result in the point moving further and further away from the origin towards infinity, so you don't need to iterate it further. All points that escape like this are not in the Mandelbrot set. Any point that does not diverge in this way after a given large number of iterations belongs to the Mandelbrot set. Any point that starts out more than a distance 2 from the origin will not belong to the Mandelbrot set, so this gives us an idea of the area in the complex plane in which to look.
Here's a function that iterates the equation for the Mandelbrot set:
size_t IteratePoint(double zReal, double zImaginary, double cReal, double cImaginary)
{
double zReal2(0.0), zImaginary2(0.0); // z components squared
size_t n(0);
for( ; n < MaxIterations ; ++n) // Iterate equation Zn = Zn-1**2 + K
{ // for Mandelbrot K = c and Z0 = c
zReal2 = zReal*zReal;
zImaginary2 = zImaginary*zImaginary;
if(zReal2 + zImaginary2 > 4) // If distance from origin > 2, point will
break; // go to infinity so we are done// Calculate next Z value
zImaginary = 2*zReal*zImaginary + cImaginary;
zReal = zReal2 - zImaginary2 + cReal;
}
return n;
}The IteratePoint() function iterates the equation Zn+1=Z2n+c with the starting point, ,Z-0., specified by the first two parameters and the complex constant c, specified by the last two parameters. MaxIterations is the maximum number of times to plug Z back into the equation, and it needs to be defined as a global constant. The for loop calculates a new Z, and if its distance from the origin is greater than 2, the loop is terminated and the current value of n is returned. The if expression actually compares the square of the distance from the origin to 4, to avoid having to execute the computationally expensive square root function. If the loop ends normally, then n will have the value MaxIterations, and this value will be returned.
So, maybe the for loop in the IteratePoint() function is a candidate for parallel operations? No, I'm afraid not. Each loop iteration requires the Z from the previous iteration to be available, so this is essentially a serial operation. However, there are other possibilities. To figure out the extent of the Mandelbrot set, we will have to call this function for every point in a region of the complex plane. In that context, we will have lots of potential for parallel computation.
In order to visualize the Mandelbrot set, we will display it as an image in the client area of a window; we will treat the pixels in the client area as though they are points in the complex plane. This implies that we will need a loop to test every pixel in the client area to see whether it's in the Mandelbrot set. In broad terms, the loop will look like this:
for(int y = 0 ; y < imageHeight ; ++y) // Iterate over image rows
{
for(int x = 0 ; x < imageWidth ; ++x) // Iterate over pixels in a row
// Iterate current point x+yi...
}
// Display the yth row...
}Each pixel in the image will correspond to a particular point in a region of the complex plane. The pixel coordinates run from 0 to imageWidth along a row and from 0 to imageHeight down the y-axis of the client area. We need to map the pixels1 coordinates to the area of the complex plane we are interested in. A good region to explore to find the Mandelbrot set is the area containing real parts — which will be the x-axis in the window — from −2.1 to +2.1 and the area containing the imaginary parts — the y-axis in the window — from −1.3 to +1.3. However, the client area of a window may not have the same aspect ratio as this, so ideally, we should make sure to map the pixels to the complex plane so that we maintain the same scale on both axes. This will prevent the shape of the Mandelbrot set from being squashed or elongated. To do this, we can calculate factors to convert from pixel coordinates to the complex plane as follows:
// Client area axes const double realMin(−2.1); // Minimum real value double imaginaryMin(−1.3); // Minimum imaginary value double imaginaryMax(+1.3); // Maximum imaginary value
// Set maximum real so axes are the same scale double realMax(realMin+(imaginaryMax-imaginaryMin)*imageWidth/imageHeight); // Get scale factors to convert pixel coordinates double realScale((realMax-realMin)/(imageWidth-1)); double imaginaryScale((imaginaryMax-imaginaryMin)/(imageHeight-1));
The realMax value is the maximum real value, and this is calculated so that the real and imaginary axes have the same scale. The realScale and imaginaryScale variables hold factors that we can use to multiply the x and y pixel coordinates, respectively, to convert them to complex plane values.
Let's put a working program together.
TRY IT OUT: Displaying the Mandelbrot Set
You are going to create a Windows API program to do this. Create a new Win32 Application project with the default application settings, which will be for a Windows application. I called this Ex13_02A. When the project has been created, change the value for the Character Set project property to Not Set, because we won't be using Unicode. Rather than accept the default settings for the window that is to be created, modify the call to CreateWindow() in the InitInstance() function to:
hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW, 100, 100, 800, 600, NULL, NULL, hInstance, NULL);
The window will now be located at position 100,100, and its size will be 800×600. If you have a large screen with lots of pixels, by all means change the window size to suit your display. Remember, though, that the more pixels there are in the window, the longer it will take to execute the program.
Note that I use NULL for a null pointer in this example, and in the other examples in this chapter, just for consistency with the code that is generated automatically. Elsewhere in the book, I use the new language keyword, nullptr.
Now add the following definition at global scope:
const size_t MaxIterations(8000); // Maximum iterations before infinity
The appropriate value for MaxIterations depends on how finely the complex plane is represented. The more detail you can display, the higher this value needs to be. The value here is much higher than is necessary for the typical client area, but I set it this way so the elapsed time to compute the Mandelbrot set will be a significant number of seconds.
Next, you can add three global function prototypes, following the existing prototypes at the beginning of the source file:
size_t IteratePoint(double zReal, double zImaginary, double cReal, double cImaginary); COLORREF Color(int n); // Selects a pixel color based on n void DrawSet(HWND hwnd); // Draws the Mandelbrot set
You can now add the definition for the IteratePoint() function to the end of the source file, exactly as it appears in the previous section.
Add the following Color() function definition:
COLORREF Color(int n)
{
if(n == MaxIterations) return RGB(0, 0, 0);
const int nColors = 16;
switch(n%nColors)
{
case 0: return RGB(100,100,100); case 1: return RGB(100,0,0);
case 2: return RGB(200,0,0); case 3: return RGB(100,100,0);
case 4: return RGB(200,100,0); case 5: return RGB(200,200,0);
case 6: return RGB(0,200,0); case 7: return RGB(0,100,100);
case 8: return RGB(0,200,100); case 9: return RGB(0,100,200);
case 10: return RGB(0,200,200); case 11: return RGB(0,0,200);
case 12: return RGB(100,0,100); case 13: return RGB(200,0,100);
case 14: return RGB(100,0,200); case 15: return RGB(200,0,200);
default: return RGB(200,200,200);
};
}
This function chooses a color for a pixel based on the value of the parameter n, which will be the value returned by the IteratePoint() function. The RGB macro forms a DWORD value specifying a color from three 8-bit values for intensities of the primary colors, red, green, and blue. The value of each color component can be from zero to 255. All values at zero will result in black, and all values at 255 will result in white.
The color-selection process based on n is arbitrary. I chose to use the remainder after dividing n by the number of colors, as this works reasonably well with the value I have set for MaxIterations. A more common approach is to select a color based on where the value of n lies in the interval 0 to MaxIterations-1, with the interval being divided into as many equal subdivisions as the number of colors you want to use, and MaxIterations representing black. However, this works better with a lower value for MaxIterations. You can try varying the mechanism for coloring pixels yourself.
You can also add the following definition for DrawSet() to the source file:
void DrawSet(HWND hWnd)
{
// Get client area dimensions, which will be the image size
RECT rect;
GetClientRect(hWnd, &rect);
int imageHeight(rect.bottom);
int imageWidth(rect.right);
// Create bitmap for one row of pixels in image
HDC hdc(GetDC(hWnd)); // Get device context
HDC memDC = CreateCompatibleDC(hdc); // Get device context to draw pixels
HBITMAP bmp = CreateCompatibleBitmap(hdc, imageWidth, 1);
HGDIOBJ oldBmp = SelectObject(memDC, bmp); // Select bitmap into DC
// Client area axes
const double realMin(−2.1); // Minimum real value
double imaginaryMin(−1.3); // Minimum imaginary value
double imaginaryMax(+1.3); // Maximum imaginary value// Set maximum imaginary so axes are the same scale
double realMax(realMin+(imaginaryMax-imaginaryMin)*imageWidth/imageHeight);
// Get scale factors to convert pixel coordinates
double realScale((realMax-realMin)/(imageWidth-1));
double imaginaryScale((imaginaryMax-imaginaryMin)/(imageHeight-1));
double cReal(0.0), cImaginary(0.0); // Stores c components
double zReal(0.0), zImaginary(0.0); // Stores z components
for(int y = 0 ; y < imageHeight ; ++y) // Iterate over image rows
{
zImaginary = cImaginary = imaginaryMax - y*imaginaryScale;
for(int x = 0 ; x < imageWidth ; ++x) // Iterate over pixels in a row
{
zReal = cReal = realMin + x*realScale;
// Set current pixel color based on n
SetPixel(memDC, x, 0, Color(IteratePoint(zReal, zImaginary, cReal, cImaginary)));
}
// Transfer pixel row to client area device context
BitBlt(hdc, 0, y, imageWidth, 1, memDC, 0, 0, SRCCOPY);
}
SelectObject(memDC, oldBmp);
DeleteObject(bmp); // Delete bitmap
DeleteDC(memDC); // and our working DC
ReleaseDC(hWnd, hdc); // and client area DC
}
This version of the function is strictly serial execution. We will get to a parallel version once we have this working. The parameter of type HWND provides access within the function to the current window. You need this to be able to find out the size of the client area, and to draw on it. The call to the Windows API GetClientRect() function places data about the client area of the window you specify by the first argument, in a RECT structure that you supply as the second argument. The RECT structure will contain the coordinates of the top left and bottom right points of the client area of the window. The public members of the structure that will contain the x, y coordinates of the top-left corner, are left and top and right and bottom will contain the coordinates of the bottom-right corner. The coordinates of the top-left point will be 0,0, so the width and height of the client area are right and bottom, respectively.
To draw in the client area, we need a device context (DC). A device context is a structure that you use to draw or display text in a window. You obtain a DC from Windows by calling the GetDC() function with a handle to the window you want to work with as the argument. The function returns a handle to a DC that encapsulates the client area of the window. You won't be writing pixels to this DC directly. You will assemble the pixels for a row in the image in a bitmap, and then transfer this to the DC. To do this, you first have to create a compatible DC, memDC, which is a DC in memory with the same pixel color range as the window client area DC. Initially, this DC will be able to store only 1x1 pixels, so you'll need to adjust it. You then create a handle to a bitmap object, bmp, that can store one row of pixels ( imageWidth long by 1 pixel high) by calling the CreateCompatibleBitmap()function. Calling the SelectObject() function replaces an existing object in the DC, specified by the first argument, with the one you pass as the second argument, so selecting bmp into memDC provides memDC with the capacity to hold an image row of pixels.
After you've created and initialized variables to hold Z and the constant c, you have two nested for loops. The outer loop iterates over the image rows, and the inner loop iterates over the pixels in a row. The inner loop assembles a row of pixels in the image in memDC, using the SetPixel() API function to set each pixel to a color determined by the value returned by the IteratePoint() function. The arguments to SetPixel() are the DC, the x and y coordinates of the pixel to be set, and the color.
The memDC context is reused for each row of pixels in the client area, so before starting the next row, you write the contents of memDC to the client area DC, hdc; using the BitBlt() function (Bit Block Transfer). The arguments to this function are the destination DC (hdc); the coordinate of the first pixel; the number of pixels in a row (imageWidth) and the number of rows (1); the source DC (memDC); the x and y coordinates of the first pixel is the source DC (0,0); and a raster operation code (SRCCOPY) that determines how the source pixels are to be combined with the destination.
Finally, after the nested loops finish executing, you delete the bitmap and the DC resource you created, and release the DC you obtained from Windows, because they are no longer required.
The last bit of code you need to add is in the WndProc() function:
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
// TODO: Add any drawing code here...
DrawSet(hWnd);
EndPaint(hWnd, &ps);
break;You just need to add the call to DrawSet() as the action for a WM_PAINT message.
When you compile and execute the example, you should get the window shown in Figure 13-2.
Of course, on your screen, it will be in glorious technicolor. The Mandelbrot set is the black region. The set is of finite area, clearly, because it lies inside a circle of radius 2, but its perimeter is of infinite length. Moreover, any segment of its perimeter, no matter how small, is also of infinite length, so there are unlimited possibilities for exploration of the boundaries of the set by scaling the image. The colored areas around the set produce some very interesting patterns, especially when they are scaled up.
TRY IT OUT: Drawing the Mandelbrot Set Using parallel_invoke
You are going to create a new version of the DrawSet() function called DrawSetParallel(), but don't replace the original. Keep both versions in the source code for the example. You will be able to use both in a later evolution of this program. This version of the program is Ex13_02B in the code download.
To improve the performance of the program, you could use the parallel_invoke algorithm to compute two or more rows of the image simultaneously, depending on how many cores or processors your machine has. However, the fact that you must not write to a DC in parallel, because DCs are strictly serial facilities is a major limitation. This means that the SetPixel() and BitBlt() function calls are a problem.
One way to deal with the call SetPixel() is to create a separate memory DC and bitmap for each concurrent row computation. If you provide separate DCs and bitmaps for the concurrent tasks that you pass to parallel_invoke, they can execute without interfering with one another. I'll define the DrawSetParallel() function for two cores, because that's all I have in my computer. If you have more, you can extend the code accordingly. The code for a parallel version of DrawSet() might look like this:
void DrawSetParallel(HWND hWnd){ HDC hdc(GetDC(hWnd)); // Get device context // Get client area dimensions, which will be the image size RECT rect; GetClientRect(hWnd, &rect); int imageHeight(rect.bottom); int imageWidth(rect.right);// Create bitmap for one row of pixels in imageHDC memDC1 = CreateCompatibleDC(hdc); // Get device context to draw pixelsHDC memDC2 = CreateCompatibleDC(hdc); // Get device context to draw pixelsHBITMAP bmp1 = CreateCompatibleBitmap(hdc, imageWidth, 1);HBITMAP bmp2 = CreateCompatibleBitmap(hdc, imageWidth, 1);HGDIOBJ oldBmp1 = SelectObject(memDC1, bmp1); // Select bitmap into DC1HGDIOBJ oldBmp2 = SelectObject(memDC2, bmp2); // Select bitmap into DC2// Client area axes const double realMin(−2.1); // Minimum real value double imaginaryMin(−1.3); // Minimum imaginary value double imaginaryMax(+1.3); // Maximum imaginary value // Set maximum real so axes are the same scale double realMax(realMin+(imaginaryMax-imaginaryMin)*imageWidth/imageHeight); // Get scale factors to convert pixel coordinates double realScale((realMax-realMin)/(imageWidth-1)); double imaginaryScale((imaginaryMax-imaginaryMin)/(imageHeight-1));
// Lambda expression to create an image rowstd::function<void(HDC&, int)> rowCalc = [&] (HDC& memDC, int yLocal){double zReal(0.0), cReal(0.0);double zImaginary(imaginaryMax - yLocal*imaginaryScale);double cImaginary(zImaginary);for(int x = 0 ; x < imageWidth ; ++x) // Iterate over pixels in a row{zReal = cReal = realMin + x*realScale;// Set current pixel color based on nSetPixel(memDC, x, 0, Color(IteratePoint(zReal, zImaginary, cReal, cImaginary)));}};for(int y = 1 ; y < imageHeight ; y += 2) // Iterate over image rows{Concurrency::parallel_invoke([&]{rowCalc(memDC1, y-1);}, [&]{rowCalc(memDC2, y);});// Transfer pixel rows to client area device contextBitBlt(hdc, 0, y-1, imageWidth, 1, memDC1, 0, 0, SRCCOPY);BitBlt(hdc, 0, y, imageWidth, 1, memDC2, 0, 0, SRCCOPY);}// If there's an odd number of rows, take care of the last oneif(imageHeight%2 == 1){rowCalc(memDC1, imageWidth-1);BitBlt(hdc, 0, imageHeight-1, imageWidth, 1, memDC1, 0, 0, SRCCOPY);}SelectObject(memDC1, oldBmp1);SelectObject(memDC2, oldBmp2);DeleteObject(bmp1); // Delete bitmap 1DeleteObject(bmp2); // Delete bitmap 2DeleteDC(memDC1); // and our working DC 1DeleteDC(memDC2); // and our working DC 2ReleaseDC(hWnd, hdc); // Release client area DC}
The bits that are new or changed from the DrawSet() function are shown in bold. You can see that there's quite a lot that's different from the original version of the function. You now create two memory DCs and two bitmaps, one for each of two parallel tasks. If you have four cores in your computer, you can create four of each of these.
The code for each task to run in parallel is the same, so rather than repeating the code in each of the arguments to parallel_invoke, you define a function variable, rowCalc, to encapsulate it. This uses the function template that I introduced in Chapter 10, defined in the functional header. The arguments to the rowCalc object are a memory DC and a value for yLocal, which will be the row index for the row to be calculated. The variables storing the components of Z and c are now inside the rowCalc function because these cannot be shared between parallel processes. The rowCalc function iterates over the pixels in a row, as before, and sets the pixel color in the memory DC that is passed to it, using the value returned by IteratePoint().
In the loop over rows that is indexed by y, y now starts at 1 and proceeds in steps of 2 because you are going to compute rows y and y-1 in parallel. You do this with the call to the parallel_invoke algorithm. The arguments to the algorithm are lambda expressions that call rowCalc with arguments that select the DC and the y value to be used. When the parallel_invoke algorithm returns, you transfer the pixels from each memory DC to the window DC, hdc, serially.
If imageHeight is odd, then the last row will not have been processed, so you have to treat this as a special case to complete the image. This just involves calling rowCalc for the last row with index value imageHeight-1. Finally, you delete the memory DCs and bitmaps when the computation is complete.
Before compiling and executing the new version, you should add a prototype for DrawSetParallel() to the source file and change the action for the WM_PAINT message in WndProc() to call this new function. You also need to add the following #include directives:
#include "ppl.h" #include <functional> // For the function<> template
When you run this new version of the program, you should get the same image of the Mandelbrot set displayed, but faster. It would be nice to know how much faster though, wouldn't it?
Timing Execution
You will add a class to the application that defines a high-resolution timer that you can start when the computation begins and can stop when it ends. This version is in the code download as Ex13_02C. You will also add the capability to execute either DrawSet() for serial execution, or DrawSetParallel(), and see how long they take to execute. You'll be able to switch between serial and parallel execution by right-clicking the mouse. A good place to display the time will be in a status bar at the bottom of the application window, so you will add that to the application, too.
The HRTimer class will use the Windows API function for accessing a high-resolution timer. Not all systems have a high-resolution timer, so if yours doesn't, the timer will not work. I'll explain the bare bones of how this class works and leave you to research the fine detail.
Add a new header file, HRTimer.h, to the application and insert the following code:
#pragma once
#include "windows.h"
class HRTimer
{
public:
// Constructor
HRTimer(void) : frequency(1.0 / GetFrequency()) { }
// Get the timer frequency - clock ticks per second
double GetFrequency(void)
{
LARGE_INTEGER proc_freq;
::QueryPerformanceFrequency(&proc_freq);
return static_cast<double>(proc_freq.QuadPart);
}
// Start the timer
void StartTimer(void)
{
// Set thread to use processor 0
DWORD_PTR oldmask = ::SetThreadAffinityMask(::GetCurrentThread(), 0);::QueryPerformanceCounter(&start);
::SetThreadAffinityMask(::GetCurrentThread(), oldmask); // Restore original
}
// Stop the timer and return elapsed time in seconds
double StopTimer(void)
{
// Set thread to use processor 0
DWORD_PTR oldmask = ::SetThreadAffinityMask(::GetCurrentThread(),0);
::QueryPerformanceCounter(&stop);
::SetThreadAffinityMask(::GetCurrentThread(), oldmask); // Restore original
return ((stop.QuadPart - start.QuadPart) * frequency);
}
private:
LARGE_INTEGER start; // Stores start ime
LARGE_INTEGER stop; // Stores stop time
double frequency; // Time for one clock tick in seconds
};A high-resolution timer has a frequency — the clock tick rate per second — that can vary from one processor to another, so to use a timer, you must find out what the frequency is. The ::QueryPerformanceFrequency() function does this, and stores the result in the LARGE_INTEGER variable you pass as the argument. You call this function in the GetFrequency() member function that is called by the class constructor to initialize the frequency member of the class. The frequency member stores the time in seconds, between one clock tick and the next, as a value of type double; this is calculated as the reciprocal of the timer frequency. The LARGE_INTEGER type is an 8-byte union that is defined in Windows.h. It combines two structs as members, which I won't go into, because we won't be using them, plus a QuadPart member that is a signed 64-bit integer.
Once you have created a HRTimer object, you start the timer by calling its StartTimer() function. The start time is returned by the ::QueryPerformanceCounter() function and stored in the start member. The call to ::SetThreadAffinityMask(), before getting the start time, is to ensure the call is executed on a specific processor, processor 0. The StopTimer() member function that records the stop time and returns the elapsed time will execute on the same processor. This is to remove the possibility of problems arising from these calls executing on different processors.
To stop the timer, call StopTimer() for the timer object. This function computes the elapsed time from when you called StartTimer() by taking the difference between the two values (QuadPart, which treats the stop and start values as 64-bit signed integers) and multiplying by the frequency member. This will result in the elapsed time in seconds being returned as a value of type double.
To use an HRTimer object in Ex13_02.cpp, first add an #include directive for HRTimer.h to the source file. Then you can create a timer object at global scope by adding the following statement to the other global definitions in the file:
HRTimer timer; // Timer object to calculate processor time
You'll add the code to use the timer after you have added a status bar to the application window.
A status bar, like most entities that are displayed in Windows, is just another window, so you create a status bar by calling the CreateWindowEx() API function. The place to add the code that creates the status bar is in the InitInstance() function, so add the following code immediately before the call to ShowWindow():
HWND hStatus = CreateWindowEx(0, STATUSCLASSNAME, NULL,
WS_CHILD | WS_VISIBLE | SBARS_SIZEGRIP, 0, 0, 0, 0,
hWnd, (HMENU)IDC_STATUS, GetModuleHandle(NULL), NULL);
if(!hStatus) // Make sure we have a status bar
return FALSE; // and return false if we don't
// Set up the panels in the status bar
int statwidths[] = {100,200, −1};
SendMessage(hStatus, SB_SETPARTS, sizeof(statwidths)/sizeof(int), (LPARAM)statwidths);
SendMessage(hStatus, SB_SETTEXT, 0, (LPARAM)_T("Processor Time :"));
SendMessage(hStatus, SB_SETTEXT, 2, (LPARAM)_T(" Right-click for parallel execution"));The second argument to CreateWindowEx() specifies the window to be a status bar with the standard class name STATUSCLASSNAME. There are many other standard class names for other kinds of controls (defined in the commctrl.h header), such as toolbars, buttons, and so on. The status bar will be a child window to the main window, hWnd. It will be visible, and it will have a size grip at the right end of the status bar. The size and position of the status bar will be determined by default to be along the bottom of the parent window and with a height to accommodate the default font. The IDC_STATUS symbol that appears in the 10th argument is a unique integer constant that identifies the status bar control. You need to add this to the resources for the project. Display the Resource View and right-click the .rc file name. Select Resource Symbols... from the popup to display the Resource Symbols dialog. Click on the New... button, enter the name as IDC_STATUS, and click on OK. Click on Close to close the dialog. The value for the new symbol will be chosen automatically to be different from the existing symbol values.
Each element in the statwidths array specifies the size, in logical units, of a part in the status bar, in which you will be displaying text. The array here defines three parts where the last part width is −1, which specifies that it takes up whatever space is left after the first two have been allocated space. The SendMessage() function sends a message to the window specified by its first argument — in this case, the status bar. You set the status bar parts by sending an SB_PARTS message to the status bar, with the third argument specifying the number of parts, and the fourth argument specifying the widths of the parts. The next two SendMessage() calls write text to a particular part of the status bar, the parts being indexed from the left, starting at zero. The first SB_SETTEXT message sets the text specified by the fourth argument in the part specified by the third argument. The last message that is sent sets the text for the third part. You'll use the second status bar part to show the elapsed time in seconds, when you have computed it.
In order to compile this code, you must add an #include directive for the commctrl.h header to the source file. If you execute the program at this point, you should see a status bar at the bottom of the application window.
Switching between Serial and Parallel Execution
First, add a global variable to Ex13_02C.cpp with the following definition:
bool parallel(false); // True for parallel execution
This is an indicator you will use to select which client area drawing function to call when the WM_PAINT message is received. You can toggle the value of this variable by handling the WM_RBUTTONDOWN message that is sent when the right mouse button is pressed. Add the following case statement in the switch in the WndProc() function:
case WM_RBUTTONDOWN:
parallel = !parallel; // Toggle the indicator
// Now update the message in the status bar
SendMessage(GetDlgItem(hWnd, IDC_STATUS), SB_SETTEXT, 2,
(LPARAM)(parallel ?
_T(" Right-click for serial execution") :
_T(" Right-click for parallel execution")));
InvalidateRect (hWnd, NULL, TRUE);
UpdateWindow (hWnd);
break;Here, you toggle the parallel variable and send a message to the status bar to update the text in the third status bar part to reflect the current value of parallel. The call to InvalidateRect() defines the region of the window specified by the first argument that needs to be redrawn when the next WM_PAINT message is received. The second argument is a RECT object that defines the region of the client area that is to be redrawn, but the NULL value here specifies the entire client area of the window. The third argument is TRUE if the client area is to be erased before being redrawn. The call to UpdateWindow() sends a WM_PAINT message to the application window, which will cause the Mandelbrot set to be recomputed either serially or in parallel, once we have finalized the code to do that.
Now you can update the code that processes the WM_PAINT message to draw the client area of the window:
case WM_PAINT: hdc = BeginPaint(hWnd, &ps); // TODO: Add any drawing code here...if(parallel)DrawSetParallel(hWnd);elseDrawSet(hWnd);EndPaint(hWnd, &ps);break;
Handling the message now involves choosing which function to call to compute the Mandelbrot set, based on the value of parallel. When parallel is true, you run the parallel version of the function, and when it is false, the serial version.
We can start and stop the global timer we have created in the code that handles the WM_PAINT message, but we have a slight problem. As you saw earlier, a HRTimer object returns elapsed time as a value of type double. Displaying this in the status bar requires that it be in the form of a null-terminated text string. Your first step in using a timer is to add a function that will accept a time value as type double and update the status bar with a text representation of the double value.
Add the following prototype to Ex13_02C.cpp at the end of the existing function prototypes:
void UpdateStatusBarTime(HWND hWnd, double time);
Here's the function definition to add to the source file:
void UpdateStatusBarTime(HWND hWnd, double time)
{
std:: basic_ stringstream <TCHAR> ss; // Create a string stream
ss.setf(std::ios::fixed, std::ios::floatfield); // Turn on fixed & turn off float
ss.precision(2); // Two decimal places
ss << _T(" ") << time << _T(" seconds"); // Write time to ss
SendMessage(GetDlgItem(hWnd, IDC_STATUS), SB_SETTEXT, 1, (LPARAM)(ss.str().c_str()));
}The hard work is done by the basic_stringstream object, and the basic_stringstream class template is defined in the sstream header, so you need an #include directive for that. A basic_stringstream <TCHAR> object is a stream that transfers the data that you write to it to a string buffer storing characters of type TCHAR. This is very useful for formatting operations. Here, you set the flags for the ss object to transfer a floating-point value to the underlying buffer in a fixed-point representation instead of the default scientific representation. The first argument to the setf() function is the flags to be set, and the second argument is the flags to be unset. Calling the precision() function for ss with the argument as 2 causes floating-point values to have two decimal places after the point. You then write the time value to ss, along with the descriptive text.
You update the status bar with the time string by calling the SendMessage() function. The last argument to the function calls the str() function for ss to retrieve the contents of the stream as a string object. Calling the c_str() function for that produces a null-terminated string. The string pointer argument here has to be of type LPARAM, so you cast the pointer for this string to type LPARAM.
The last step is to amend the handling of the WM_PAINT message in the WndProc() function to use the timer:
case WM_PAINT: hdc = BeginPaint(hWnd, &ps); // TODO: Add any drawing code here...timer.StartTimer();if(parallel) DrawSetParallel(hWnd); else DrawSet(hWnd);UpdateStatusBarTime(hWnd, timer.StopTimer());EndPaint(hWnd, &ps); break;
You should now get the time displayed in the status bar. You can toggle between serial and parallel execution by clicking the right mouse button. This will enable you to see how much performance increase you are getting from parallel execution. I got the window shown in Figure 13-3 running parallel execution on my machine.
This is more than 3 seconds faster than the serial computation on my computer. Keep in mind that other programs running on your computer may have a significant effect on the timings. As well as various operating system services, your virus scanner may be executing in the background, for instance, so don't expect the execution times measured by our example to be necessarily consistent on different occasions. You will find the various stages of development of this example in the code download for the book as Ex13_02A, Ex13_02B, and Ex13_02C.
So, what about the parallel_for algorithm that I spent so much time discussing earlier in this chapter? Can we apply this to speed up the Mandelbrot set calculation, bearing in mind that the calculation consists almost entirely of for loops? Well, we could make the inner loop parallel by creating a new memDC for every image row, but it would be nice to make the outer loop parallel. However, the BitBlt() function call that has to be in the outer loop cannot be executed in parallel because it writes to a DC. This really prevents us from using parallel_for for the outer loop. However, with a little more help from the PPL, maybe we can crack it.
A critical section is a contiguous sequence of statements that cannot be executed by more than one task at any given time. As you saw with the last example, concurrent execution of code that updates a device context will cause problems because a device context is not designed to be used in this way. Critical sections can arise in other contexts, too.
The PPL defines the critical_section class that you can use to identify sequences of statements that must not be executed in parallel.
There is only one constructor for the critical_section class, so creating an object is very simple:
Concurrency::critical_section cs;
This creates the object cs. A critical_section object is a mutex. The name mutex is a contraction of mutual exclusion object. A mutex allows multiple threads of execution to access a given resource, but only one at a time. It provides a mechanism for the thread to lock the resource that it is currently using. All other threads then must wait until the resource is unlocked before another thread can access it.
Once you have created a critical_section object, you can apply a lock to a section of code by calling the lock() member function as follows:
cs.lock(); // Lock the statements that follow
The statements that follow this call to the lock() member function can be executed by only one thread at a time. All other threads are excluded until the unlock() method for the mutex is called, like this:
cs.lock(); // Lock the statements that follow // Code that must be single threaded... cs.unlock(); // Release the lock
Once the unlock() method for the critical_section object has been called, another thread of execution may apply a lock to the code section and execute it.
If a task calls lock() for a critical_section object, and the code is already being executed by another task, the call to lock() will block. In other words, execution of the task trying to lock the code section cannot continue. In many situations this may be inconvenient. It can be the case that there are several different code sections controlled by other mutexes, and if another section is not locked, you could execute that section. In situations where you don't want the call to lock a section of code to block because there are other things you can do, you can use the try_lock() member function:
if(cs.try_lock())
{
// Code that must be single threaded ...
cs.unlock(); // Release the lock
}
else
// Do something else...The try_lock() function does not block if a lock cannot be obtained, but returns a bool value that is true if a lock is obtained, and false otherwise.
I think we have enough additional capability to get over the problems in applying the parallel_for loop to the Mandelbrot set computation.
TRY IT OUT: Using the parallel_for for the Mandelbrot Set
You can just amend the previous example by replacing the DrawSetParallel() function with a new version. In the code download, this example will be Ex13_03.
The simplest approach to applying the parallel_for algorithm is to replace the outer loop in the original DrawSet() function, and then lock the code sections that must not execute concurrently. We will still need to rearrange some of the code though to allow parallel loop operations. Here's the code:
void DrawSetParallel(HWND hWnd){ HDC hdc(GetDC(hWnd)); // Get device context // Get client area dimensions, which will be the image size RECT rect; GetClientRect(hWnd, &rect); int imageHeight(rect.bottom); int imageWidth(rect.right); // Client area axes const double realMin(−2.1); // Minimum real value double imaginaryMin(−1.3); // Minimum imaginary value double imaginaryMax(+1.3); // Maximum imaginary value // Set maximum real so axes are the same scale double realMax(realMin+(imaginaryMax-imaginaryMin)*imageWidth/imageHeight); // Get scale factors to convert pixel coordinates double realScale((realMax-realMin)/(imageWidth-1)); double imaginaryScale((imaginaryMax-imaginaryMin)/(imageHeight-1));Concurrency::critical_section cs; // Mutex for BitBlt() operationConcurrency::parallel_for(0, imageHeight,[&](int y) // Iterate parallel over image rows{cs.lock(); // Lock for access to the client DC// Create bitmap for one row of pixels in imageHDC memDC = CreateCompatibleDC(hdc); // Get device context to draw pixelsHBITMAP bmp = CreateCompatibleBitmap(hdc, imageWidth, 1);cs.unlock(); // We are done with hdc here so unlockHGDIOBJ oldBmp = SelectObject(memDC, bmp); // Select bitmap into DCdouble cReal(0.0), cImaginary(0.0); // Stores c componentsdouble zReal(0.0), zImaginary(0.0); // Stores z componentszImaginary = cImaginary = imaginaryMax - y*imaginaryScale; for(int x = 0 ; x < imageWidth ; ++x) // Iterate over pixels in a row { zReal = cReal = realMin + x*realScale; // Set current pixel color based on n SetPixel(memDC, x, 0, Color(IteratePoint(zReal, zImaginary, cReal, cImaginary)));
}
cs.lock(); // Lock for writing to hdc
// Transfer pixel row to client area device context
BitBlt(hdc, 0, y, imageWidth, 1, memDC, 0, 0, SRCCOPY);
cs.unlock(); // Release the lock
SelectObject(memDC, oldBmp);
DeleteObject(bmp); // Delete bitmap
DeleteDC(memDC); // and our working DC
});
ReleaseDC(hWnd, hdc); // Release the client DC
}
When you substitute this function for the function of the same name in the previous example, you are ready to go. Executing the version that uses the parallel_for algorithm, you'll be able to see the non-sequential nature of the operation, with various rows in the image being displayed at different times. On my computer, it seemed to be slightly faster than the version using the parallel_invoke algorithm.
The combinable class template is designed to help you with shared resources that can be segmented into thread-local variables and combined after the computation is complete. It offers advantages over using a mutex, like a critical_section object, in that you don't have to lock the shared resources and cause threads to wait. The way it works is that a combinable object can create duplicates of a shared resource, one for each thread that is to be executed in parallel. Each thread uses its own independent copy of the original shared resource. The only prerequisite is that you must be able to specify an operation that will combine the duplicates to form a single resource, once the parallel operation is complete. A very simple example of where combinable can help is a variable that is shared in a loop to accumulate a total. Consider the following fragment:
std::array<double, 100> values;
double sum(0.0);
for(size_t i = 0 ; i<values.size() ; ++i)
{
values[i] = (i+1)*(i+1);
sum += values[i];
}
std::cout << "Total = " << sum << std::endl;You cannot make this loop parallel without doing something about sum because it is accessed and updated on each iteration. Allowing concurrent threads to do this is likely to corrupt the value of the result. Here's how the combinable class can help you execute the loop in parallel:
Concurrency::combinable<double> sums; Concurrency::parallel_for(static_cast<size_t>(0), values.size() ,
[&values, &sums](size_t i)
{
values[i] = (i+1)*(i+1);
sums.local() += values[i];
});
double sum = sums.combine([](double lSum, double rSum)
{return lSum + rSum; });The combinable object, sums, can create a local variable of type double for each concurrent thread. The template argument specifies the type of variable. Each concurrent thread uses its own local variable of the type specified, which you access by calling the local() function for sums in the lambda expression.
Once the parallel_for loop has executed, you combine the local variables that are owned by sums by calling its combine() function. The argument is a lambda expression that defines how any two local variables are to be combined. The lambda expression must have two parameters that are both of the same type, T, as you used for the combinable template argument, or both of type const reference to T. The lambda must return the result of combining its two arguments. The combine() function will use the lambda expression as often as necessary to combine all the local variables that were created, and return the result. In our case, this will be the sum of all the elements of values.
The combinable class also defines the combine_each() member function for combining local results that have a void return type. The argument to this function should be a lambda expression or a function object with a single parameter of type T or type const T&. With this function, it is up to you to assemble the combined result. Here's how you would use it to combine the local results for the previous fragment:
double sum(0.0);
sums.combine_each([&sum](double localSum)
{ sum += localSum; });The lambda expression that is the argument to combine_each() will be called once for each local partial total owned by sums. Thus, you will accumulate the grand total in sum.
You can reuse a combinable object. To reset the value of the local variables for a combinable object, you just call its clear() function.
You can use a task_group class object to manage the parallel execution of two or more tasks, where a task may be defined by a functor or a lambda expression. A task_group object is thread-safe, so you can use it to initiate tasks from different threads. If you only want to initiate parallel tasks from a single thread, then a structured_task_group object will be more efficient.
To execute a task in another thread, you first create your task_group object; then you pass the function object or lambda expression that defines the task to the run() function for the object. Here's a fragment that shows how this works:
std::array<int, 50> odds;
std::array<int, 50> evens;
int n(0);
std::generate(odds.begin(), odds.end(), [&n] { return ++n*2 - 1; });
n = 0;
std::generate(evens.begin(), evens.end(), [&n] { return ++n*2; });
int oddSum(0), evenSum(0);
Concurrency::task_group taskGroup;taskGroup.run([&odds, &oddSum]
{ for(size_t i = 0 ; i<odds.size() ; ++i)
oddSum += odds[i];
});
for(size_t i = 0 ; i< evens.size() ; ++i)
evenSum += evens[i];
taskGroup.wait();The arrays odds and evens are initialized with sequential odd and even integers, respectively. The oddSum and evenSum variables are used to accumulate the sums of the elements in the two arrays. The first call to the run() function for the taskGroup object initiates the task specified by the lambda expression on a separate thread from the current thread — in other words, on a separate processor. The lambda expression sums the elements of the odds, and accumulates the result in oddSum. The for loop that follows sums the elements of the evens array and will execute concurrently with the task group lambda. Calling the wait() function for the taskGroup object suspends execution of the current thread until all tasks initiated by the taskGroup object — just one in our case — are complete.
Note how the current thread of execution can continue once a task group task has been initiated. The current thread will only pause execution when you call the wait() function for the task_group object. Of course, if you have more than two processors, you can use the task_group object to initiate more than one task to execute concurrently with the current thread.
A structured_task_group object can only be used to initiate tasks from a single thread. Unlike task_group objects, you cannot pass a lambda expression, or function object to the run() function, for a structured_task_group object. In this case, the argument specifying the task must be a task_handle object. task_handle is a class template where the type parameter is the type of the function object it encapsulates. It's easy to construct a task_handle object, though. Here's how the previous fragment can be coded to use the structured_task_group object to initiate a parallel task:
std::array<int, 50> odds;
std::array<int, 50> evens;
int n(0);
std::generate(odds.begin(), odds.end(), [&n] { return ++n*2 - 1; });
n = 0;
std::generate(evens.begin(), evens.end(), [&n] { return ++n*2; });
int oddSum(0), evenSum(0);
Concurrency::structured_task_group taskGroup;
auto oddsFun = [&odds, &oddSum]
{ for(size_t i = 0 ; i<odds.size() ; ++i)
oddSum += odds[i];
};
taskGroup.run(Concurrency::task_handle<decltype(oddsFun)>(oddsFun));
for(size_t i = 0 ; i< evens.size() ; ++i)
evenSum += evens [i];
taskGroup.wait();Here you create a function object, oddsFun, from a lambda expression. The auto keyword deduces the correct type for oddsFun from the lambda expression. The run() function for the taskGroup object requires the argument to be a task_handle object that encapsulates the task to be initiated. You create this by passing the oddsFun object as the argument, with the type argument for the task_handle template specified as the declared type of oddsFun. You use the decltype keyword to do this.
Note that the argument to the task_handle constructor must be a function object that has no parameters. Consequently, you cannot use a lambda expression here that requires arguments when it is executed. If you do need to use a lambda that requires parameters, you can usually wrap it in another lambda without parameters that calls your original lambda.
Another important consideration is that it is up to you to ensure that a task_handle object is not destroyed before the task associated with it has completed execution. This can come about if execution of the current thread, in which you create the task_handle object and initiated the parallel task execution, continues to a point where the destructor of the task_handle object is called, while the parallel task is still in progress.
In this chapter, you have learned the basic elements provided by the Parallel Patterns Library for programming to use multiple processors in an application. The PPL is effective only if you have a substantial compute-intensive task that will run on a machine with multiple processors, but such tasks can crop up quite often. Many engineering and scientific applications come into this category, as do many image-processing operations, and you can find large-scale commercial data-processing tasks that may benefit from using the PPL.
WHAT YOU LEARNED IN THIS CHAPTER
TOPIC | CONCEPT |
|---|---|
The | The |
The | The |
The | You use the |
The | You can use a |
The | You can use a |
The | You can use a |
High-resolution timers | You can use the |