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

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.