Parallel STL

In this chapter, you will learn how to use the computer's graphical processing unit for computationally heavy tasks. We will use the excellent Boost Compute library, which exposes the GPU via an interface that resembles the STL, meaning that you will move your standard C++ code almost seamlessly from the CPU to the GPU.

This chapter is not going to go in depth into theories of parallelizing algorithms or parallel programming in general, as these subjects are far too complex to cover in a single chapter. Also, there is a multitude of books on this subject. Instead, this chapter is going to take a more practical approach and demonstrate how to extend a current C++ code base to utilize parallelism while preserving the readability of the code base.

In other words, we do not want the parallelism to get in the way of readability; rather, we want the parallelism to...

Importance of parallelism

From a programmer's perspective, it would have been very convenient if the computer hardware of today had been a 100 GHz single core CPU rather than a three gigahertz multi-core CPU, and we wouldn't need to care about parallelism. But, as the evolution of computer hardware is going in the direction of multi-core CPUs, programmers have to use efficient parallel patterns in order to make the most out of the hardware.

Parallel algorithms

As mentioned in Chapter 10, Concurrency, with parallelism we refer to programming that takes advantage of hardware with multiple cores. It makes no sense to parallelize algorithms if the hardware does not provide any of the benefits of it.

Therefore, a parallel algorithm equivalent of a sequential algorithm is algorithmically slower than the sequential. Its benefits come from the ability to spread the algorithms onto several processing units.

With that in mind, it's also notable that not all algorithms gain the same performance increase when run in parallel. As a simple measurement of how well an algorithm scales, we can measure:

• A: The time it takes to execute sequentially at one CPU core
• B: The time it takes to execute in parallel, multiplied by the number of cores

If A and B are equal, the algorithm parallelizes perfectly, and the larger B is compared...

Parallel STL

As of C++17, the STL library has been extended with parallel versions of most, but not all, algorithms. Changing your algorithms to execute in parallel is only a matter of adding a parameter that tells the algorithm which parallel execution policy to use.

As stressed earlier in this book, if your code base is based upon STL algorithms, or at least if you have the habit of writing C++ by using algorithms, you get an instant performance boost almost for free by adding an execution policy where suitable.

auto roller_coasters = std::vector<std::string>{ 
  "woody", "steely", "loopy", "upside_down" 
}; 

Sequential version	Parallel version
auto loopy_coaster = *std::find( roller_coasters.begin(), roller_coasters.end(), "loopy" );	auto loopy_coaster = *std::find( std::execution::par, roller_coasters...

Executing STL algorithms on the GPU

Graphics processing units, or GPUs, were originally designed and used for processing points and pixels for computer graphics rendering. Briefly, what the GPUs did was to retrieve a buffer of pixel data or vertex data, perform a simple operation on each one of them individually, and store the result in a new buffer (to eventually be displayed).

GPU APIs and parallel operations

The main API for programming the GPU is OpenGL, although similar functionality is available in DirectX as well.

Here are some examples of simple, independent operations that could be executed on the GPU at an early stage:

• Transform a point from world coordinates to screen coordinates.
• Perform a lighting calculation...

Boost Compute

In this book, we have chosen Boost Compute (written by Kyle Lutz) as the library for accessing the GPU. The reasons we picked Boost Compute are that it is very well written, vendor independent, and contains almost all STL algorithms. On top of that, it is a part of Boost, one of the most widely used C++ library.

Throughout this section we will keep a steady focus on the syntactic similarities between Boost Compute and STL algorithms, therefore many Boost Compute code examples will be presented side by side with its equivalent STL algorithm implementation.

Basic concepts of Boost Compute

Boost Compute has a few basic concepts, which are good to grasp before going further:

• Device, the equivalent of the actual...