## 3 Reference Implementations on CPU and GPU  
For further comparisons, we also performed software-based CPU and OpenCL-based GPU implementations of the Hamming distance calculation. The performance of both implementations is listed in Table 2. Both implementations were optimized for the calculation of 512-bit signatures and all performance tests were performed using one million static and ten million dynamic, randomly generated 512-bit signatures.  
The software implementation of the Hamming distance calculation for CPUs is realized using C++. It was optimized for and build with the GCC (GNU Compiler Collection). First, an unoptimized straight-forward implementation was developed, which achieved a quite low performance of 2.8 MH/s. Therefore, in the next step, different optimizations were applied to the code to improve the performance. These optimizations ranged from compiler flags to improved function access (pass by reference instead of pass by value) to the use of the processor's AVX (Advanced Vector Extensions) and SSE (Streaming SIMD Extensions) instruction sets in combination with OpenMP (Open Multi-Processing) to achieve maximum parallelism. On an Intel E3-I505M v6 [33] CPU with a clock speed of 3.0 GHz and eight threads the fully optimized implementation achieved a performance of 868 MH/s.  
For the GPU, an OpenCL-based implementation was designed and executed on an NVIDIA GTX 1060. By using an nd-range kernel in combination with loop unrolling (processing multiple iterations of a loop simultaneously instead of sequentially), the GPU design achieved a high degree of parallelism. The 512-bit Hamming distance calculations were performed using OpenCLs _vector data types_[34] in combination with the population count function provided by OpenCL. Before the  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Design** & **Bit Width** & **Clock Frequency (1)** & **Throughput (2)** \\ \hline \multirow{3}{*}{LUT-based [30]} & 16 & 400 MHz & 6.40 GBit/s \\  & 256 & 166 MHz & 42.50 GBit/s \\  & 512 & 125 MHz & 64.00 GBit/s \\  & 1024 & 110 MHz & 112.60 GBit/s \\ \hline \multirow{3}{*}{DSP-based [31]} & 16 & 476 MHz & 7.62 GBit/s \\  & 256 & 133 MHz & 34.13 GBit/s \\ \cline{1-1}  & 512 & 108 MHz & 55.05 GBit/s \\ \cline{1-1}  & 1024 & 91 MHz & 93.94 GBit/s \\ \hline LUT \& DSP-based [32] & 2\({}^{20}\) & 4.4 MHz (3) & 4.65 TBit/s \\ \hline \hline \end{tabular} \({}^{(1)}\) Based on maximum combinational path delays. \({}^{(2)}\) Theoretical maximum throughput in counted bits per second. \({}^{(3)}\) Frequency at which results can be calculated by the design, calculated from the values provided in the publication.  
\end{table}
Table 1: Comparison of three FPGA implementations to determine population counts. All designs leverage only one computation unit.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Platform** & **Throughput** & **Parallelism** & **System** & **Power** & **Energy Eff.** \\ \hline CPU (ANSI C) [27] & 167 MH/s (1) & - & AMD Opteron & - & - \\ CPU (C++) & 868 MH/s & 8 Thr., AVX/SSE & Intel E3-1505M v6 & 56.05 \(W\) (2) & 15.49 MH/s/W \\ GPU (OpenCL) & 15.46 GH/s & loopunrolling & NVIDIA P100 & 69 W (3) & 224.06 MH/s/W \\ \hline \hline \end{tabular} \({}^{(1)}\) With 64-bit signature length. \({}^{(2)}\) From Datasheet [33]. \({}^{(3)}\) Measured using NVIDIA SMI.  
\end{table}
Table 2: Overview of CPU and GPU Implementations.  
calculation starts all data is transferred to the GPUs attached DDR-memory from where it is read by the kernel. During the calculation of the Hamming distances, the average power consumption of the GPU was 69 Watt (measured with the SMI tool provided by NVIDIA). When looking at the performance, the GPU implementation achieved 15.46 GH/s (Giga Hamming distance operations per second) thus significantly outperforming the CPU implementation. To measure the actual performance, data transfer times from host to device and back were included.