Changes

DPS921/Team team

11,682 bytes added, 16:38, 4 December 2020

no edit summary

== Intel Threading Building Blocks ==

=== Overview of TBB ===

Intel TBB is a library which provides features for parallel programming.It is used for task-based parallelism and requires no special compiler support. TBB has features such as Parallel Algorithms, memory allocation, threads and synchronization. Along side these features are similar features that were talked about in C++11. Naturally, TBB supports features such as containers and iterators, but with additional features to support the parallel nature of the library. Finally, TBB allows for generic programming which removes type requirements.

=== Containers ===

Containers within TBB allow for multiple threads to alter the same container at once. These containers are known as concurrent containers. Examples of these containers are:

<li>parallel_scan</li>

</ul>

=== Mutual Exclusion ===

A TBB mutex is created by access tbb::mutex from the <tbb/mutex.h> file. To lock a mutex you call tbb::mutex::lock() and to unlock, tbb::mutex::unlock(). Different mutexes in TBB have a combination of different flavors, or attributes. These attributes have tradeoffs depending on which one is chosen.

<ul>

<li>Scalable - Is a mutex that does not do worse than limiting one execution to a thread. It is generally slow.</li>

<li>Fair/Unfair: Allows for threads to move forward in the program in the order that they arrive. Unfair threads are potentially faster as they will allow for running threads to cut the line over threads that are waiting.</li>

<li>Recursive: Allows for a thread with a lock on the mutex to acquire another lock on the mutex.</li>

<li>Yield or Block: If there is a long wait, a decision will be made if progress can continue, and if it can then yield the processor. If it cannot be made it will block otherwise.</li>

</ul>

Taken from threadingbuildingblocks.org is a table displaying different mutexes and the flavors they possess.

<table summary="" id="tbl11" frame="border" rules="all" width="100%" cellspacing="0" cellpadding="4" border="1"><caption>Traits and Behaviors of Mutexes</caption>

<tr>

Mutex

</th>

Scalable

</th>

Fair

</th>

Recursive

</th>

Long Wait

</th>

Size

</th>

</tr>

<tr>

<samp class="codeph">mutex</samp>

</td>

OS dependent

</td>

OS dependent

</td>

no

</td>

blocks

</td>

≥ 3 words

</td>

</tr>

<tr>

<samp class="codeph">recursive_mutex</samp>

</td>

OS dependent

</td>

OS dependent

</td>

✓

</td>

blocks

</td>

≥ 3 words

</td>

</tr>

<tr>

<samp class="codeph">spin_mutex</samp>

</td>

no

</td>

no

</td>

no

</td>

yields

</td>

1 byte

</td>

</tr>

<tr>

<samp class="codeph">speculative_spin_mutex</samp>

</td>

HW dependent

</td>

no

</td>

no

</td>

yields

</td>

2 cache lines

</td>

</tr>

<tr>

<samp class="codeph">queuing_mutex</samp>

</td>

✓

</td>

✓

</td>

no

</td>

yields

</td>

1 word

</td>

</tr>

<tr>

<samp class="codeph">spin_rw_mutex</samp>

</td>

no

</td>

no

</td>

no

</td>

yields

</td>

1 word

</td>

</tr>

<tr>

<samp class="codeph">speculative_spin_rw_mutex</samp>

</td>

HW dependent

</td>

no

</td>

no

</td>

yields

</td>

3 cache lines

</td>

</tr>

<tr>

<samp class="codeph">queuing_rw_mutex</samp>

</td>

✓

</td>

✓

</td>

no

</td>

yields

</td>

1 word

</td>

</tr>

<tr>

<samp class="codeph">null_mutex</samp>

</td>

moot

</td>

✓

</td>

✓

</td>

never

</td>

empty

</td>

</tr>

<tr>

<samp class="codeph">null_rw_mutex</samp>

</td>

moot

</td>

✓

</td>

✓

</td>

never

</td>

empty

</td>

</tr>

</table>

Figure 2. https://www.threadingbuildingblocks.org/docs/help/tbb_userguide/Mutex_Flavors.html

=== Atomics ===

Virtually the same compared to the Standard Template library. An atomic variable is declared with atomic<Type> variableName. A thread can perform actions on the atomic variable without the need for locks. This is potentially quicker but comes with the downside of having less operations available to perform.

== What was added in C++17 STL ==

C++ 17 introduces parallel algorithms and execution policies, and the reduce, inclusive_scan, and exclusive_scan algorithms. This allows for true parallelization to occur, not multitasking. The execution policies that were created in C++17 are what allow for the distinction between running a program sequentially or in parallel.

The algorithms inclusive_scan and exclusive_scan do not require an execution_policy and can simply be called with arguments containing the an iterator pointing to the beginning of a container, and an iterator pointing to the end

== Case Studies between STL & TBB ==

Comparison of TBB parallel sort, STL sort

<pre>

Mvizl

18

edits

CDOT Wiki β

Changes

DPS921/Team team

CDOT Wiki ^β