-
Notifications
You must be signed in to change notification settings - Fork 1.4k
Concurrency in CGAL
- Which library?
- License
- Guidelines for developers
- Changes in the CMake process
- Which mechanism to enable or disable parallelism
- Advanced TBB configuration
Intel TBB is the library which is used for parallel programming in CGAL. It provides thread support, atomic operations, task-based parallelism support, concurrent containers and high-level tools (scalable memory allocators, parallel sorts, etc.).
Intel TBB is designed and optimized for task-based programming. Several layers are available.
- For simple cases, it provides a high-level API (
parallel_for
,parallel_do
, etc.). - For more complex cases, the developer has access to tasks and can control the task-scheduler behavior.
- And if the user wants even more control, threads can be created and managed "by hand".
If one combines several algorithms/packages which use Intel TBB for task-based programming, the number of threads used by each component is automatically adjusted so that the total number of threads matches the number of available hardware threads.
As a result, we strongly suggest that developers use Intel TBB instead of any other library, at least for thread-related features. For other features such as atomics, thread-local storage or locks, C++11 could be used as an alternative in the future when CGAL officially supports C++11, since it can be safely mixed with Intel TBB. Note that Intel TBB's API is very close to C++11 for those features.
Nevertheless, if one needs another library for a good reason, we don't strictly forbid it as long as it is thoroughly documented and as long as it provides control on the number of threads used. But the developer must know that, doing so, it prevents its algorithm to be easily nested/mixed with other parallel algorithms. For this reason, this choice will have to appear and to be justified in the feature submission, and the reviewers are allowed to challenge it.
TBB is dual-licensed: Apache v2.0 with the libstdC++ Runtime Exception or commercial COM license (see here and here).
For developers who are new to TBB, we recommend to visit the TBB documentation page and read:
- User guide: learn how to use Intel TBB, with examples and code samples. It goes through the main features of TBB. A must-read.
- Design Patterns: a cookbook of common parallel design patterns and how to implement them in TBB. You will probably find here a useful recipe to get inspiration.
- Reference Manual.
- And don’t forget the codes samples which come with TBB.
Here is a quick checklist of TBB key features that a developer should know:
- High-level TBB mechanisms (parallel_for, parallel_do)
- Parallel containers (concurrent_vector, concurrent_queue...), with a special attention to operations which are concurrently callable (e.g. concurrent_vector::push_back) and operations which are not (e.g. concurrent_vector::clear)
- Mutual exclusion (different kind of mutexes) and its pathologies (e.g. deadlocks).
- [More advanced] Atomics, TBB task-scheduler
Note that TBB provides concurrency-optimized allocators. We advice the developers to try them.
In order to easily link with TBB, we provide a FindTBB CMake module.
Thus, the developer of a demo/example/test using parallel code needs to
add the following lines after include(${CGAL_USE_FILE})
in the
CMakeLists.txt
file:
# Activate concurrency?
option(ACTIVATE_CONCURRENCY
"Enable concurrency"
ON)
if( ACTIVATE_CONCURRENCY )
find_package( TBB REQUIRED )
if( TBB_FOUND )
include(${TBB_USE_FILE})
target_link_libraries(the_target ${TBB_LIBRARIES})
endif()
endif()
Note: If you are using create_single_source_cgal_program
, replace
the target_link_libraries
call by:
list(APPEND CGAL_3RD_PARTY_LIBRARIES ${TBB_LIBRARIES})
Remarks:
- External users using headers with concurrency-enabled code also have to ensure to give the right parameters to the compiler.
- In case we go for CTest, tests there can have properties: PROCESSORS and RUN_SERIAL, which should be set when testing parallelized code.
When CMake finds TBB and links it to the program, the
CGAL_LINKED_WITH_TBB
macro is defined. To use the parallel version of
an algorithm, two conditions must be fulfilled:
-
CGAL_LINKED_WITH_TBB
is defined - The user requests the parallel version (see below to know how)
If one of these conditions is not true, the package must automatically fall back on the sequential version.
Note that we need to keep a sequential version (i.e. we don't want to rely on TBB to automatically fall back on a sequential version) for several reasons:
- One should be able to build CGAL without TBB installed
- We don't want a hard dependency to TBB
- The automatic TBB fallback won't probably be as fast as a true sequential code (but you may not notice the difference)
Tag dispatching must be used to allow the user to enable/disable concurrency. Compared to macros (#ifdef), it allows to use sequential and parallel versions in the same application. Several techniques are available for this, and the developer can choose whatever is best in his case:
- Tag dispatching by Type or by Instance.
- Non-type template parameters (
bool
,enum
…)
In <CGAL/tags.h>
, two tags are defined: Sequential_tag and
Parallel_tag.
struct Sequential_tag {};
struct Parallel_tag : public Sequential_tag {};
The developers should use them (and no other custom tag) in order to keep a good consistency among packages.
Here are a few code samples showing different ways to use tag
dispatching. These examples are just here as a "quick-start guide" and
are not exhaustive, there may be more complex scenarii involving tag
dispatching. Please note that we combine "#ifdef CGAL_LINKED_WITH_TBB
"
and tag dispatching to test both conditions. As long as
CGAL_LINKED_WITH_TBB
is defined, both sequential and parallel versions
can be used in the same program, depending on the tag used.
By Type
// Default: sequential
template <typename Concurrency_tag = Sequential_tag >
class Foo
{
public:
void Bar() { std::cout << "Hello sequential world" << std::endl; }
};
#ifdef CGAL_LINKED_WITH_TBB
// Parallel
template <>
class Foo<Parallel_tag>
{
public:
void Bar() { std::cout << "Hello parallel world" << std::endl; }
};
#endif // CGAL_LINKED_WITH_TBB
int main(void)
{
Foo<> f1; // Sequential_tag is used by default
Foo<Parallel_tag> f2;
f1.Bar(); // Calls the sequential version
f2.Bar(); // Calls the parallel version
return 0;
}
Note: If the developer is using custom tags inherited from Parallel_tag, he must provide one specialization by tag.
By Instance
// Default: sequential
template <typename Concurrency_tag = Sequential_tag >
class Foo
{
protected:
void Bar_dispatch(Sequential_tag)
{
std::cout << "Hello sequential world" << std::endl;
}
#ifdef CGAL_LINKED_WITH_TBB
void Bar_dispatch(Parallel_tag)
{
std::cout << "Hello parallel world" << std::endl;
}
#endif //CGAL_LINKED_WITH_TBB
public:
void Bar()
{
#ifdef CGAL_LINKED_WITH_TBB
Bar_dispatch(Concurrency_tag());
#else //!CGAL_LINKED_WITH_TBB
// If TBB is not available, we fall back on the sequential function
Bar_dispatch(Sequential_tag());
#endif //CGAL_LINKED_WITH_TBB
}
};
int main(void)
{
Foo<> f1; // Sequential_tag is used by default
Foo<Parallel_tag> f2;
f1.Bar(); // Calls the sequential version
f2.Bar(); // Calls the parallel version
return 0;
}
Using is_convertible
Note that it makes it possible to have some inheritance amongst tags.
// Default: sequential
template <typename Concurrency_tag = Sequential_tag>
class Foo
{
public:
void Bar()
{
#ifdef CGAL_LINKED_WITH_TBB
// Parallel
if (boost::is_convertible<Concurrency_tag, Parallel_tag>::value)
{
std::cout << "Hello parallel world" << std::endl;
}
// Sequential
else
#endif // CGAL_LINKED_WITH_TBB
{
std::cout << "Hello sequential world" << std::endl;
}
}
};
int main(void)
{
Foo<> f1; // Sequential_tag is used by default
Foo<Parallel_tag> f2;
f1.Bar(); // Calls the sequential version
f2.Bar(); // Calls the parallel version
return 0;
}
Using non-type template parameters
// Default: sequential
template <bool Is_parallel = false>
class Foo
{
public:
void Bar()
{
#ifdef CGAL_LINKED_WITH_TBB
// Parallel
if (Is_parallel)
{
std::cout << "Hello parallel world" << std::endl;
}
// Sequential
else
#endif // CGAL_LINKED_WITH_TBB
{
std::cout << "Hello sequential world" << std::endl;
}
}
};
int main(void)
{
Foo<> f1; // Is_parallel = false by default
Foo<true> f2;
f1.Bar(); // Calls the sequential version
f2.Bar(); // Calls the parallel version
return 0;
}
Note: this is for internal use only. Documented classes must use Sequential_tag/Parallel_tag.
Of course, more advanced techniques may be used – e.g.: specialized base classes to provide different member variables.
An advanced user may want to specify the number of threads used by TBB.
This control is provided by the tbb::task_scheduler_init
class.
TBB automatically creates a task scheduler the first time that a thread
uses task scheduling services and destroys it when the last such thread
exits. Instead, an instance of task_scheduler_init might be manually
created by the user to control, among other things, the number of
threads used by the task scheduler. Here is an example:
{
tbb::task_scheduler_init tsi(6); // 6 threads
run_parallel_algo1(); // Uses 6 threads
}
{
tbb::task_scheduler_init tsi(12); // 12 threads
run_parallel_algo2(); // Uses 12 threads
}
See Intel documentation for more information.
General Information
- Information for New Developers
- Developing with Git
- Structure of a CGAL Package
- Building
- Concurrency in CGAL
- License
- Documentation Guidelines
- Reviewing Process
- Testing
- Miscellaneous
- Tools
- Scripts
- Libraries
- Infrastructure
- Releases
- Miscellaneous