parallel computing

What are the two main programming styles covered in the course?

Posix Threads and MPI style programming.

What is the significance of parallel computing in relation to microchip technology?

The number of transistors on microchips is expected to double every two years, making it essential for software developers to understand parallel computing.

What is a supercomputer?

The world's fastest computers, typically consisting of thousands of processors, used mainly in academia, military, government, and large corporations.

What is grid computing?

A form of computing where multiple servers, labs, or companies are connected via the internet to share resources, requiring high communication for synchronization.

What is the traditional sequence of instructions for summing an array of data?

For each element in the array, add it to a sum variable.

What is pair-wise summation?

A method where elements are summed in pairs, such as x0 + x1, x2 + x3, etc.

What is the parallel sum approach?

A method where multiple sums are calculated simultaneously, such as t0 = x0 + x1 and t1 = x2 + x3.

What are the two main types of memory architectures in parallel computing?

Shared Memory and Distributed Memory.

What is the difference between shared memory and distributed memory?

In shared memory, all processors access the same memory, while in distributed memory, each processor has its own memory and communicates over a network.

What are the six main architectures of parallel computing?

Chip Multiprocessors, Symmetric Multiprocessors, Heterogeneous Chip Designs, Clusters, Supercomputers.

What is the difference between threads and processes?

Threads are smaller processes that share the same memory space, while processes have their own address space.

What is Inter-Process Communication (IPC)?

A mechanism that allows processes to communicate and synchronize their actions when sharing resources.

What factors should be considered when choosing between a single process with multiple threads or multiple processes with IPC?

The operating system being used, the complexity of the problem, and the processing requirements.

What is the role of the operating system in thread scheduling?

The OS schedules threads for execution, managing resource allocation and execution timing.

What does SIMD stand for in parallel computing?

Single Instruction, Multiple Data.

What does MIMD stand for in parallel computing?

Multiple Instruction, Multiple Data.

What is the significance of computational resources in parallel computing?

They refer to the combined processing power of multiple computers or processors working together.

What is the expected outcome of parallel processing?

To accomplish a single task faster or to handle multiple tasks simultaneously.

What is the importance of communication in distributed memory systems?

Communication is crucial for synchronization and coordination between nodes that do not share memory.

What is the role of a cache controller in symmetric multiprocessors?

It manages the cache memory for each processor to optimize data access and performance.

What factors determine the complexity of a problem in parallel processing?

Operating System in use, processing requirements, timing requirements, and the architecture (single PC or distributed systems).

What are threads in the context of operating systems?

Threads are lightweight processes that have less overhead for creation and termination compared to full processes.

How does the OS manage threads compared to processes?

The OS can switch between threads faster than between processes, allowing for more efficient multitasking.

What tool can be used to check the number of cores and processors on a PC?

Windows Task Manager.

What is the significance of parallel processing in programming?

It allows a program to be broken into parts that can run independently, improving efficiency.

What is the difference between concurrent programming and parallel programming?

Concurrent programming deals with multiple tasks at once, while parallel programming involves doing multiple tasks simultaneously.

What is the role of the OS in scheduling threads and processes?

The OS manages scheduling to allow multiple processes to run concurrently and optimizes resource usage.

What happens during context switching?

The OS saves the state of the current process/thread and loads the state of the new process/thread to resume execution.

What are the different states a thread can be in?

New, Runnable, Blocked, and Terminated.

What is a 'main thread' in a process?

The main thread is the initial thread that runs when a process starts and can spawn child threads.

What is a 'blocked state' for a thread?

A blocked state occurs when a thread is waiting for resources or data and is not using CPU time.

What is a 'detached thread'?

A detached thread allows the parent thread to terminate without waiting for the child thread to finish.

What is Flynn's Taxonomy?

A classification system for parallel architectures based on the number of instruction streams and data streams.

What are the two types of memory architectures in parallel processing?

Shared Memory and Distributed Memory.

What is the problem with concurrent threads accessing the same memory location?

Conflicts arise when multiple threads access and modify the same memory location simultaneously.

What are synchronization techniques used for?

To solve problems that arise from data races when multiple threads access shared memory.

What is the difference between Uniform Memory Access (UMA) and Non-uniform Memory Access (NUMA)?

UMA allows all processors to share the same memory uniformly, while NUMA has varying access times for different processors.

What is the purpose of the 'join()' method in thread management?

It places a thread in a blocked state until the thread completes execution.

What is the illusion of parallel processing when using a single processor?

Swapping processes frequently gives the illusion of parallel processing, but it is not true parallelism.

What is the significance of data in parallel processing?

Parallel processing is particularly beneficial for data-intensive tasks, such as matrix multiplication.

What is a daemon thread?

A background thread that runs independently of the main process and can terminate without affecting the main thread.

What does it mean for a thread to be 'joinable'?

It indicates that a thread can be joined, meaning the parent thread can wait for it to finish.

What is the main goal of scheduling algorithms in operating systems?

To maximize throughput, fairness, minimize wait time, and minimize latency.

What is the role of the 'Ready Queue' in thread scheduling?

It holds processes that are ready to execute and waiting for CPU time.

What are 'Child Threads'?

Threads spawned by the main thread to perform additional tasks.

What is the first step in updating a variable in a multi-threaded environment?

READ the current value from memory.

What operation follows reading a variable's value in the update process?

MODIFY the value based on the desired operation.

What is the final step in updating a variable after modification?

WRITE the new value back to memory.

What is a data race in multi-threading?

A situation where two threads access shared data and try to change it at the same time.

What is a critical section in programming?

A part of the code that accesses shared resources and must not be executed by more than one thread at a time.

What mechanism is used to control access to critical sections?

A mutex (mutual exclusion lock).

What happens when a thread tries to acquire a mutex that is already locked?

The thread transitions to a BLOCKED state and waits for the mutex to be released.

What must a thread do after it has finished using a mutex?

Unlock (release) the mutex.

What can happen if a thread does not unlock a mutex?

It can lead to deadlocks or the program appearing to be caught in an infinite loop.

What is the purpose of keeping critical sections short and simple?

To avoid slowing down the execution of the program and to minimize the time threads spend in a BLOCKED state.

What is an atomic object in C++?

A templated object that encapsulates mutual exclusion required to control a single variable.

What is a recursive mutex?

A mutex that allows the same thread to lock it multiple times without causing a deadlock.

What happens when a thread requests a lock it already holds with a regular mutex?

It can lead to a deadlock situation where all threads are waiting indefinitely.

What is a non-blocking lock method?

A method that checks if a mutex can be locked without blocking the thread if it is unavailable.

What is the significance of the 'try to lock' method?

It attempts to lock a mutex and returns TRUE if successful, or FALSE if the mutex is not available.

Why is it important to manage critical sections carefully?

To prevent data races and ensure that shared resources are accessed safely.

What is the role of the main thread in a multi-threaded application?

It may be placed in a BLOCKED state waiting for other threads to complete their tasks.

What is the effect of including complex logic in a critical section?

It can slow down the execution and cause other threads to remain in a BLOCKED state.

What is a mutex?

A mutex (short for mutual exclusion) is a synchronization primitive used to protect shared resources from concurrent access by multiple threads.

What happens when multiple threads attempt to lock the same mutex?

If a thread tries to lock a mutex that is already locked by another thread, it will be blocked until the mutex is released.

What is the purpose of a 'Try Lock'?

A 'Try Lock' allows a thread to attempt to acquire a mutex without blocking; if the mutex is not available, the thread can continue executing other tasks.

What is a shared read lock?

A shared read lock allows multiple threads to read a shared resource simultaneously, but does not permit any thread to write to the resource.

What is an exclusive write lock?

An exclusive write lock allows only one thread to write to a shared resource at a time, preventing other threads from reading or writing until the lock is released.

What is the role of std::shared_mutex in C++17?

The std::shared_mutex class in C++17 allows multiple threads to read from a resource simultaneously while ensuring exclusive access for writing.

What is a deadlock?

A deadlock occurs when two or more threads are blocked forever, each waiting on the other to release a mutex, preventing any of them from proceeding.

What is starvation in threading?

Starvation happens when a thread is perpetually denied access to resources because other threads are continuously being prioritized over it.

What is a livelock?

A livelock occurs when two or more threads continuously change states in response to each other without making any progress, often due to excessive communication.

What is a scoped_lock in C++17?

A scoped_lock is a mutex wrapper that automatically manages the locking and unlocking of one or more mutexes, ensuring that they are released when the lock goes out of scope.

How can you prevent deadlocks?

Deadlocks can be prevented by establishing a consistent order of acquiring locks, setting timeouts for lock acquisition, or using a single lock for multiple resources.

What is the significance of priority in mutex management?

Setting priorities for mutexes can help manage which threads get access to resources first, reducing the likelihood of starvation and improving overall system performance.

What is the impact of contention for resources in parallel programming?

Contention for resources can lead to performance degradation as threads compete for limited resources, resulting in increased wait times and reduced throughput.

What is Amdahl's Law?

Amdahl's Law is a formula used to find the maximum improvement of a system when only part of the system is improved, highlighting the diminishing returns of parallelization.

What are some common sources of performance loss in parallel designs?

Common sources of performance loss include overhead, non-parallelizable tasks, idle processors, and contention for resources.

What is the difference between blocking and non-blocking locks?

Blocking locks prevent a thread from proceeding until the lock is available, while non-blocking locks allow a thread to continue executing if the lock cannot be acquired immediately.

What is the purpose of a mutex in critical sections?

A mutex is used in critical sections to ensure that only one thread can access a shared resource at a time, preventing data corruption and ensuring data integrity.

What happens if a thread holding a mutex terminates unexpectedly?

If a thread holding a mutex terminates without releasing it, other threads may be blocked indefinitely, leading to a situation known as an abandoned lock.

What is a 'TryLockDemo'?

A 'TryLockDemo' simulates multiple threads attempting to access a shared counter, demonstrating the differences between standard mutex usage and try-lock behavior.

What is the effect of having multiple threads reading a shared resource?

Having multiple threads read a shared resource is generally safe, as they can access the same value simultaneously without causing data corruption.

What is the purpose of a 'yield' in thread management?

A 'yield' allows a thread to voluntarily give up its remaining time slice, enabling other threads to run and potentially reducing the chances of starvation.

What is a 'Deadlock_Demo'?

A 'Deadlock_Demo' illustrates a situation where two threads are unable to proceed due to each holding a mutex that the other needs, resulting in a deadlock.

What is the significance of 'Abandoned_Demo'?

An 'Abandoned_Demo' showcases the consequences of a thread terminating without unlocking a mutex, leading to potential deadlocks or resource blocking.

What are the main factors to consider when writing parallel code?

Communication, Synchronization, Computation, Memory

What is a major component of communication in parallel processing?

Communication between threads or processes

What is the overhead in parallel code related to single data transitions?

A single data transition is considered overhead in parallel code.

What are examples of communication in parallel processing?

Sharing counters and caching between threads/processes.

What causes synchronization overhead?

When one thread or process must wait for another to complete.

What are mutexes used for in parallel processing?

Mutexes (locks) are used to share resources among threads.

How do parallel algorithms typically compare to sequential ones in terms of computations?

Parallel algorithms usually perform more computations than their sequential counterparts.

What is load imbalance in parallel processing?

Load imbalance is the uneven distribution of work among processors.

What is weak scaling in parallel processing?

Weak scaling refers to using N processors with a fixed amount of data/tasks per processor to accomplish more work in the same amount of time.

What is strong scaling in parallel processing?

Strong scaling involves using N processors with a fixed total problem size to accomplish the same amount of work faster.

How is throughput defined in parallel processing?

Throughput is the measure of actions per unit time, indicating how many tasks can be completed in a given time frame.

What is latency in the context of parallel processing?

Latency is the time it takes to perform a task once.

What is Amdahl's Law in parallel processing?

Amdahl's Law estimates the potential speedup of a processing task, considering the portion of the program that can be parallelized.

What is the formula for calculating speedup?

Speedup = (sequential execution time) / (parallel execution time)