Embarrassingly parallel solutions

Calculating the Mandelbrot set (which I covered in my previous post) lends itself to parallel processing. The value for each pixel is not dependant on the value of other pixels, and is controlled by the iterative algorithm with a few parameters that are common to all pixels right from the start. This type of parallelism is called embarassingly parallel processing, not because it is embarrasing per se, but it is just really easy to work with. The main object is to try not to introduce dependencies between the individual parts when converting the calculations from sequential mode to parallel mode. An example will pop up in the following.

Javidx9’s main object in his youtube video that started my path into rediscovering the Mandelbrot Set and Pixel Graphics was exactly to investigate how to utilize the multiple cores of a modern PC to speed up calculations for the Mandelbrot Set.

Below is the code again for the central piece of the calculations from the sequential version, which is also present in the code for this post for comparison.

double worldY = worldTopLeft.y;
for (int y = 0; y < ScreenHeight(); y++)
{
	double worldX = worldTopLeft.x;
	for (int x = 0; x < ScreenWidth(); x++)
	{
		int count = MandelbrotCount(worldX, worldY);
		olc::Pixel currPix;
		if (count >= maxCount)
			currPix = olc::BLACK;
		else
		{
			float angle = 2 * pi * count / maxCount;
			currPix = olc::PixelF(0.5f * sin(angle) + 0.5f, 0.5f * sin(angle + 2*pithird) + 0.5f, 0.5f * sin(angle + 4 * pithird) + 0.5f);
		}

		Draw(x, y, currPix);
		worldX += xStep;
	}
	worldY += yStep;
}

The first parallel implementation I will discuss is based on the OpenMP framework. The MP stands for Multi Processing. It is an initiative that started in 1997 and really took off around 2000. It is available for C, C++ and Fortran, and integrates itself in those languages with #pragma constructs, which are code lines that can tell a compiler or a pre-compiler to do special stuff that is outside the standard language of the compiler. This approach demands very little extra from the programmer to use it, as long as the chosen compiler supports it. MSVC has supported it since Visual C++ 2005 and gcc since 4.2.

Here is the central piece of code for calculating the Mandelbrot, letting the OpenMP framework decide how to distribute the calculations on the available cores on the PC.

#pragma omp parallel
#pragma omp for schedule(dynamic, 1) nowait
for (int y = 0; y < ScreenHeight(); y++)
{
	double worldY = worldTopLeft.y + y * yStep;
	double worldX = worldTopLeft.x;
	for (int x = 0; x < ScreenWidth(); x++)
	{
		int count = MandelbrotCount(worldX, worldY);
		olc::Pixel currPix;
		if (count >= maxCount)
			currPix = olc::BLACK;
		else
		{
			float angle = 2 * pi * count / maxCount;
			currPix = olc::PixelF(0.5f * sin(angle) + 0.5f, 0.5f * sin(angle + 2 * pithird) + 0.5f, 0.5f * sin(angle + 4 * pithird) + 0.5f);
		}

		Draw(x, y, currPix);
		worldX += xStep;
	}
}

Line 1 and 2 were the only things that had to be added to gain access to automatic parallelization of the algorithm. And of course the correct compiler switches and libraries as explained for each compiler at the end of this post.

But one other change had to be made: the worldY variable had to be moved inside the loop body for each iteration – because in the original single thread the worldY value was stored in a single variable, as only one value of y at a time was using it. When many different values of y will have its loop body run in parallel, they each need their own copy of the corresponding worldY value in the Mandelbrot x-y world. Line 1 and 20 in the sequential calculation became Line 5 in the parallel calculation, costing a multiplication instead of a simple addition. Since this is only done once for each value of y, it is a very small overhead. This is an example of your responsibility to make each step in the loop independent from the others.

You must also be sure that all functions you call in a loop step are thread safe. MandelbrotCount is a very simple function working on only its parameters and local variables, and is fully under my control. The sin function is thread-safe if you use the right C++ library. And fortunately the PGE function Draw(x, y, currPix) is thread safe if x and y are not the same pixel. Since the full source code of the PGE is available in the include file olcPixelGameEngine.h (see my previous post here), you can make sure that is the case.

Line 2 tells OpenMP to use the full parallelism obtainable on your platform: run as many single y values concurrently as feasible, and don’t wait for the other values to finish, before scheduling the calculation for a new value in parallel.

OpenMP is supported in all compilers I have been working with: MSVC, clang and MinGW64 on Windows; gcc and clang on Linux.

Timings for the different compilers and parallelization methods can be seen in the table below after all the methods have been described.

The main advantage for many years of OpenMP has been that it is portable to a very high degree between compilers and platforms. Not until the standard C++17 did C++ have native support (in the language or in STL) for high level parallelism. So before C++17 you had to rely on OpenMP, your own implementation using C++ threads (as in Javidx9’s Parallel Mandelbrot project) or various non-portable libraries to obtain it.

But with C++17 and the corresponding standard libraries this changed. If your compiler supports C++17 you have it! Here is the code:

std::for_each(std::execution::par, indices.begin(), indices.end(),
	[&](size_t y)
	{
		double worldY = worldTopLeft.y + y * yStep;
		double worldX = worldTopLeft.x;
		for (int x = 0; x < ScreenWidth(); x++)
		{
			int count = MandelbrotCount(worldX, worldY);
			olc::Pixel currPix;
			if (count >= maxCount)
				currPix = olc::BLACK;
			else
			{
				float angle = 2 * pi * count / maxCount;
				currPix = olc::PixelF(0.5f * sin(angle) + 0.5f, 0.5f * sin(angle + 2 * pithird) + 0.5f, 0.5f * sin(angle + 4 * pithird) + 0.5f);
			}

			Draw(x, y, currPix);
			worldX += xStep;
		}
	}
);

Lines 1 and 2 contains 2 C++ features that came with C++17 and C++11.

The algorithm std::for_each existed before C++17 (and even C++11) as a way to apply a function to all the elements of an STL container, nothing new here. But the first parameter std::execution::par is a kind of tag or flag as an instruction to the algorithm, to handle this with as much parallelism as possible.

The last parameter to the algorithm is a function with code to apply on each member of the container. Functions as objects existed before C++11 (you could already overload the function call operator () for objects), but defining them anonymously on the fly with a lambda expression was new.

The start of the lambda expression is the [] pair, in which you can specify how the variables of the surrounding scope are accessed. I have chosen to access them by reference, using [&]. Again, it is your responsibility to make sure you are not changing any of those, as they will be common for all the parallel threads. The lines 2-21 defines the function to call for each of the elements in container, and as you can see, it is exactly the same code as each step in the loop from the previous methods, working on one y value.

But where do these y values come from in this case? Well, before C++20, for_each needed the start and end point iterators for a container, so I had to define one, filled with all the y values I needed:

std::vector<size_t> indices(ScreenHeight());
std::iota(indices.begin(), indices.end(), 0);

I haven’t investigated it fully, but from C++20 concepts as ranges and views probably makes it possible to construct a lazy iota range of the y values, much in the same style as Python ranges. (Check cppreference.com on this for yourself).

This was the first time I was using C++17 parallellism, and to my joy it worked really well, in spite of the akward setting up of the range. The timing can be seen in the table below. There was a caveat for MinGW64 and gcc, though, as described at the end of this post.

Intel has offered their own C/C++ compiler for many years, with optimization targetted at their own CPUs.

The Intel compiler and library system has demanded a license fee for the use of them, and I could only sit there and look with envy on the wonderful Threading Building Blocks (TBB) library contained in that bundle. For my hobby programming, it was out of my reach.

Fortunately the compiler and libraries are now available for free as open source software (check the license conditions, if you are going to make a commercial product with them).

The parallelism features are part of TBB, and they are very easy to use. The library is written in standard C++11 and can be used by any compiler, it doesn’t need Intel’s compiler nor Intel CPUs. It is also available on Linux, compiled with gcc. It can now also run on AMD CPUs.

Here is the code to use it:

tbb::parallel_for(0, ScreenHeight(),
	[&](size_t y)
	{
		double worldY = worldTopLeft.y + y * yStep;
		double worldX = worldTopLeft.x;
		for (int x = 0; x < ScreenWidth(); x++)
		{
			int count = MandelbrotCount(worldX, worldY);
			olc::Pixel currPix;
			if (count >= maxCount)
				currPix = olc::BLACK;
			else
			{
				float angle = 2 * pi * count / maxCount;
				// Palette based on @Eriksonn's calculation, see my post and OneLoneCoder Discord channel
				currPix = olc::PixelF(0.5f * sin(angle) + 0.5f, 0.5f * sin(angle + 2 * pithird) + 0.5f, 0.5f * sin(angle + 4 * pithird) + 0.5f);
			}
			Draw(x, y, currPix);
			worldX += xStep;
		}
	}
);

The format for this is somewhere in between that of OpenMP and that of native C++17 parallelism. The for statement is replaced by the parallel_for function call, and the start and end values are visible as the first and second parameters, but the function to run is again in the form of a function object with one parameter, created with a lambda expression. Otherwise the core code is exactly the same as the previous 2 parallel methods.

TBB can run with all the compilers I have used on both Windows and Linux, including MSVC on Windows. How to set up and use TBB is described at the end of this post. It worked really well, see timing in the table below.

Via C# I found out about the Microsoft Task Parallel Library, and I discovered that similar features are available with MSVC in C++ as the Concurrency and Parallel libraries, I used for my first post. It is just as easy to use as Intel TBB.

I stumbled over a reference that Microsoft PPL is actually based on a license from Intels TBB, adding some more features and functionality. It is mentioned here. It makes sense, looking at the completely similar way a parallel_for is used:

concurrency::parallel_for(0, ScreenHeight(),
	[&](size_t y)
	{
		// This must have a separate copy for each possible thread
		double worldY = worldTopLeft.y + y * yStep;
		double worldX = worldTopLeft.x;
		for (int x = 0; x < ScreenWidth(); x++)
		{
			int count = MandelbrotCount(worldX, worldY);
			olc::Pixel currPix;
			if (count >= maxCount)
				currPix = olc::BLACK;
			else
			{
				float angle = 2 * pi * count / maxCount;
				// Palette based on @Eriksonn's calculation, see my post and OneLoneCoder Discord channel
				currPix = olc::PixelF(0.5f * sin(angle) + 0.5f, 0.5f * sin(angle + 2 * pithird) + 0.5f, 0.5f * sin(angle + 4 * pithird) + 0.5f);
			}

			Draw(x, y, currPix);
			worldX += xStep;
		}
	}
);

Since this is a Microsoft product, the timing table below doesn’t have values for PPL running on Linux – it’s simply not possible.

This is the full picture of the program. The Mandelbrot is calculated for a window of size 960 x 720, with a maximum iteration count of 256. Each calculated pixel is displayed as 1×1. The pallette used is the one invented by Ericsonn as described in my previous post.

At the top of the window different characteristics are displayed:

Namely: the current parallel method used, the compiler used for this instance of the program, the current mouse position in Mandelbrot world coordinates, the combined calculation and draw time in seconds and the current maximum iteration count. As always for PGE applications, the frames per second value is shown in the window title.

Using the normal keys from 1 to 5 will switch between the 5 different parallelism methods, including single thread. The maximum count can be increased/decreased by using the up and down arrow keys. Dragging with the middle mouse the view can be moved around, and using the scroll wheel, the view can be zoomed in and out. The R-key will reset the view. The Q- or Escape-key will exit the program.

Here are the timings using different methods with different compilers on different platforms. For each combination, a timing for the main calculation and a framerate has been measured and recorded.

The measurements were run on my computer #6 from this list of my computers. It’s a Ryzen 9 5950X based PC with 16 cores and hyperthreading, resulting in 32 parallel threads, which can dual boot into Windows 11 and Q4OS Linux.

A few observations:

On this platform, the Microsoft parallel library is not quite as good as the other 3 methods of obtaining parallellism.

That C++ parallel and oneTBB are exactly equal to each other for both minGW64 on Windows and gcc on Linux is explained further down in this post.

OpenMP doesn’t have quite as good a frame rate on Linux, even if the raw calculation times are similar to the other 2 methods. This could be caused by how handling of creating the parallel threads around the actual calculation is implemented on this platform.

I think some variation between other cases could also be explained by the same root-cause: how and when the overhead from creating and synchronising lots of threads is amortized over time.

Where did C++ take us this time

So on this excursion with C++ I was looking for some ways to easily exploit the parallel processing abilities of my computer.

I was pleased to learn that I have several methods to choose from and they are all relatively easy to use, as long as you know a bit about the dangers of parallel processing.

There may be other possibilities than the 4 libraries/methods I investigated, but they were the only I found that could easily make me implement a way to calculate this problem, which, as I described, is of the class Embarrassingly Parallel Algorithms.

The all have the advantage that they will automatically use all the processing cores of the current computer. I have tried it out on all of my computers in my computer park, without any changes to the code and they could all load the CPU up to 100%, giving me a speed up that matched the number of possible parallel threads on each of them.

Each of the 4 libraries/methods have further features that enable more advanced utilisation of tasks/threads, e.g. synchronised intercommunication between them that enables pipe lines of tasks, reduce/merge algorithms, or networks/graphs of communicating tasks/threads. They are not compatible with each other, so to use this kind of features, you must investigate what you need and what the individual libraries offer.

I used Microsoft PPL in my post about parallel algorithms for prime sieves to get exactly this intercommunication between tasks. It may be that one of the other libraries would be a better choice. It may also be that a simple parallel for would have sufficed for that problem. Feel free to investigate my code from that post, and see if you can find a solution along those lines – before I do it myself 🙂

To investigate further, here are a few links about each method.

For OpenMP, the documentation is here, and a good introduction is here. It is quite complete for building parallel applications.

For C++ the information is bit spread out on cppreference.com, threads/tasks are covered here, and specifics for parallel algorithms can be found here. For an introduction, I can recommend Bjarne Stroustrup’s book A Tour of C++, 3rd edition. As of C++17 the concurrency part is not as complete as the other 3 methods, mostly because interthread/intertask communication is at a lower abstraction level.

For oneTBB, the documentation can be found here. It is very complete for building parallel applications.

For Microsoft PPL, which is part of the big concurrency library, documentation can be found here. This library is only available on Windows (Arm, x86 and x64 based). It is very complete for building parallel applications, but not compatible with oneTBB and not portable to other platforms.

About the code

As usual the code is available in my github repository here.

It is arranged as a Visual Studio 2022 solution with 2 projects – one for single thread solution as covered in my previous post. And one for this solution using parallel processing.

In my previous post I mentioned the necessity of mapping to/from screen coordinates from/to world coordinates of the mathematical space where the Mandelbrot Set exists.

One advantage of the Pixel Game Engine is that it has a hook to add extensions, and in the eco-system surrounding PGE there are several of these available, some done by javidx9 himself, some by other enthusiasts.

One such is the Transformed View extension, which supports this transformation/mapping between screen and world coordinates, and as a bonus includes a method to zoom and move around in the world through mouse input, maintaining the mapping.

I won’t go into details about how to use the Transformed View, look in the code. Everywhere I refer to the member variable tv and call a method is where I use the Transformed View extention.

I will mention one more point, though. The mapping in the Transformed View extension is between 32 bit long int and 32 bit float values. Using 32 bit floating point values, which have about 6 decimal places of precision, has the disadvantage that there is a practical limit to how far in you can zoom in the Mandelbrot Set. Many interesting parts of the Mandelbrot Set are found at very high magnification. In the code for my previous post I implemented this transformation myself, using 64 bit double values, which have 13 decimal places of precision.

I have tried with 5 different combinations of compilers and OS’s, as seen in the table above. I will now give short instructions and observations about each of them, for each of the available methods.

Setting up your PC according to simple use of PGE can be found in the Wiki of Javidx9’s repository here. The most important thing is to make sure that the compiler is set to use C++17 features and libraries. That is the prerequisite for all the following instructions.

In the VS project directory you will find build scripts to build the application on the other platforms.

MSVC from Visual Studio (Windows)

For a standard installation of VS with the “Desktop Development with C++” workload, OpenMP, C++ parallel and Microsoft PPL is available right out of the box. Just make sure the C++17 or higher standard is set for the project.

Using OpenMP consist of inserting the correct #pragma omp directives in the correct positions as shown in the code above. Furthermore, the /openmp compiler switch should be set, either from VS or the command line.

To use C++17 parallel execution, the <algorithm> and <execution> library header files should be included. The elements you need are in the std:: namespace.

To use PPL insert #include <ppl.h> . The namespace to reach them is concurrency:: .

To use oneTBB from MSVC compiled programs, follow the instructions from Intel here. As part of the installation, it will try to install an extention for VS, which makes compiling and linking an application easier, as it will set up the proper include and library paths.

Once this is done, #include <tbb/tbb.h> should be inserted at the start of your source file. The namespace for oneTBB entry points is simply tbb:: .

To make my application actually use oneTBB with MSVC it is necessary to set a precompiler symbol like this:

#define USE_TBB_WITH_MSC 1

clang from Visual Studio (Windows)

The clang compiler and the LLVM toolset can be installed from the Visual Studio installation application by including two packages, use search “clang” under the Individual Components tab and check them, then install/modify.

Inside VS, it can be used by adding a new configuration for the current project using the Configuration Manager, copying from the MSVC Release configuration. Then select the new configuration from the drop down list in the toolbar, if it is not already selected. To make it a clang configuration then open the Properties for the project and on the Configuration Properties/General tab, change the Platform Toolset to “LLVM (clang-cl)” which should now be available.

Out of the box, after installing clang for VS as described, OpenMP, C++ Parallel and MS PPL are immediately available in the same way as for MSVC with a little addition. Apparantly Microsoft has made the clang toolset component compatible with MSVC, respecting special Microsoft features. Including the fact that the macro _MSC_VER is predefined when compiling with clang.

So follow the above instructions for C++ Parallel and MS PPL.

For OpenMP, instead add the -openmp compiler switch in the project Properties for the clang configuration on the C/C++ / Command Line tab in the field Additional Options. AND add libomp.lib on the Linker / Command Line tab in the field Additional Options.

The dynamic runtime library libomp.dll must be in a directory on the PATH of the system, or be present in the same directory as the executable.

For oneTBB, the clang tool set can use the same installation as MSVC. But to make it work, paths for include files and libraries must be set manually in the Project Properties, on the VC++ Directories tab. Insert the path to the oneTBB include files in the Include Directories list, using the <Edit…> dropdown function. On my PC it is

“C:\Program Files (x86)\Intel\oneAPI\tbb\2022.0\include”.

AND insert the path to the oneTBB libraries in the Library Directories in a similar way. On my PC it is

“C:\Program Files (x86)\Intel\oneAPI\tbb\2022.0\lib”

The dynamic runtime library tbb12.dll must be in a directory on the PATH of the system, or be present in the same directory as the executable.

MinGW64 (Windows)

MinGW64 makes the gcc compiler available under Windows. I use the UCRT variant of MinGW64 for best compatability and the most modern version of the Windows shared C/C++-supporting library.

Make sure you have installed the package mingw-w64-ucrt-x86_64-toolchain with pacman.

To use OpenMP all that is needed is to add the -fopenmp switch on the command line for the compiler g++.

Using C++17 parallel features with this compiler was not that easy. I implemented the C++ parallel code before the method using oneTBB, and was surprised that I neither got compiler nor linker warnings, but the C++17 parallel for_each behaved as a single thread implementation!

Only by accident did I find the explanation on cppreference.com, my preferred source for C++ details. It has a Compiler Support list for the various C++ standard versions, and under gcc in the C++17 library support list there is an asterisk (*) for “Parallel algorithms and execution policies”. Well hidden at the top of the page it explains that the asterisk means you should hover the mouse over the cell and get further information. So I did, and it states:

i.e. oneTBB must be linked with the program! Even if you’re not using oneTBB explicitly.

Using MinGW64 pacman I installed the mingw-w64-ucrt-x86_64-tbb package and added -ltbb12 to the command line. Currently this is version 12 of oneTBB.

And now it worked.

To use oneTBB was then already solved.

Using Microsoft PPL with this compiler is not possible.

The application can be built inside the MinGW64 environment using the MinGWBuild.sh script found in the project folder. It will build an executable file PgeMandelbrotParallel.exe in that folder.

This executable can run within the MinGW64 environment. To run outside, eg. on another Windows, since some of the libraries cannot be linked statically, the libraries libgcc_s_seh-1.dll, libgomp-1.dll, libstdc++-6.dll, libtbb12.dll and libwinpthread-1.dll from the MinGW64 installation must be present in a directory on the PATH of a system or in the same directory as the executable.

gcc (Linux)

Make sure the development packages with gcc and g++ and other prerequisties for PGE are installed.

To use OpenMP all that is needed is to add the -fopenmp switch on the command line for the compiler g++.

As explained above for MinGW64, oneTBB is required for the C++17 parallel algorithms to work. So install that on your Linux, and add -ltbb on the command line for g++. Installation on Linux normally will make sure this refers to the correct version.

The same steps enables usage of oneTBB.

Using Microsoft PPL on this platform is not possible.

The application can be built using the linuxBuild.sh script found in the project folder. It will build an executable file PgeMandelbrotParallel in that folder.

clang (Linux)

To use the clang/LLVM tool chain on Linux, it will of course have to be installed.

To use OpenMP add the -fopenmp and -lomp switches on the command line for clang++. This will enable OpenMP and link with the necessary clang library.

To use C++17 parallel algorithms clang needs oneTBB, so this must installed and linked, using the -ltbb command line switch.

To use oneTBB, oneTBB must be installed, and -lttb must be added to the command line

Using Microsoft PPL with this platform is not possible.

The application can be built using the clangBuild.sh script found in the project folder. It will build an executable file CLangPgeMandelbrotParallel in that folder.

Wrapping it up!

Pheeewww! That was a long post. And it has also taken a long time for me to release. But it does cover a lot of information that had to be pieced together from many sources. I hope this work is useful for you, my readers, in case you want to find smart ways to exploit you wonderful multi-core PC.

Have fun, try it, modify it, give comments and ask questions below!