PTfS22: Assignment 3: Peak performance, peak bandwidth, code balance (due May 27 11:59 p.m.)

Opened: Tuesday, 17 May 2022, 12:00 AM

Due: Saturday, 28 May 2022, 12:00 AM

Peak numbers. Floating-point computations and memory bandwidth are important resources of a processor. Both can be used to derive upper limits for code performance. Assume a processor chip with the following properties:
- Clock frequency of 2.4 GHz
- 36 cores
- AVX-512 instruction set (512-bit wide SIMD registers); each core is capable of retiring two full-width double-precision FMA instructions per cycle
- 8-channel DDR4 RAM, 3200 MHz
(a) (5 crd) Calculate the double-precision floating-point peak performance of the chip in Tflop/s
(b) (5 crd) Calculate the theoretical memory bandwidth of the chip in Gbyte/s
(c) (20 crd) Consider the following "STREAM Triad" loop on double-precision data:
```
for(int i=0; i<10⁸; ++i)
    a[i] = b[i] + s * c[i];
```
Assume that nontemporal stores cannot be used here, and that the calculation can be distributed across all cores of the chip. Calculate the minimum time it takes to do the arithmetic in this loop and the minimum time it takes to transfer the data over the memory bus. From these numbers, what would you conclude is the relevant bottleneck when executing the loop on the above chip?
Outer product. The following C loop nest computes the outer product of two vectors x[] and y[] in order to generate a matrix a[][]:
```
for(j=0; j<N; ++j) 
  for(i=0; i<N; ++i)
    a[i][j] = x[i] * y[j];
  
```
You can assume that N is "large," i.e., the matrix does not fit into any cache, and that all data in a, x, and y are double-precision floating-point numbers. This serial code is run on a 20-core processor with cache sizes of 32 KiB (per-core L1), 1 MiB (per-core L2), and 27 MiB (shared L3), a MULT peak performance of 34 GFlop/s per core, and a memory bandwidth of 120 GB/s. A core can execute two LOAD and one STORE instruction per cycle (throughput) in addition to two MULT instructions (and a couple of other stuff that is of no interest here). SIMD is supported with up to AVX-512. The MULT instruction has a latency of four cycles. This is all quite close to a modern Intel Xeon "Skylake" CPU.

(a) (5 crd) Do you see a severe potential performance problem with this code? Describe it and suggest a code transformation to fix it!

(b) (10 crd) Identify spatial and temporal access locality in the code (with the optimization from (a)). Which data structures lead to which locality of access? How does this depend on N?

(c) (20 crd) Calculate how much data must be transferred to and from main memory per iteration! If this depends on N, quantify the dependence. Can nontemporal stores be used? If they can, how would this change the memory data traffic per iteration?
Balance. Calculate the in-memory code balance for loops with the following loop bodies, assuming that all arrays do not fit into any cache (a loop over i is always implied, nontemporal stores do not apply):

(a) (5 crd) s = s + a[i]; (double precision)
(b) (5 crd) s = s + a[i]*b[i]; (double precision)
(c) (5 crd) a[i] = b[i] + s*c[i]; (single precision)
(d) (5 crd) a[i] = a[i] + s*c[i]; (single precision)
(e) (15 crd) y[i] = y[i] + x[i] * v[index[i]]; (DP for x[],y[], and v[], and int32 for index[])

In case (e) you have to be a little imaginative; obviously it is impossible to give a single, definite answer...