Chapter 4

Question 1

What are the four steps in the Parallel Design Process?

Answer 1

• PARTITION
• COMMUNICATE
• AGGLOMERATE
• MAP

These steps help in analyzing and designing parallel algorithms.

Question 2

What is a dependency in the context of parallel computing?

Answer 2

A situation where one operation must complete before another can begin

Dependencies are considered the enemy of parallelism.

Question 3

True or false: Only RAW dependencies limit parallelism.

Answer 3

TRUE

WAR and WAW dependencies can often be worked around.

Question 4

What are the three types of data dependencies?

Answer 4

• RAW (Read After Write)
• WAR (Write After Read)
• WAW (Write After Write)

Each type has different implications for parallel execution.

Question 5

What is a loop-carried dependency?

Answer 5

A dependency where iteration i depends on results from iteration i-k

These dependencies are primary barriers to loop parallelization.

Question 6

What is the key insight regarding S2 and S3 in the dependency example?

Answer 6

S2 and S3 can run in parallel because they have no dependency on each other

This illustrates how dependencies affect execution order.

Question 7

What are Bernstein’s Conditions for Parallelism?

Answer 7

• Condition 1: No RAW
• Condition 2: No WAR
• Condition 3: No WAW

These conditions help determine if two tasks can run in parallel.

Question 8

What is data decomposition in parallel computing?

Answer 8

Partitioning the data and applying the same operation

This strategy is useful for uniform workloads.

Question 9

What is the block distribution strategy?

Answer 9

Divide data into contiguous chunks

Best for uniform workloads where each element takes the same time to process.

Question 10

What is the cyclic distribution strategy?

Answer 10

Assign elements in round-robin fashion

Best for non-uniform workloads where processing time varies by element position.

Question 11

What is the block-cyclic distribution strategy?

Answer 11

Assign blocks of size B in round-robin fashion

Used in ScaLAPACK and many HPC applications.

Question 12

What is the functional (task) decomposition?

Answer 12

Partitioning the computation/functions

Different processors execute different tasks, often combined in real applications.

Question 13

What is the pipeline decomposition?

Answer 13

A special form of functional decomposition where stages operate on a stream of data

It helps in improving latency and throughput.

Question 14

What is the recursive decomposition?

Answer 14

Dividing a problem into subproblems of the same type and solving them in parallel

Commonly used in divide-and-conquer algorithms.

Question 15

What does a dependency graph show?

Answer 15

Which operations must precede others

It helps visualize dependencies and critical paths.

Question 16

What is the critical path in a dependency graph?

Answer 16

The longest path through the graph, determining the minimum time to complete all tasks

It indicates the maximum speedup possible.

Question 17

What are the three techniques to eliminate or reduce dependencies?

Answer 17

• Variable Renaming
• Privatization
• Reduction

These techniques help enable parallelism by addressing different types of dependencies.

Question 18

What is the first step in the PCAM model for parallel algorithm design?

Answer 18

Partitioning

Decompose problem into tasks (Data or functional).

Question 19

In OpenMP, what directive is used to indicate a parallel for loop?

Answer 19

pragma omp parallel for

This directive allows multiple iterations of the loop to be executed in parallel.

Question 20

What does the reduction clause do in OpenMP?

Answer 20

Combines values from multiple threads into a single value

Example: #pragma omp parallel for reduction(+:sum) for summing elements.

Question 21

What is the purpose of loop fission?

Answer 21

Split loops to separate dependencies

This can allow for parallel execution of independent parts.

Question 22

What is the goal of load balancing in parallel computing?

Answer 22

Even distribution of computation

This helps to maximize resource utilization and minimize idle time.

Question 23

True or false: Fine-grained tasks have a small size and many tasks.

Answer 23

TRUE

Fine-grained tasks typically have higher overhead due to more synchronization.

Question 24

What are the communication patterns in parallel computing?

Answer 24

• Point-to-Point
• Broadcast
• Scatter
• Gather
• All-to-All
• Reduction

These patterns determine how tasks exchange data.

Question 25

What does **loop interchange** achieve?

Answer 25

Reorders loops to change dependency structure ## Footnote This can allow for better parallelization by reducing dependencies.

Question 26

In the context of parallel programming, what does **granularity** refer to?

Answer 26

The size of tasks in a parallel program ## Footnote It can be fine-grained (small tasks) or coarse-grained (large tasks).

Question 27

What is the **OpenMP directive** for static scheduling with chunks of 4?

Answer 27

#pragma omp for schedule(static, 4) ## Footnote This assigns equal chunks of 4 iterations upfront to threads.

Question 28

Fill in the blank: The **PCAM** model stands for **P**, **C**, **A**, **M**.

Answer 28

Partitioning, Communication, Agglomeration, Mapping ## Footnote This model provides a systematic approach to parallel algorithm design.

Question 29

What is the **dependency type** in the following code snippet: for (i = 0; i < n; i++) { a[i] = b[i] + c[i]; }

Answer 29

Fully parallel ## Footnote There are no dependencies between iterations.

Question 30

What is the **dependency type** in the following code snippet: for (i = 1; i < n; i++) { a[i] = a[i-1] * 2; }

Answer 30

Sequential only ## Footnote Each iteration depends on the result of the previous one.

Question 31

What is the **OpenMP implementation** for parallelizing matrix multiplication?

Answer 31

#pragma omp parallel for collapse(2) ## Footnote This allows both outer loops (i and j) to be executed in parallel.

Question 32

What is the **dependency type** in the following code snippet: for (i = 0; i < n; i++) { sum = sum + a[i]; }

Answer 32

Parallel (use reduction) ## Footnote The sum can be computed in parallel using a reduction clause.

Question 33

What is the **dependency type** in the following code snippet: for (i = 2; i < n; i++) { a[i] = a[i-2] + b[i]; }

Answer 33

2-way parallel ## Footnote There are dependencies, but they can be parallelized in two ways.

Question 34

What is the **dependency type** in the following code snippet: for (i = 0; i < n; i++) { a[i] = a[i] + 1; }

Answer 34

Fully parallel ## Footnote Each iteration is independent of the others.