Assignment 4
- Handling recurrence. Parallelize the second loop in the following code using OpenMP:
#define N 10000000
int main() {
int i,b[N],c[N],d[N];
for(i=0;i<N;i++)
b[i]=c[i]=d[i]=rand();
// parallelize this loop
for(i=1;i<N;i++) {
b[i]=1+i;
c[i]=b[i-1]+i;
d[i]=c[i-1]+i;
}
} 
Barrier cost. In lecture 5 we compared
the performance of a parallel dense MVM code with and without the nowait clause (see image). This was run on a CPU with a 3 GHz clock speed. From the data, and assuming that the version with nowait does not have any barrier overhead, estimate
the time in cycles for an implicit barrier on this system (with 10 cores).- Parallel ray tracer. Parallelize a simple ray tracer code using OpenMP. You can find the source in ~unrz55/GettingStarted/raytrace_c.c.
The picture is divided into so-called tiles (see figure). 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) Draw a diagram of performance vs. number of cores on up to 20 physical cores of an Emmy node, using a picture size of 8000x8000 pixels.
(b) Is the memory bandwidth a bottleneck? How can you tell? Hint: each pixel is one byte (8 bits), and the memory bandwidth of an Emmy socket is about 40 GByte/s.
(c) Does your code scale up to 20 cores? If is does not, improve the scaling! (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.) Is there an optimal tile size? Can you optimize the sequential code? What is the best performance in pixels per second you can get on an Emmy node? Document all your settings so that your experiment can be reproduced.
Last modified: Wednesday, 11 November 2020, 5:43 PM