PTfS22: Assignment 8: More OpenMP (due July 5 6:00 p.m.)

Opened: Friday, 24 June 2022, 12:00 PM

Due: Tuesday, 5 July 2022, 6:00 PM

(10 crd) Handling recurrence. Parallelize the second loop in the following code using OpenMP- correctly, of course:

#define N 10000000
int main() {<br>    int i,b[N],c[N],d[N];<br>    for(i=0;i<N;i++)<br>        b[i]=c[i]=d[i]=rand();<br>    // parallelize this loop<br>    for(i=1;i<N;i++) {<br>        b[i]=1+i;<br>        c[i]=b[i-1]+i;<br>        d[i]=c[i-1]+i;<br>    }
}

(10 crd) OpenMP fun. There is a correctness problem with this OpenMP parallelization. Describe it and fix it.

double x[100],y[100],tmp;
int i;
double work1(int);
// initialization code etc. omitted
#pragma omp parallel 
{<br>  #pragma omp for <br>  for(i=0; i<100; i++) {<br>    tmp=work1(i);<br>    x[i]=x[i]+tmp;<br>  }
  #pragma omp for
  for(i=1; i<100; i++) {<br>    y[i]=x[i-1]*y[i];<br>  }
}

π by the Monte Carlo method. The quarter unit circle in the ﬁrst quadrant with origin at \( (0,0) \) and radius 1 has an area of \( \pi / 4 \). Look at random number pairs in \( [0,1] \times [0,1] \). The probability that such a point lies inside the circle is \( \pi / 4 \), so given enough statistics we are able to calculate \( \pi \) using this so-called “Monte Carlo” method.

(a) (20 crd) Write a parallel OpenMP program that performs this task. Use the rand_r() function to get separate random number sequences for all threads (why is this important?). Report the relative error you can achieve with 72 threads and 3 x 10⁹ points (using double precision).

(b) (20 crd) Draw a plot of performance (in iterations per second) vs. number of cores on a Fritz ccNUMA domain (1..18 cores) at constant clock speed (2.0 GHz). Does your performance "scale," i.e., do you get n times faster with n cores instead of one? If you don't: you really should. Fix the problem. (Hint: when the first OpenMP region in a program is entered there may be considerable startup overhead. In order to avoid such effects, execute a "bogus" parallel region before the actual benchmark loop.).
Parallel histogram computation. The following code fragment calculates a histogram with 8 bins from the results of the least significant three bits of the standard rand_r() random number generator:
```
unsigned int seed = 1;
long hist[8];
for(int i=0; i<8; ++i)
  hist[i]=0;
```
```
wcstart = getTimeStamp();
for(long i=0; i<2000000000; ++i) {<br>  hist[rand_r(&seed) & 7]++;<br>}
wcend = getTimeStamp();
for(int i=0; i<8; ++i) {<br>  cout << "hist[" << i << "]=" << hist[i] << endl;<br>}
cout << "Time: " << wcend-wcstart << " sec" << endl;
```
Parallelize the histogram calculation correctly using OpenMP (20 crd). You can find a serial example code in the ~ptfs100h/GettingStarted/HISTO folder. Draw performance in iterations per second vs. number of cores in a diagram (use up to 18 cores on one Fritz ccNUMA domain at fixed 2.0 GHz). Does your solution scale? If it does not, make it scale! (20 crd)
Hint: Try different solutions. Think simple first.