The MPTL project

Authors

Current authors of the project are

  • Didier Baertschiger
  • Jonas Latt

What is the MPTL ?

MPTL stands for “MultiProcessing Template Library”, a name that hints both at the OpenMP standard and the STL. The MPTL proposes a programming model for writing thread-level parallel programs in C++. Within this model, the programmer can parallelize algorithms like those of the Standard Template Library (STL) in such a way that they are executed concurrently by different threads. The parallelization is transparent to the programmer, which means that he doesn't have to tackle any explicit thread-related code, nor even, in most cases, think about a strategy for how to parallelize a given algorithm. The syntax of a parallel code remains very similar to the one used in typical C++/STL programs.

The following example shows a conventional, sequential code that applies the function object calculation to each element of a container named data:

std::for_each(data.begin(), data.end(), calculation);

The parallel counterpart of this code is written as follows:

mptl::execute(mptl::for_each(data.begin(), data.end(), calculation));

The call to the algorithm std::for_each is replaced by the instantiation of an appropriate policy class through the convenience function mptl::for_each. The information contained in this class is used by the function mptl::execute to execute the algorithm std::for_each in parallel.

The function mptl::execute implements a data-parallel programming model that is designed in accordance with the principles of the STL, based on the container-algorithm-iterator abstraction. The basic idea is that all threads that are run in parallel execute exactly the same algorithm on the same container. However, the range spanned by the iterators data.begin() and data.end() is divided into subranges, and each thread gets a different pair of newly generated, appropriate iterators. One can therefore say that the parallelization takes place at the level of the iterators, and that both the containers and the algorithms remain unchanged – their source code must not even be accessible to the implementer of the parallel code.

The code uses a fork-join model of parallel execution. The program starts with a single process, the master thread, which executes sequentially. During the execution of the function mptl::execute though, a team of parallel threads is created that execute the code concurrently before synchronizing and terminating at the end of the algorithm call. This model is reminiscent of the widely used OpenMP API that offers a precompiler solution to thread-level parallelism in Fortran, C and C++ programs. Indeed, there are strong analogies between the parallelization of an STL algorithm and the execution of loop parallelization directives in OpenMP. However, the OpenMP directives must be written textually at the beginning of a loop construct. This is contradictory to the STL way of writing programs, where hand written loops are replaced by function calls. You might therefore find the MPTL way of approaching concurrency to be better adapted to the needs of modern C++ programming.

The number of threads to be used in a parallel section can be chosen through a call to the function mptl::setNumThreads. A call to this function has no immediate effect, but it modifies the behavior of mptl::execute and mptl::dynamicExecute subsequently. The currently active number of threads can be requested through the function mptl::getNumThreads.

The current version of the library includes

  • A general framework for parallelizing algorithms
  • A parallel version for more than 50% of all STL algorithms, including a parallel quicksort

A full example on how to use the parallel version of the STL algorithms here.

A full example on how to parallelize your own algorithms can be found here.

Download

The MPTL library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose. See the GNU Lesser General Public License for more details.

Download the current version of the library: mptl.zip

Download an extensive documentation (french only): mptl.pdf