Assignment 10: More stencils, slow computing (due July 15 11:59 p.m.)

#pragma omp parallel private(iter)
{<br>  for(iter=0; iter<maxiter; ++iter) {<br>    #pragma omp for schedule(runtime)<br>    for(k=1; k<N-1; ++k) {</span><br><span>      for(j=1; j<N-1; ++j) {</span><br><span>        for(i=1; i<N-1; ++i) {</span><br><span>          f[t1][k][j][i] = 1./6. * <br>                      (f[t0][k-1][j][i]+<br>                       f<span>[t0]</span>[k+1][j][i]+<br>                       f<span>[t0]</span>[k][j-1][i]+<br>                       f<span>[t0]</span>[k][j+1][i]+<br>                       f<span>[t0]</span>[k][j][i-1]+<br>                       f<span>[t0]</span>[k][j][i+1]);</span><br><span>        }
      }
    }
    swap(t0,t1);
  }
}

Assume that N=350, all arrays are in double precision, and that we run this code on a ten-core Intel "Ivy Bridge" processor (25 MiB of shared L3 cache, 256 KiB of per-core L2 cache, 32 KiB of per-core L1, memory bandwidth of 41 GB/s, clock frequency 2.0 GHz).

(a) (5 crd) Is the code correct? If it is not, fix it.

(b) (10 crd) We set OMP_NUM_THREADS=10 and OMP_SCHEDULE="static" and run the code on one socket (N=350). What is the relevant bottleneck? Calculate the maximum performance we can expect. What changes for N=200?

(c) (10 crd) Someone says: "It is better to choose the data layout f[k][j][i][t], because the source and the target arrays are handled together in the same loop, and it will be better to interleave them." What is your comment on this?

(d) (10 crd) What happens if we set OMP_SCHEDULE="static,1"at N=350? Assume the original data layout. What is the expected performance now?

(e) (25 crd) Instead of parallelizing the outer (k) loop, we might just as well parallelize the inner (i) loop. Assume that the cost for the implicit barrier at the end of a parallel for loop is 2000 CPU cycles. At N=350, calculate the expected performance when the inner loop is parallelized (assuming OMP_SCHEDULE="static"). Calculate at which N the performance would exceed the level predicted in (b). Can we do something about the barrier overhead when the inner loop is parallelized? (Hint: There is a way to switch off the automatic barrier at the end of work-sharing loops in OpenMP. Think carefully about how to leverage this feature here and still have a correct code).

Slow computing. It is often stated (sometimes humorously) that all you have to do to make your program scale is to compile it with the "-O0" optimization flag. Substantiate this claim using a speedup model based on Amdahl's Law.
Assume that Amdahl's Law holds for a given code with serial execution time \(T(1)=T_s+T_p\), where \(T_s\) is the serial runtime of the non-parallelizable part and \(T_p\) is the serial runtime of the perfectly parallelizable part. In the parallel case with \(N\) workers, an additional runtime overhead of \(T_c(N)\) applies.

(a) (10 crd) Formulate a model for the strong-scaling speedup function \(S(N)\) in terms of dimensionless quantities \(\bar s\), \(\bar p\), and \(\bar c(N)\) for serial fraction, parallel fraction, and communication overhead; bar donates dimensionless quantities.

(b) (15 crd) Now assume that everything that pertains to code execution is slowed down by a given factor \(\sigma<1\), i.e., for \(\sigma=0.5\) the code executes with half the original performance. However, the communication time stays unchanged. This mimics the "slow program" scenario or the use of slower CPUs. The speedup is now a function of \(\sigma\), i..e, \(S(N,\sigma)\). Explain if the statement from the beginning is justified, i.e., can you improve the scaling of your code by making it run slower? What is the only prerequisite for that (assuming that Amdahl's Law with communication holds)?

(c) (15 crd) Now assume a specific case of \(\bar s=0\) (no serial fraction) and \(\bar c=\bar\alpha N^{-2/3}+\bar\lambda\), which describes 3D Cartesian domain decomposition on a non-blocking network with finite latency (don't bother about the details, it will be covered in the lecture). \(\bar\alpha\) is a dimensionless constant. The single-worker performance (without slowdown) is \(P(1)\). Calculate the limit of \(P(N,\sigma)\)  for \(N\to\infty\). How does it depend on \(\sigma\)? Is this an expected result? Elaborate!