PTfS22: Assignment 9: Ray tracing, performance modeling (due July 10 11:59 a.m.)

Opened: Friday, 1 July 2022, 12:00 AM

Due: Sunday, 10 July 2022, 12:00 PM

Parallel ray tracer. Parallelize a simple ray tracer code using OpenMP. You can ﬁnd the C source in ~ptfs100h/GettingStarted/raytrace_c.c.

The picture is divided into so-called tiles (see ﬁgure). The function which is responsible for calculating a tile is called calc_tile(). Important parameters are size (the number of pixels in one direction) and tilesize (the number of pixels of one tile in one direction), both hard-coded at the start of main(). The commands that print the picture in PNM format are commented out, but you can use them to check for correctness. You can display the image with the ’display’ tool from the ImageMagick toolkit.

(a) (30 crd) Parallelize the code with OpenMP and draw a diagram of performance vs. number of cores on up to 72 physical cores of a Fritz node, using a picture size of 10000x10000 pixels and a tile size of 2000x2000 pixels. When parallelizing the code, make sure that it really computes the image correctly! Set the clock speed to 2 GHz.
(b) (10 crd) Is the memory bandwidth a bottleneck? How can you tell? Hint: each pixel is one byte (8 bits), and the memory bandwidth of a Fritz socket is about 160 Gbyte/s.
(c) (30 crd) Does your code scale up to 72 cores, i.e., does it run 72 times faster than in sequential mode? If it does not, improve the scaling! How did you accomplish this? You have to keep the image size constant at 10000x10000 pixels, but you are free to make any other changes to the code and its parameters. (Hint. Depending on how you did the parallelization, you may want to look up the collapse clause in OpenMP. Also remember that not all pixels are equal.) Document all your settings so that your experiment can be reproduced.
Stencils. Consider the following stencil update sweep (all data is double precision):
```
for(j=0; j<N-2; ++j)
     for(i=1; i<M-1; ++i) 
          y[j][i] = c * (x[j][i-1]+x[j][i+1]+x[j+1][i]+x[j+2][i]) + f[j][i];
```
(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.
(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 one 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?