PTfS22: Assignment 4: Code optimization, multicore power (due June 3 11:59 p.m.)

Opened: Thursday, 26 May 2022, 12:00 AM

Due: Saturday, 4 June 2022, 12:00 AM

Optimizing for code balance. Suppose you have a code like this:
```
for(i=0; i<N; ++i) {
  a[i] = b[i] * c[i];
}
for(i=0; i<N-1; ++i) {
  b[i] = a[i+1] * 0.5;
}
```
All arrays hold DP floating-point numbers, and N is "large."

(a) (10 crd) Suggest an optimization that will improve the performance of the code. What is the expected change in the memory code balance? Discuss if the optimized code is SIMD vectorizable.
(b) (30 crd) Construct a single-core performance model (along the lines of what we did in the lecture with the vector triad) for the optimized code on an Intel Haswell core at 2.3 GHz. Consider that the Haswell is in Cluster-on-Die (CoD) mode. Calculate the expected performance in Gflop/s and the expected memory bandwidth in Gbyte/s for an in-memory data set. You can assume that the compiler generates separate load instructions for loads to successive elements, e.g., a[i] and a[i+1].
Loop optimization. In Assignment 3.2 (outer product of vectors), we found that the memory code balance (memory data transfer volume per flop) can be larger than the minimum if N is very large. This is the loop nest again (with correct loop order):
```
for(i=0; i<N; ++i) 
  for(j=0; j<N; ++j)
    a[i][j] = x[i] * y[j];
```
(a) (10 crd) Consider an Intel Ivy Bridge processor with a 25 MiB L3 cache. Use the formula you derived in Assignment 3 to calculate the value of N at which the code balance increases from the minimum. Explain why this is not a realistic scenario.
(b) (30 crd) Now we look at a modified version of the problem:
```
for(i=0; i<M; ++i) 
  for(j=0; j<N; ++j)
    a[i][j] = x[i] * y[j];
```
For a given N, we choose M so that N*M\(~\approx~\)10⁹. Calculate at which N (and M) the code balance increase occurs now. Modify the code so that the memory code balance becomes independent of N.
Multicore power envelope. We wish to understand why processor vendors trade clock frequency for concurrency when introducing multicore chips, so we establish a simple model for power dissipation. Assume that a certain chip (with a given manufacturing process, e.g., 14 nm) dissipates a power of \( W=W_d \) when running at its base frequency \( f_0\). Furthermore we assume that \(W\) is proportional to \( f^3 \).

(a) (5 crd) "Overclocking" is a popular strategy (especially among gamers, but also used for "Turbo Boost") to speed up the CPU. Calculate the power dissipation \(W\) when the clock frequency is increased by 25% (e.g., from 2.0 GHz to 2.5 GHz).
(b) (10 crd) If we require that the overall power dissipation of a chip shall be constant (\(W_d\)), we can trade clock speed for cores: By reducing the clock speed by some relative amount \(\Delta f/f_0\), we can put more cores (transistors) on the same chip and still stay within the power limit. Calculate the required clock speed reduction \(\Delta f/f_0\) for an \(m\)-core chip (instead of single core) with a power dissipation of \(W_d\). Calculate how many cores can be put on the chip (approximately) when the clock speed is reduced by a factor of 1.8.
(c) (5 crd) Now assume \(m=6\). Calculate the minimum and maximum performance gain (compared to the single-core chip with \(m\) times fewer transistors but the same power envelope, and the same memory interface) when using all six cores. For which types of code do you expect these extremal performance gains?