PTfS26: Assigmnent 10: Stencils, slow computing

Opened: Tuesday, 7 July 2026, 12:00 PM

Due: Wednesday, 15 July 2026, 10:05 AM

Stencils. Consider the following stencil update sweep (all data is double precision):
```
#pragma omp parallel for schedule(static)
for(int j=1; j<N-2; ++j)
     for(int i=1; i<M-1; ++i) 
          y[j][i] = c * (x[j][i-1]
                       + x[j+1][i]
                       + x[j+2][i]
                       + x[j+2][i-1]);
```
(a) (10 crd) Formulate the relevant layer condition that determines the code balance in a given memory hierarchy level (e.g., memory).
(b) (10 crd) Assuming that none of the arrays fit into any cache, calculate the best-case and worst-case in-memory code balance in byte/LUP.
(c) (10 crd) Calculate the absolute upper performance limit for an in-memory problem (i.e., none of the arrays fit into any cache) on a full Fritz socket (memory bandwidth 160 Gbyte/s)! Knowing the cache sizes of the CPU (if you don't remember, use likwid-topology to find out), what does the condition from (a) look like in this particular case? Hint: Take into account that the L3 cache on the Ice Lake CPUs is an exclusive victim cache, i.e., in order to calculate the available cache per core you can add the L2 and L3 cache sizes.
(d) (10 crd) Finally, we modify the stencil code:
```
#pragma omp parallel for schedule(static)
for(int j=1; j<N-2; ++j)
     for(int i=1; i<M-1; ++i) 
          y[j][i] = c * (x[j][i-1]
                       + x[j+2][i]
                       + x[j+2][i-1]);
```
Derive the layer condition for this variant. Explain how you arrived at your result!
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) (5 crd) Formulate a model for the strong-scaling speedup function \(S(N)\) in terms of dimensionless quantities \(s\), \(p\), and \(c(N)\) for serial fraction, parallel fraction, and dimensionless communication overhead.
(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, the use of slower CPUs, or a clock frequency reduction. 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)? Is speedup a good metric for assessing the quality of a parallel code?
(c) (15 crd) Now assume a specific case of \(s=0\) (no serial fraction) and \(c(N)=\alpha N\), which describes a typical barrier synchronization overhead if the barrier is not implemented optimally. \(\alpha\) is a dimensionless constant. The single-worker performance (without slowdown) is \(P(1)\). Calculate how \(P(N,\sigma)\) scales for \(N\gg 1\). How does it depend on \(\sigma\)? Is this an expected result? Elaborate!
Wavefront Gauss-Seidel. Consider the wavefront-parallel Gauss-Seidel algorithm as shown in the lecture on stencils. The code cannot be vectorized due to a loop-carried dependency in the inner loop. Assume we run the code with a memory-bound problem size on a Fritz node, and that the overhead for the barrier is insignificant. The scalar FP64 ADD and MUL instruction latencies are 4 cycles each. Further assume that the division by a constant (6.0) is replaced by the compiler by a multiplication with a reciprocal.

(a) (15 crd) Assuming that all independent work in the loop nest can be overlapped with the relevant dependency chain, calculate the maximum in-core performance limit \( P_{max} \) per core in LUPs/cy.
(b) (10 crd) When running the code in parallel, is it possible to saturate the memory bandwidth of an 18-core ccNUMA domain (about 75 Gbyte/s) at a clock speed of 2.4 GHz? You can assume that the optimal code balance for this code applies.