There are several ways to get programmers to solve assigned tasks at high speed with a minimal number of errors.
The first way is to use high-level languages, for example, C++. Object-oriented programming makes it possible to create entities of various kinds in code, as well as define operations on them. As a result, we get at our disposal a set of certain objects that correspond to objects from the problem domain of the task being solved, with high-level properties and methods. Implementation details are hidden behind these high-level methods, which allows the programmer to focus on solving the task.
The second way is to use modern tools: compilers, test generators, formal verifiers, profilers. Compilers use internal optimizations to obtain better time characteristics and minimal memory costs. Examples of such optimizations include automatic pipelining, unrolling (rolling up), or parallelization of loops, which produces a faster implementation of the program. In this case, the compiler handles the routine programming tasks, and, as is well known, it works much faster and makes mistakes less often than the programmer.
The third way is to use methodological support. Numerous design methods and so-called patterns have been developed — approaches to solving one task or another in a certain context. Numerous books and manuals have been published, devoted both to programming as such, to solving abstract tasks, and also to application in specific tasks of the national economy.
The fourth way is to use libraries that contain ready-made, tested solutions: algorithms and data structures. Using library components, first, reduces development time, and second, reduces project testing time, because library components have been tested in advance and have repeatedly been introduced into industrial projects. Thus, the amount of library code can substantially exceed the amount of code written by the programmer.
Let’s do a brief overview of technologies that increase the productivity of programmers developing parallel applications. For many years the most accessible way of multithreaded programming was to use the Windows API or POSIX Threads library. The programmer had to solve the assigned tasks at a very low level. For example, the programmer needs to:
-
create and delete threads on their own;
-
determine the functions that should be executed in a thread;
-
pass the needed parameters into the thread;
-
use various functions to synchronize threads;
-
ensure an even load of the threads with computations;
-
take care of the scalability of the resulting solution.
Obviously, the drawback of this approach is that converting a sequential program into a parallel one can take a lot of time. The resulting solution will also be prone to many errors.
Some of these problems were successfully solved in the OpenMP library. This library is implemented as a set of functions and directives — special extensions to the compiler. The programmer applies one directive or another in the required place, and the compiler inserts calls to system functions at the specified place. For example, parallelizing a loop is done with a single directive to the compiler. In doing so, the compiler will take care of creating and synchronizing threads, dividing iterations among threads, and also of good load balancing. This approach makes it possible to solve a limited class of tasks practically without errors and in a short time.
But the OpenMP library has a number of limitations and drawbacks. We will indicate only some of them.
-
Loops with an unknown number of iterations cannot be parallelized.
-
Substantial limitations on loop parameters.
-
Limited possibilities for distributing work among threads.
-
The reduction operation is limited to eight elementary operations.
-
No more complex templates than a parallel loop or a parallel section.
Intel Threading Building Blocks (hereafter TBB) is a new library for multithreaded programming, developed by Intel. The library has a number of functions and classes for solving common tasks in parallel programming:
-
the parallel_for function for organizing a parallel loop;
-
the parallel_reduce function for a parallel loop with subsequent combination of partial results;
-
the parallel_while class for creating a parallel loop with an unknown number of iterations;
-
the pipeline class for organizing pipeline computations;
-
containers with parallel access capability: concurrent_vector, concurrent_queue, concurrent_hash_map.
TBB introduces the concept of a task object — a C++ class in which operator () is defined, which performs the assigned task (see the listing below). Depending on the algorithm in which the task object is used, this operator, for example, may take as a parameter a range of iterations (parallel_for, parallel_reduce) or the next element for processing (parallel_while, pipeline).
`// Класс-задача class Body { public: // Оператор-обработчик void operator() () { // Здесь расположены вычисления } };
* This source code was highlighted with Source Code Highlighter.`
Here you can see the difference from programming ordinary threads: the programmer creates tasks, not threads. During initialization, the TBB library creates the necessary number of threads, and the built-in scheduler assigns tasks to these threads while the program is running.
The template functions parallel_for and parallel_reduce work with ranges (iteration spaces). The TBB library provides two classes for this: blocked_range and bloced_range2d, one-dimensional and multidimensional space, respectively. TBB recursively divides the original range into many blocks, which are passed as parameters to the handler operator. Thus, each task object performs computations over its own portion of iterations. Let us give an example of using a one-dimensional range.
<span style="font-family:Courier New;font-size:85%;color:black;">blocked_range<<span style="color:#0000ff;">int</span>>(begin, end, grainsize)</span>
Here the template parameter is the type of the range elements, begin is the starting point, end is the ending point. The pair begin and end describes a half-open interval [begin, end); for example, the loop for (int i = 2; i < 5; i++) corresponds to the interval [2; 5) and includes iterations 2, 3, 4. The grainsize parameter determines the size of an indivisible block of iterations. In the event that, at the next stage of dividing the original range, a block smaller than grainsize is encountered, it will be considered indivisible. The figure below shows an example of recursive division of the range blocked_range
To conclude the article, let us give an example of parallelizing a for loop.
`#include “tbb/blocked_range.h”
include “tbb/parallel_for.h”
include “tbb/task_scheduler_init.h”
using namespace tbb;
///////////////////////////////////////////////////////////////////////////////
// Класс-задача class MyTask { public: // Метод-обработчик выполняет функцию Calculate для каждого элемента // блока итераций. void operator() (const blocked_range<int>& r) const { for (int i = r.begin(); i != r.end(); i++) Calculate(i); } };
///////////////////////////////////////////////////////////////////////////////
int main() { // Инициализация библиотеки ТББ task_scheduler_init init;
// Запуск шаблона parallel_for, который принимает два параметра: // * объект диапазона итераций [0, 1000000) // * объект-задачу parallel_for(blocked_range<int>(0, 1000000, 10000), MyTask);
return 0; }
///////////////////////////////////////////////////////////////////////////////
* This source code was highlighted with Source Code Highlighter.`