Parallel Computing Flashcards
What is a directed acyclic graph (DAG) and how is it used in describing explicit parallelism?
Used to model dependencies between tasks.
Because they make clear which tasks can be executed in parallel.
Functional Parallelism
Focus on parallel execution of functions.
Data Parallelism
Focus on parallel processing of data
Task Parallelism
Focus on parallel executions of tasks such as thread, semaphores and locks.
What is Parallel Speedup and Efficiency?
Parallel Speedup is how much faster is the parallel algorithm.
Parallel Efficiency is the measure of the performance loss associated with parallel execution.
Amdahl’s Law
Tp = T1 (Fs + Fp / P)
Flynn’s Taxonomy
Characterizes architectures by whether the data flow and control flow are shared or independent.
SISD
Single Instruction Single Data:
At any one time only a single instruction is executed
Ex. Single Core
SIMD
Single Instruction Multiple Data:
Single Instruction broadcasted to multiple processors
Ex. Pipelining
MISD
Multiple Instruction Single Data:
Multiple Instructions operate on the same data stream.
Ex. Redundant computing for fault tolerance?
MIMD
Multiple Instruction Multiple Data:
Multiple cores operate on multiple data items.
Ex. Clusters and MPPs
Describe the particular case of SPMD and how it relates to Flynn’s taxonomy.
Single Program Multiple Data:
Running the same program with different data inputs on parallel processors
SPMD is a type of MIMD
Symmetric multiprocessor
Where processors see no difference between one memory location from another
Any memory location is accessible to every processor
Access times do not differ
Logically distributed memory
The memory is logically spread across all processors but is physically stored locally on each processor.
Physically Distributed Memory
The processors have their own address space that is physically separate from the memory of other processors.
What does granularity mean with respect to parallelism?
How many operations can be performed between synchronizations.
What is Thread Parallelism?
Multiple threads within a single process are run in parallel.
What is the difference between a thread and a process?
Same code as a process but has a private program counter, stack, and local variables.
What is the fork-join mechanism?
Divides a program into multiple threads to do different tasks and then joins to combine the results.
What is a thread context? What does it consist of?
Private data (stack, local variables)
What are atomic operations?
Operations performing a single indivisible step.
What is a critical section? Is it used in shared address space or distributed address space architectures?
Where multiple threads need to access the same resources one at a time.
Can be used in both shared address space or distributed address space architectures.
What is affinity in thread systems?
Mapping certain threads to run on only certain cores.
What is the difference between hyperthreading and multi-threading?
Hyperthreading does not run at the same time, but quickly switches between themselves when one thread is waiting.
Multi-threading can do many processes at the same time to get more work done faster.
Degree
The number of nodes connected to another node.
Bisection Width
The minimum number of links that have to be removed to divide the graph into 2 equal parts
Diameter
the maximum shortest distance between two nodes.
Why is the difference between static and dynamic scheduling?
Static: Using a pre-determined assignment of work to processors.
Dynamic: The assignment is determined during executions.
