Team Darth Vector
TEAM, use this for formatting. Wiki Editing Cheat Sheet
Join me, and together we can fork the problem as master and thread
Members
Alistair Godwin
Giorgi Osadze
Leonel Jara
TBB Background
Containers Comparison
List of TBB containers:
concurrent_queue : Multiple threads may simultaneously push and pop elements from the queue.
concurrent_vector :
concurrent_hash_map : hash table that permits concurrent accesses.
quotes: Intel Threaded Building Blocks book. Highly concurrent containers are very important because Standard Template Library (STL) containers generally are not concurrency-friendly, and attempts to modify them concurrently can easily corrupt the containers.
Algorithms
parallel_for
parallel_scan
parallel_reduce
Threads
STL Background
Containers Comparison
pair,vector,list,slist,
Algorithms
TBB Threads
Lock Convoying Problem
What is a Lock?
Quick background on mutex/lock
Parallelism Problems in STL
Put a picture and maybe some code here
Lock Convoying in TBB
Put another picture here
Study Ref: https://software.intel.com/en-us/blogs/2008/10/20/tbb-containers-vs-stl-performance-in-the-multi-core-age This leads into Concurrent_vector growing below..
Efficiency Comparison Parallel for and concurrent_vector
If only you knew the power of the Building Blocks
Concept: Fine-grained locking
Multiple threads operate on the container by locking only those portions they really need to lock.
Concept: Lock-free algorithms
Bits of knowledge:
STL interfaces are inherently not thread-safe.
Threading Building Blocks containers are not templated with an allocator argument.
Links
http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-summary.html
http://www.cplusplus.com/reference/stl/
https://www.inf.ed.ac.uk/teaching/courses/ppls/TBBtutorial.pdf
Code Implementation Comparison for STL and TBB
| COLUMN1 | COLUMN2 |
|---|---|
| ROW1 | ROW1/COL2 |
| ROW2 | ROW2/COL2 |
Parallel Algorithms support
C++11 STL does not have much to offer for parallel algorithms natively unlike TBB
Though there are new algorithms for parallelism in the C++17 standard
More: http://www.bfilipek.com/2017/08/cpp17-details-parallel.html
Resource management
Overall partitioning, thread creation, and management is hidden in TBB
Thread Creation, terminating, and synchronizing is handled by TBB
The thread creation and overall resource for STL is managed by a combination of libraries;
-thread for creation and joining
-mutex for mutual exclusion and locks
-future for accessing results of asynchronous operations
Details: http://en.cppreference.com/w/cpp/thread
Implementation Safety
TBB specifically makes concurrent vector not to support insert and erase operations. Only new items can only be pushed back, and cannot be shrunk;
-This prevents devs to write bad code
-Allowing this could cause a mistake on implementing parallel code. Which will cause a big performance hit, burdening both iterating and growing operations. Which will make the concurrent containers in TBB unless due to this risk.
Note for TBB (to trash less on STL)
-Some operations in TBB containers are not thread safe, like reserve() and clear() in concurrent vector.
-Complexity on concurrent containers is higher compared to STL. For layouts and implementation. This due to the nature of running in parallel and how TBB implements it.