NPRG042 Programming in Parallel Environment

Assignment 2

---

---

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

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

1. Each point is assigned to its nearest cluster, i.e., the cluster whose centroid is nearest in the Euclidean metric. If multiple cluster centroids 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 the average of all assigned points (computed per dimension). The task expects integer arithmetic to be used (i.e., all operations, including the division, are computed using integers). If a cluster has no points assigned to it (and thus computing a new centroid would result in a division-by-zero error), the centroid should be preserved (no new centroid should be computed).

The number of points is 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 differences (Euclidean distance), will fit into a signed 64-bit integer.

Your solution must use a framework, which is also available at /home/_teaching/para/02-kmeans (the ZIP archive contains only debugging data; testing data are available on parlab). Your solution is expected to modify only the implementation.hpp file of the framework, while preserving 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 expected to submit to ReCodEx. If you need to create additional headers (*.hpp), submit them as well, but you cannot create any subdirectories (and they must not collide with any of the names in the framework).

Use the attached Makefile for compilation. There are also build.sh and run.sh script wrappers that can be used with the sbatch command. When debugging, the KMeans class has a bool template parameter DEBUG. When the program is called with a -debug argument, the debugging version of the class is used. You may use it to print debugging information, but make sure that the regular (non-debug) version does not print anything to stdout.

Your solution will be tested on datasets different from those provided to you. However, the evaluation data will be of the same size. The K used for testing will be selected to be rather high withing the specified range (i.e., you do not have to optimize for a very small K, such as less than 10).