Assignment8

Assignment 8, due May 20th, 2020

The goal of this assignment is to work with data and control dependencies.

Exercise 1 (1 Point)

Description

Consider the following, individual code examples in the context of dependence analysis, race conditions, and parallelization:

a[0] = 0;
#pragma omp parallel for
for (i=1; i<N; i++) {
    a[i] = 2.0*i*(i-1);
    b[i] = a[i] - a[i-1];
}

a[0] = 0;
#pragma omp parallel
{
    #pragma omp for nowait
    for (i=1; i<N; i++) {
        a[i] = 3.0*i*(i+1);
    }
    #pragma omp for
    for (i=1; i<N; i++) {
        b[i] = a[i] - a[i-1];
    }
}

#pragma omp parallel for
for (i=1; i<N; i++) {
    x = sqrt(b[i]) - 1;
    a[i] = x*x + 2*x + 1;
}

f = 2;
#pragma omp parallel for private(f,x)
for (i=1; i<N; i++) {
    x = f * b[i];
    a[i] = x - 7;
}
a[0] = x; 

sum = 0; 
#pragma omp parallel for
for (i=1; i<N; i++) {
    sum = sum + b[i];
}

Tasks

• For each example, investigate whether it is parallelized correctly, whether there are any dependencies and how any potential parallelization mistakes can be solved while keeping the parallelism. Are there any downsides to your solutions?

Exercise 2 (1 Point)

Description

• Dependence analysis is a method of determining whether parts of source code can be run independently and hence be safely parallelized. Compilers often perform dependence analysis as a first step in order to safely perform vectorization in a second step (an instruction level parallelism technique, to be covered later in this course). In this exercise, we will look at the first step only, namely compiler capabilities and reporting.

Tasks

• Compile the given program analysis.c with gcc 8.2.0 and the flags -O2 -ftree-vectorize -fopt-info-vec-all.
• Examine the output. Is there any useful information regarding dependence analysis? What are your findings?

Exercise 3 (1 Point)

Description

Investigate the following given code examples along with their task.

Tasks

• Investigate the given code excerpt. Can this code be safely parallelized manually? Can this code be safely parallelized by the compiler?

  void copy(double* x, double* y) {
      for(int i = 0; i < 1024; i++) {
          x[i] = y[i];
      }
  }

• Normalize the following loop nest:

  for (int i=4; i<=N; i+=7) {
      for (int j=0; j<=N; j+=3) {
          A[i] = 0;
      }
  }

• Does the following code excerpt hold any dependencies? If not, how would you parallelize it? If yes, what are the distance and direction vectors?

  for(int i = 1; i < N; i++) {
      for(int j = 1; j < M; j++) {
          for(int k = 1; k < L; k++) {
              a[i+1][j][k-1] = a[i][j][k] + 5;
          }
      }
  }

General Notes

All the material required by the tasks above (e.g., code, figures, text, etc...) must be part of the solution that is handed in. Your experiments should be reproducible and comparable to your measurements using the solution materials that you hand in.

Every member of your group must be able to explain the given problem, your solution, and possible findings. You may also need to answer detailed questions about any of these aspects.