Parallel Programming Concepts

Back to course details

Week 3

Optional Coding Task

Week 3 - Optional Coding Task

Although this course is focusing on parallel programming concepts , we would like to give you a chance to 'make your fingers dirty' with some coding tasks. The following assignment is completely optional, the results have no influence on your final grading.

We suggest that you use the OpenHPI forum for discussing your solution strategy with other students. The teaching team will monitor the idea exchange and tries to help, if needed. Code can be easily shared via Pastie. We will publish some of our own example solutions (with threads and with C/OpenMP tasks) in week 4.

Parallel Reduction

Implement a program that sums up a range of numbers in parallel, using multiple threads. The general algorithmic problem is called “parallel reduction”.

In order to produce comparable solutions, your application should accept three command-line parameters in this order:

  • The number of threads to be used.
  • The start number of the range (inclusive).
  • The end number of the range (inclusive).

The program should perform a true parallelized computation with a flexible number of threads. Play with different thread counts and ranges, and try to answer the following questions for yourself:

  • What is the relation between the optimal thread count and my computer hardware ?
  • Does my CPU has hyperthreading enabled ? Is this relevant for the performance with different thread counts ?
  • Is it possible to develop a serial version of the program that is faster than my multithreaded solutions ?

Heatmap

heatdist.gif

Implement a parallel program that simulates heat distribution on a two-dimensional field. You can solve the problem by using threads in your favourite programming language. It is also possible (and recommended) to solve this excercise with OpenMP, which is  supported by all major compilers at this time.

The heatmap field is divided into equal-sized cells. Initially some of the cells are cold (value=0), some other cells are active hot spots (value=1). 

The simulation is executed in rounds. In each round, heat is transfered from every cell to its neigbor cells, which change their temperature value accordingly. The new value for each cell is computed by getting the last round values of the eight direct neighbor cells, and averaging them with the own cell value from the last round. The round is finished if all new cell values are computed.

Cells at the edges of the field have 'virtual' neighbor cells outside of the field, which should be treated as having the constant value 0.

When the round is finished, and all cell values are computed, the value of the hot spot cells may be set to 1 again, depending on their live time (see below). 

The goal of the implementation is to minimize the execution time of the complete simulation. In order to allow some comparison with other implementations, your application should accept five command-line parameters in this order:

  • The width of the field in number of cells.
  • The height of the field in number of cells.
  • The number of rounds to be simulated.
  • The name of a file (in the same directory) describing the hotspots.

The hotspot description file has the following structure:

  • The first line can be ignored.
  • All following lines describe one hotspot per line. The first two values indicate the cell position in the heat field (x, y), were position indexes start at zero. The hot spot is active from a start round (inclusive), which is indicated by the third value, to an end round (exclusive) that is indicated by the last value of the line. 

Example content of hotspots.csv:

x,y,startround,endround
5,2,0,20
15,5,5,15

Example run of the application:

./heatmap 20 7 17 hotspots.csv

With such an input file and the given command-line parameters, you have to run a simulation of 17 rounds on a 20x7 field with two hotspots. The first one is located at the coordinates (5, 2) and will be active from the first round to the last round. The second hotspot will be located at the coordinates (15, 5) and will be active starting from round 5. Starting from round 15, it will no longer be active.

The program has to produce an output file with the name “output.txt” in the same directory. This file represents the resulting field after simulation termination. The values in the field are encoded in the following way:

  • A block with a value larger than 0.9 has to be represented as “X”.
  • All other values must be increased by 0.09. From the resulting value, the first digit after the decimal point is added to the output picture. 

Example content of “output.txt” for the described input:

11112221111111111100
11123432111111111110
11124X42211111111111
11124442111111222111
11122222111112222211
11111211111112232211
01111111111111222111

While developing your solution, try to think about the following questions:

  • How can I determine the right level of parallelism ? Is it better to have many threads / tasks, maybe even more than cores, or to have only a few threads / tasks ?
  • What is the relationship between application performance and field size ?
  • What could be alternative ways to deal with the borders of the field ? Does that influence the parallelization performance ?
  • Given some operating system API to determine the number of cores in your system, could you automatically determine the right granularity of work distribution to tasks / threads ?
Go to overview