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

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

Coding Time 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