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.
