#1 K-means Clustering

Write an implementation of k-means clustering algorithm using Intel Threading Building Blocks technology. The algorithm gets input points in a plane (R ²), the number of clusters K, and the number of iterations. It returns coordinates of the cluster centroids, and the assignment of the points after the last iteration.

The algorithm works as follows. As an initialization, the first K points are taken as the initial set of cluster centroids. After that, the algorithm performs prescribed number of iteration, whilst each iteration consists of the following steps:

1. Each point is assigned to its neares cluster -- i.e., the cluster which has its centroid nearest by the Euclidean metrics. In case there are multiple clusters with centroids that are equidistant from the point being assigned, the cluster with the lowest index is considered the closest one.
2. A new centroid is computed for each cluster. The centroid is in fact an average of all assigned points (computed per dimension). The task expects that integer arithmetics is used (i.e., all operations including the division is computed on integers). In case that a cluster has no points assigned to it (and thus computing new centroid will result in zero division error), the centroid should be preserved (no new centroid shall be computed).

The number of points are divisible by 1,024 and the number of clusters K will not exceed 256 (clusters are indexed from 0). All points will fit in RAM and the sum of all point coordinates in one dimension as well as the sum of squares of coordinate diferences (Euclidean distance) will fit into signed 64-bit integer.

Your solution must use a framework, which is available for you at /mnt/home/_teaching/para/01-kmeans (including the testing data, data generator, and serial implementation). Your solution is expected to modify only the implementation.hpp file of the framework while you have to preserve the name of the implementation class ( KMeans ) and it must implement the interface IKMeans . The modified file implementation.hpp is also the only file you are expect to submit into your submit_box directory. If you need to create additional headers ( *.hpp ), add them to you submit box as well, but do not create any subdirectories.

Use the attached Makefiles for compilation. When debugging, the KMeans class has a bool template parameter DEBUG . When the program is called with -debug argument, the debugging version of the class is used. You may use it to print out debugging information, but make sure that the regular (non-debug) version is not printing anything to the stdout.

Your solution will be tested on different datasets than you are provided. However, the evaluation data will be of the same size. The small partition (w2xx workers) will be used to measure the speedup.

#2 Levenshtein's Edit Distance

Design and implement a parallel algorithm for computing Levenshtein's Edit Distance using the OpenMP technology.

Your solution must use a framework, which is available for you at /mnt/home/_teaching/para/02-levenshtein (including the testing data, data generator, and serial implementation). Your solution is expected to modify only the implementation.hpp file of the framework while you have to preserve the name of the implementation class (EditDistance). The modified file implementation.hpp is also the only file you are expect to submit into your submit_box directory. If you need to create additional headers (*.hpp), add them to you submit box as well, but do not create any subdirectories.

Use the attached Makefiles for compilation. When debugging, the EditDistance class has a bool template parameter DEBUG. When the program is called with -debug argument, the debugging version of the class is used. You may use it to print out debugging information, but make sure that the regular (non-debug) verision is not printing anything to the stdout.

Your solution will be tested on diffrent datasets than you are provided. However, the evaluation data will use the same string lengths as the testing data. We recommend designing your performance-optimized solution to expect that the string lengths are divisible by 1,024 (but note that debugging data are much smaller).

#3 Physical Simulation in CUDA

The third assignment is to implement a physical simulation based on given model specification described in a separate document (Czech, English). The simulation is about simple particle mechanics based on forces and velocities. Unlike the other assignments, this one will be developed and tested on our GPU-lab (front server is gpulab.ms.mff.cuni.cz and it is accessible for you in the same manner as parlab).

Your solution must use a framework, which is available for you at /mnt/home/_teaching/para/03-potential (including the testing data and serial implementation). Your solution is expected to modify only the implementation.hpp, kernels.h, and kernels.cu. These are also the only files you are supposed to leave in your submit box. The implementation class (ProgramPotential) must be preserved and it must implement the interface IProgramPotential.

The compilation is a bit tricky as we need to combine pure-C++ code with CUDA code. You may use CUDA runtime functions in the implementation.hpp (e.g., for memory allocation and transfers), but kernels and their invocation has to be placed in kernels.cu. Each kernel should be provided with a pure-C function wrapper which invokes it (see my_kernel kernel and its run_my_kernel wrapper). We recommend not using templates (even though the interface is designed in that way). Your solution will be tested only with double precision floats (coordinates) and 32bit unsigned integers (indices).

Your solution is expected to perform the following changes in the implementation file:

1. The virtual function initialize() is designed to initialize (allocate) the memory buffers. You may also copy input data (like edges) to the GPU or initialize the velocities to zero vectors.
2. The virtual function iteration(points) should implement the computation performed in each iteration of the simulation. The function updates the velocities and moves the points according to them. This function is called as many times as many iterations the simulation has to perform. Furthermore, the API guarantees that every iteration call (starting from the second iteration) is given the points vector yielded by its previous call. In other words, you may cache the point positions (or any related data) at the GPU(s).
3. The virtual function getVelocities() is expected to retrieve the internal copy of the point velocities. This function is invoked for verification only and it does not have to be efficient (its execution time will not be added to the overall measured time).

All the parameters of the model are set to the member variables of the ProgramPotential object before the initialize() function is called. The member variable mVerbose indicates whether the application was launched with "-verbose" argument. If so, you may print out debugging or testing output without any penalizations. Otherwise, your implementation must not perform any output to the stdio nor to the stderr. Criticall errors should be reported by throwing UserException. Cuda errors may be reported by throwing CudaError exception (you may conveniently use CUCH macro).

The framework tests the solution and prints out the measured times. The first value is the time of the initialization and the second value is an average time of an iteration (both in milliseconds). The initialization time is not considered for the speedup evaluation. Your solution will be tested on different data than you are provided, but we will use the same numbers of vertices and edges. The verification process will be performed separately to the time measurements; thus, it will not influence the performance. All tests will be pefromed using the initial simulation parameters (see potential.cpp).

Supplied makefile may be used for compilation. Do not forget, that the code has to be compiled at workers. The SLURM partitions are named volta-hp (high priority) and volta-lp (low priority) on GPU lab. For allocating the GPUs on the workers, you need to pass a general resources request parameter to srun:
$> srun -p volta-hp --gres=gpu:1
Use gpu:2 gres value if you want to implement your solution for two GPUs (be aware that no worker has currently more than 2 GPUs).

#4 MPI Matrix Multiplication

Write a MPI program, which will perform a matrix multiplication. Source matrices can be too large to fit into a one node memory. Resulting matrix will fit into a one node memory. No other technology should be used, only vectorization instructions (SSE, AVX) are allowed. Files for source and result matrices are available only at rank #0. The program accepts three command line parameters, first two parameters are source matrices, the third one is the resulting matrix.

We have prepared some testing data and programs. They are placed in /mnt/home/_teaching/para/04-matrixmul-mpi/exec. generator generates a matrix. comparator compares two matrices. multiply is a serial version of matrix multiplication.

In this assignment, you are expected to submit an executable file named du4, which does not depend on any external library (like boost::mpi). Only the libraries which are generally available on all parlab workers can be used. The executable must be built using mpicxx/mpicc on workers.

Matrix file format

It is a binary format. First two 4-bytes integer numbers are C(olumns) and R(ows), followed by R*C floating point numbers in the IEEE 754 single precision format (float). The format is row-based, i.e. all elements from one row are in a sequence, followed by the next row.

Testing environment

The environment is slightly different from previous assignments. Testing matrices are placed in /mnt/home/_teaching/para/04-matrixmul-mpi/data. The program is executed using the following command line:

srun -n $N_PROC -N $N_HOSTS -p $PART -c 2 -m cyclic -t $TIMEOUT du4 $INPUT_FILE_A $INPUT_FILE_B $OUTPUT_FILE_R

where $N_PROC=256, $N_HOSTS=8, $PART=small-hp, and $TIMEOUT=20 (min). $INPUT_FILE_A, $INPUT_FILE_B, and $OUTPUT_FILE_R are replaced by corresponding matrices in data directory.

#5 C# .NET Async Programming

The objective is to write recursive DNS resolver in C# .NET Core using already implemented methods for individual DNS queries. Of course, all network operations will be simulated by mocks. And since the DNS problem is rather complex, we have simplified it significantly for the purposes of this assignment:

• Each known domain has exactly 1 IPv4 address. Different domains have different addresses.
• There is no difference between the server and its nameserver (we do not distinguish any record types A, NS, CNAME...).
• Server holding domain X is the only authority which can answer queries for immediate sub-domains of X (i.e., if one needs to resolve mff.cuni.cz, one must first resolve cuni.cz and then ask it for address of mff).
• Root servers are well known (you will get a list of IPs).
• There is no additional trickery (like CNAMEs), domains are simple identifiers separated by dots.

Your implementation will get an object implementing IDNSClient interface. The interface will provide the following methods:

• IReadOnlyList<IP4Addr> GetRootServers() - will give you the list of root server IPs
• Task<IP4Addr> Resolve(IP4Addr server, string subDomain) - perform single resolving (you can ask specific server for immediate subdomain)
• Task<string> Reverse(IP4Addr server) - performs reverse translation (will give you full domain name of IP address); this might be handy if you implement some sort of cache and you need to quickly find out whether an IP address is still valid

Your job is to implement class with IRecursiveResolver interface, which has only one method - Task<IP4Addr> ResolveRecursive(string domain). This method gets full domain name and yields its address. File Serial.cs holds trivial implementation of the resolver. Your codes goes into Solution.cs file, which is also the only file you need to submit.

All the interfaces yield Tasks, which might suggest your course of action. Besides low-level tasks, you may also employ async/await approach. The main objective is to use parallelism to lower (average) query latency and increase throughput.

I would suggest implementing the following optimizations: First, when two similar queries are executed simultaneously (e.g., mff.cuni.cz and ff.cuni.cz) the common part may be resolved only once. If can save time by saving resources and it may reduce latency of the query which was started later. Second, you may use whatever caching you deem necessary, but beware that the addresses may change in time. Therefore, you need to verify data from cache (e.g., by reverse translation) before yielding the result.

On the other hand, it is expected that you will not employ any hacking techniques or aggressive methods that might work in real world. E.g., you are forbidden from trying guessing IP addresses of server or scanning the entire IP range.

All parlab workers have .NET Core 3.1 installed. The initial solution is in /mnt/home/_teaching/para/05-dns-netcore You may compile it using dotnet command:
$> dotnet build -c Release ./dns-netcore.sln
The compiled binary will appear in ./bin subdir. Remember you need to start both the compilation and the job itself using SLURM on one of the workers.

Final remarks: This assignment is still experimental and it is somewhat different from other assignments. Therefore, we have not set any official scoring tables or rules yet. We will tune these things based on your results to ensure fair evaluation.