What are the 3 types of parallelism?
- Pipelined algorithms / Algorithmic parallelism
- Geometric/ Partitioned parallelism
- Asynchronous/ relaxed parallelism
- What is pipelined algorithms/ algorithmic parallelism?
- Mention 3 key concepts
Breaking down computation tasks into discrete stages that can be executed in parallel.
1. Stages
2. Parallel execution
3. Buffering
- What is geometric/ partitioned parallelism?
- Mention 3 key concepts
A type of parallel computing where data can be decomposed into geometric regions that can be processed independently and concurrently.
1. Domain decomposition
2. Independent processing
3. Communication
- What is asynchronous/ relaxed parallelism?
- Mention 3 key concepts
Running tasks independently without waiting for other tasks to complete.
1. Independence
2. Non-blocking execution
3. Callback mechanisms.
List 7 types of (less known) parallelism
- Data parallelism
- Task parallelism
- Instruction-level parallelism - multiple instructions from a single instruction stream.
- Thread-level parallelism
- Bit-level parallelism - reducing no. of instructions needed.
- Speculative parallelism
- Hybrid parallelism
List the 4 types of decomposition
- Recursive decomposition (recursion)
- Data decomposition (input/output data)
- Exploratory decomposition (tree like thing - next move)
- Speculative decomposition (switch-case)
What is a task dependency graph?
An illustration of a decomposition where nodes correspond to tasks and edges indicate the results of one task is needed for processing the next.
- How is granularity of a problem determined?
- What is fine-grained decomposition and coarse grained decomposition?
- By the number of tasks the problem is decomposed into.
- Large no. of tasks = fine grained
- Small no. of tasks = coarse grained
What is the degree of concurrency?
The number of tasks of a decomposition that can be executed in parallel.
What is the critical path length?
The length of the longest path in a task dependency graph.
What is a task interaction graph?
A graph where nodes represent tasks and edges represent their interactions/ data exchanges.
List 3 points considered during a process mapping
- mapping independent tasks to different processes.
- Assigning tasks on the critical path to processes as soon as they become available.
- Minimize interaction between processes, by mapping tasks with dense interactions to the same processes.
