# Heterogeneous Distributed Big Data Clustering on Sparse Grids
## 5 Implementation
### Node-Level Implementation  
Except for the connected component detection, all steps of the clustering algorithm have been implemented as OpenCL kernels. There are two OpenCL kernels for the density estimation: one for calculating the right-hand side and one for the matrix-vector multiplication. A third OpenCL kernel implements the \(k\)-nearest-neighbor graph creation and a fourth kernel implements the density-based graph pruning. From a performance engineering perspective, these OpenCL kernels have some commonalities. All kernels were parallelized over the outermost loop, exploiting the fact that the loop iterations are independent. Furthermore, all OpenCL kernels were designed to be branch-free with regard to their critical innermost loops. The only exception is the density matrix-vector multiplication kernel that has a single branch in the innermost loop. This branch is implemented using the OpenCL _select_ function to differentiate between the integration cases. On modern OpenCL platforms, this should be compiled to a conditional move. Because only standard arithmetic is used and because of the regular control flow, the four computed kernels get vectorized on all OpenCL platforms we tested. Due to the design of the computed kernels, we expect this to be the case on many untested OpenCL platforms as well. The local memory is used in all kernels to either share grid points or data points between all threads of the work-group. For example, the prune graph kernel evaluates 1-D sparse grid basis functions in its innermost loop. The threads of a work-group process different data points, but all always evaluate their data point with the same basis function. Therefore, the data of the currently processed basis function can be shared efficiently through the local memory. Furthermore, the data point assigned to a thread remains constant throughout the lifetime of the thread. It can therefore be stored in _private_ memory, which translates to the register file on GPU devices and the L1 cache (or the registers) on processors. Table 1 shows the number of floating-point operations for the different OpenCL kernels. As both the number of grid points \(N\) and the size of the dataset \(m\) can be large, all operations are potentially expensive. In most data mining scenarios, the sparse grid will have significantly fewer grid points than there are data points. Therefore, the \(k\)-nearest-neighbor graph creation is expected to be the most expensive operation. Depending on the number of CG iterations, the density matrix-vector product can be moderately expensive as well. However, it only depends on the grid points and therefore, benefits from \(N<m\). To estimate the achievable performance of our computed kernels, we calculated the arithmetic intensities of our computed kernels. As Table 1 shows, the arithmetic intensities of a work-group with a single thread would be too low to achieve a significant fraction of the peak performance on modern hardware platforms (see Table 2 for the machine balances of the hardware platforms we used). \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Kernel** & **FP Ops./Complexity** & **Arith. Int. (ws = 1)** & **Arith. Int. (ws = 128)** & **Peak Lim. (\%)** \\ \hline density right-hand side & \(N\cdot m\cdot d\cdot 6\) & 1.5 F B\({}^{-1}\) & 192 F B\({}^{-1}\) & 67\% \\ density matrix-vector & CG-iter. \(N^{2}\cdot d\cdot 14\) & 1.2 F B\({}^{-1}\) & 149 F B\({}^{-1}\) & 64\% \\ create graph & \(m^{2}\cdot d\cdot 3\) & 1.0 F B\({}^{-1}\) & 129 F B\({}^{-1}\) & 83\% \\ prune graph & \(m\cdot N\cdot(k+1)\cdot d\cdot 6\) & 4.5 F B\({}^{-1}\) & 576 F B\({}^{-1}\) & 67\% \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The number of floating-point operations for the different OpenCL kernels and the arithmetic intensities (in floating point operations per byte) for a work-group size (ws) of one thread and 128 threads. The peak limit states the achievable fraction of the peak performance given the instruction mix of the computed kernels.