Parallel Computing - Midterms - Crash Course

Atomic

A C++ feature that ensures safe access to shared data in multi-threaded programs without using locks.

Atomic Operations

Operations that complete without interruption, preventing race conditions.

std::atomic

Guarantees atomicity for individual operations, not for sequences of operations.

std::atomic

Many atomic operations are lock-free, meaning they don't use mutexes and are faster.

Mutex

Stands for mutual exclusion.

Mutex

Ensures that only one thread can access a critical section at any one time.

Mutex

A synchronization primitive used to protect shared data from being accessed simultaneously by multiple threads.

std::mutex

Helps prevent data races and ensures data consistency.

lock()

Blocks the calling thread until it successfully locks the mutex.

unlock()

Releases the mutex, allowing other threads to acquire it.

try_lock()

Attempts to lock the mutex without blocking.

try_lock()

Returns true if successful, false otherwise.

std::lock_guard

An elegant way to manage mutexes and ensure that they are properly locked and unlocked.

std::lock_guard

Prevents potential deadlocks and race conditions.

std::lock_guard

Locks the mtx mutex when the guard object is created.

std::lock_guard

Automatically unlocks the mutex when the guard object goes out of scope.

Conditional Variables

Used for thread synchronization, allowing threads to wait until a particular condition is met.

Conditional Variables

Part of the library in C++.

cv.notify_one()

Notifies one waiting thread.

cv.wait(lock)

Waits until a condition is met and the lock can be acquired.

Reentrant Lock

A mutex that can be locked multiple times by the same thread.

Reentrant Lock

Keeps track of how many times it's been locked by the owning thread.

Reentrant Lock

Must be unlocked an equal number of times before another thread can lock it.

Reentrant Lock

Can be useful when a program needs to lock a mutex multiple times before unlocking it.

Reentrant Lock

Using a mutex that can prevent deadlocks that occur when a thread tries to lock a mutex it already holds.

Reentrant Lock

If not unlocked the same number of times it was locked, it can still lead to being stuck.

Reentrant Lock

Useful for recursive functions that lock a mutex.

Recursive Mutex

Another term for a reentrant mutex or recursive lock.

std::recursive_mutex

Allows the same thread to acquire the lock multiple times without causing a deadlock.

Try Lock

A non-blocking version of the lock or acquire method.

Try Lock

Returns immediately, indicating if the lock was acquired.

Try Lock

Returns TRUE if the mutex is available and locked.

Try Lock

Returns FALSE if the mutex is already possessed by another thread.

try_lock()

(C++ specific) Attempts to acquire a lock without blocking.

try_lock()

(C++ specific) Returns false immediately if the lock is already acquired by another thread.

Read-write Lock

A synchronization primitive that allows multiple threads to read a shared resource simultaneously or one thread to write exclusively.

Read-write Lock

Can be locked in shared read mode (multiple readers) or exclusive write mode (single writer).

Read-write Lock

Useful when there are many more reader threads than writer threads.

std::shared_mutex

Allows multiple threads to read from a shared resource simultaneously while ensuring exclusive access for writing.

Liveness

A set of properties that require concurrent programs to make progress.

Liveness

Guarantees that all processes will eventually make progress in a well-written program.

Deadlock

A situation where each member of a group is waiting for some other member to take action, resulting in no progress.

Deadlock

Can occur if a thread tries to lock a mutex it has already locked (if it's not a reentrant mutex).

Dining Philosophers Problem

A classic example illustrating synchronization issues with multiple threads and locks.

Abandoned Lock

Occurs when a thread acquires a lock and terminates unexpectedly without releasing it.

Starvation

Occurs when a thread is unable to gain access to a necessary resource and cannot make progress.

Starvation

Can be caused by higher priority threads being scheduled more often.

Starvation

Can be caused by having too many concurrent threads.

Livelock

Similar to deadlock, but threads are actively trying to resolve the problem, yet still make no progress.

Livelock

Can occur when threads are designed to respond to each other's actions.

Livelock

Often caused by algorithms intended to detect and recover from deadlock.

Concurrency

When multiple tasks can run in overlapping time periods.

Concurrency

An illusion of parallel execution due to fast CPU switching (on a single core).

Parallelism

When tasks actually run in parallel on multiple CPUs or cores.

Sequential Computing

Tasks are executed one after another, without overlapping time periods.

Flynn's Taxonomy

A classification of computer architectures based on instruction and data streams.

SISD (Single Instruction, Single Data)

A uniprocessor machine executing a single instruction on a single data stream.

SISD

Machine instructions are processed sequentially.

SIMD (Single Instruction, Multiple Data)

A multiprocessor machine executing the same instruction on all CPUs but operating on different data streams.

SIMD

Well suited for scientific computing involving vector and matrix operations.

MISD (Multiple Instruction, Single Data)

A multiprocessor machine executing different instructions on different PEs, but all operating on the same dataset.

MIMD (Multiple Instruction, Multiple Data)

A multiprocessor machine capable of executing multiple instructions on multiple data sets.

MIMD

Each PE has separate instruction and data streams.

MIMD

PEs work asynchronously.

Shared-memory MIMD

All PEs are connected to a single global memory.

Distributed-memory MIMD

All PEs have a local memory.

Amdahl's Law

States that the theoretical speedup of a program is determined by the fraction of code that can be parallelized.

Amdahl's Law

Demonstrates that the potential for speeding up a program using parallel computing is limited by its sequential parts.

Process

An instance of a running program.

Process

Has a separate memory address space and runs independently.

Thread

The unit of execution within a process.

Thread

A process can have one or many threads.

Multithreaded Processes

Processes containing more than one thread, accomplishing multiple tasks concurrently.

Race Condition

An undesirable situation when a device or system attempts to perform two or more operations at the same time that must be done in a proper sequence.

Producer-Consumer Problem

A classic synchronization problem where one or more producers generate data that is consumed by one or more consumers.

thread

C++ header for thread support.

std::thread

C++ class that manages a separate thread.

std::jthread

C++20 thread class with support for auto-joining and cancellation.

this_thread::get_id()

Returns the thread ID of the current thread.

this_thread::sleep_for()

Stops the execution of the current thread for a specified duration.

this_thread::sleep_until()

Stops the execution of the current thread until a specified time point.

join()

Waits for a thread to finish its execution.

detach()

Permits a thread to execute independently from the thread handle.