Algorithms

Question 1

What are the 3 types of parallelism?

Answer 1

1. Pipelined algorithms / Algorithmic parallelism
2. Geometric/ Partitioned parallelism
3. Asynchronous/ relaxed parallelism

Question 2

• What is pipelined algorithms/ algorithmic parallelism?
• Mention 3 key concepts

Answer 2

Breaking down computation tasks into discrete stages that can be executed in parallel.
1. Stages
2. Parallel execution
3. Buffering

Question 3

• What is geometric/ partitioned parallelism?
• Mention 3 key concepts

Answer 3

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

Question 4

• What is asynchronous/ relaxed parallelism?
• Mention 3 key concepts

Answer 4

Running tasks independently without waiting for other tasks to complete.
1. Independence
2. Non-blocking execution
3. Callback mechanisms.

Question 5

List 7 types of (less known) parallelism

Answer 5

1. Data parallelism
2. Task parallelism
3. Instruction-level parallelism - multiple instructions from a single instruction stream.
4. Thread-level parallelism
5. Bit-level parallelism - reducing no. of instructions needed.
6. Speculative parallelism
7. Hybrid parallelism

Question 6

List the 4 types of decomposition

Answer 6

1. Recursive decomposition (recursion)
2. Data decomposition (input/output data)
3. Exploratory decomposition (tree like thing - next move)
4. Speculative decomposition (switch-case)

Question 7

What is a task dependency graph?

Answer 7

An illustration of a decomposition where nodes correspond to tasks and edges indicate the results of one task is needed for processing the next.

Question 8

• How is granularity of a problem determined?
• What is fine-grained decomposition and coarse grained decomposition?

Answer 8

• By the number of tasks the problem is decomposed into.
• Large no. of tasks = fine grained
• Small no. of tasks = coarse grained

Question 9

What is the degree of concurrency?

Answer 9

The number of tasks of a decomposition that can be executed in parallel.

Question 10

What is the critical path length?

Answer 10

The length of the longest path in a task dependency graph.

Question 11

What is a task interaction graph?

Answer 11

A graph where nodes represent tasks and edges represent their interactions/ data exchanges.

Question 12

List 3 points considered during a process mapping

Answer 12

1. mapping independent tasks to different processes.
2. Assigning tasks on the critical path to processes as soon as they become available.
3. Minimize interaction between processes, by mapping tasks with dense interactions to the same processes.