Description
This assignment covers GPU Computing as an example for heterogeneous computing. The tasks have
to be implemented in C/C++ using OpenCL, targeting GPU compute devices. The executor nodes are
equipped with an integrated Intel Processor Graphics GPU (Gen8). Specific optimizations for the given
test machine are allowed as long as they deliver correct results on other GPUs.
General Rules
The assignment solutions have to be submitted at:
https://www.dcl.hpi.uni-potsdam.de/submit/
Our automated submission system is intended to give you feedback about the validity of your file
upload. A submission is considered as accepted if the following rules are fulfilled:
• You did not miss the deadline.
• Your file upload can be decompressed with a zip / tar decompression tool.
• Your submitted solution contains only the source code files and a Makefile for Linux.
Please leave out any Git clones, backup files or compiled executables.
• Your solution can be compiled using the “make” command, without entering a separate subdirectory after decompression.
• You program runs without expecting any kind of keyboard input or GUI interaction.
• Our assignment-specific validation script accepts your program output / generated files.
If something is wrong, you will be informed via email (console output, error code). Re-uploads of
corrected solutions are possible until the deadline.
50% must be solved correctly in order to pass each assignment. Documentation should be done
inside the source code.
Students can submit solutions either alone or as team of max 2 persons.
Operating Systems and Middleware Group, Hasso Plattner Institute, University of Potsdam
Task 3.1: Parallel Sum with OpenCL
Implement a program that sums up a range of numbers in parallel. The general algorithmic problem is
called “parallel reduction”.
Input
Your executable has to be named parsum and accept two parameters: The start index and the end
index (64bit numbers) of the range to compute. For example, the command line
Example: ./parsum 1 10000000000
has to result in a parallel summation of the numbers 1,2,…,10.000.000.000.
Output
Your program has to produce a single line on the standard output, that contains only the computed
sum.
Validation
The solution is considered correct if a true parallelized computation takes place (no Gauss please), and
if the application produces correct results for all inputs. We will evaluate your solution with different
summation ranges.
Task 3.2: Heat Map with OpenCL
Implement a program that simulates heat distribution on a two-dimensional field. The simulation is
executed in rounds. The field is divided into equal-sized blocks. Initially some of the blocks are cold
(value=0), some other blocks are active hot spots (value=1). The heat from the hot spots then transfers
to the neighbor blocks in each of the rounds, which changes their temperature value.
The new value for each block per round is computed by getting the values of the eight direct
neighbor blocks from the last round. The new block value is the average of these values and the own
block value from the last round. Blocks on the edges of the field have neighbor blocks outside of the
fields, which should be considered to have the value 0. When all block values are computed in a
round, the value of the hot spot fields may be set to 1 again, depending on the live time of the hot
spot during a given number of rounds.
You have to develop a parallel application for this simulation in C or C++, which only uses OpenCL and
targets GPU compute devices. Additional OpenCL math libraries are not allowed. The goal is to
minimize the execution time of the complete simulation. Specific optimizations for the given test
machine are allowed as long as they do not result in erroneous computations on other GPUs..
Input
Your executable has to be named heatmap and needs to accept five parameters:
• The width of the field in number of blocks.
• The height of the field in number of blocks.
• The number of rounds to be simulated.
• The name of a file (in the same directory) describing the hotspots.
Operating Systems and Middleware Group, Hasso Plattner Institute, University of Potsdam
• Optional parameter: The name of a file (in the same directory) containing coordinates. If it is
passed, only the values at the indicated coordinates (starting at (0, 0) in the upper left corner)
are to be written to the output file.
Example: ./heatmap 20 7 17 hotspots.csv
./heatmap 20 7 17 hotspots.csv coords.csv
The hotspots 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 position in
the heat field (x, y). 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 hotspots.csv: Example coords.csv:
x,y,startround,endround x,y
5,2,0,20 5,2
15,5,5,15 10,5
Output
The program must terminate with exit code 0 and has to produce an output file with the name
output.txt in the same directory.
If your program was called without a coordinate file, then this file represents the resulting field after
the simulation terminated. Each value in the field is encoded the following way:
• A block with a value larger than 0.9 has to be represented as “X”.
• All other values are incremented 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 without coordinate file
11112221111111111100
11123432111111111110
11124X42211111111111
11124442111111222111
11122222111112222211
11111211111112232211
01111111111111222111
If your program was called with a coordinate file, then this file simply contains a list of exact values
requested through the coordinate file.
Example content of output.txt with coordinate file
1.0
0.03056341073335933
Operating Systems and Middleware Group, Hasso Plattner Institute, University of Potsdam
Task 3.3: Decrypt with OpenCL
Develop an OpenCL-based command line tool that performs a brute-force dictionary attack on Unix
crypt(3) passwords. An example password file to be attacked is available at:
https://www.dcl.hpi.uni-potsdam.de/teaching/parProg/assignments/taskCryptPw.txt
Each line of the password file contains the username and the encrypted password, separated by the
character “:”. Your program can use the example dictionary file available at:
https://www.dcl.hpi.uni-potsdam.de/teaching/parProg/assignments/taskCryptDict.txt
One of the users has a password exactly matching one dictionary entry. A second user has a
password build from one of the dictionary entries plus a single number digit (0-9) attached, e.g.
“Abakus5”.
Please note that the first two characters of the encrypted password string in taskCryptPw.txt are the
salt string used in the original encryption process. A correct solution therefore splits the encrypted
password string into salt and encryption payload, calls your OpenCL-based crypt(3) implementation
with the salt and all of the dictionary entries, and checks if one of the crypt results matches with an
entry from the user list.
Input
Your executable “decrypt” has to take two arguments: the name of the password file as the first and
the name of the dictionary file as the second command line argument.
Example: ./decrypt ../taskCryptPw.txt ../taskCryptDict.txt
Output
The program must terminate with exit code 0 and print a line by line a list of the successfully cracked
combinations of username and decrypted password, both separated by semicolon:
User01;pass
User02;Abakus5
(This is not the solution). Submit a compressed archive with the OpenCL sources. Additionally, the
archive can also contain a file named “taskCryptSolution.txt” with the cracked users for the above
example data (include a trailing new-line). In this case the validation step will tell you if you found the
right ones. The validation machine will not crack the example data, since this may take several hours.