# Parallel Algorithm for Connected-Component Analysis Using CUDA
## 4 Results  
Figure 4 shows the execution times on the System A for the proposed tree merge kernel (TMK) compared to the HA4 algorithm. Benchmarks on the System B showed qualitatively similar results and are not shown. Note that the execution time for TMK includes generation and balancing of the tree, whereas the HA4 algorithm does not create a tree structure. Instead, the features array F is filled and transferred completely. The results show that the increased computational effort on the device, i.e., building and balancing the tree, yields an overall lower execution time due to the drastically reduced memory transfer time in most cases.  
Further, it can be seen that the tree merge kernels execution time scales with the total number of connected components rather than the number of foreground pixels, i.e., density. Hence, it performs worst for densities around 25% which yield the largest number of objects in the random images. Contrary, the tree merge algorithm remains unaffected by the percolation threshold around 60% which typically poses a bottleneck for CCA algorithms like HA4. This slowdown for algorithms like HA4 is a result of the sudden increase in object sizes at the percolation threshold. This leads to more conflicts between threads voting on  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Component** & \multicolumn{2}{c}{**Specification**} \\  & **System A** & **System B** \\ \hline \multirow{2}{*}{CPU} & AMD EPYC 7343 (16 \(\times\) & Intel Xeon E5-2637 (16 \(\times\) \\  & 3.9 GHz) & 3.5 GHz) \\ \multirow{2}{*}{GPU} & NVIDIA RTX 3080 (10 GB & NVIDIA GTX 1080 (8 GB \\  & VRAM) & VRAM) \\ Mainboard & Supermire H12 SSL-i & Fujitsu D3358-A1 \\  & 4 \(\times\) 32 GB Samsung & 8 \(\times\) 16 GB Samsung \\ \multirow{2}{*}{RAM} & M393 AAK40 DB3-CWE (DDR4, & M393A2G40 DB0-CPB (DDR4, \\  & 3200 MHz) & 2133 MHz) \\ OS & Ubuntu 20.04 (5.15.0-46-generic) & Ubuntu 20.04 (5.4.0-131-generic) \\ GCC & 10.3.0 & 10.10 \\ NVCC & 11.6 & 11.2 \\ CUDA driver & 510.47.03 & 460.73.01 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Benchmark system specifications.  
Figure 3: Examples of the used images from the YACCLAB dataset. White pixels are considered foreground pixels.  
the objects properties which need to be serialized. TMK, on the other hand, merges object properties non-atomically (as explained in Section 3.2.2(d)). Hence, it is not negatively effected by the increase in object size. Instead, TMK needs to perform atomic operations, i.e., potential serialization, when building the tree structure which becomes more expensive for larger numbers of objects.  
Regarding varying image sizes, the results reveal TMKs different effectiveness for small, medium and large image size. The average execution time with respect to the image size is shown in Figure 5. The portions of total execution time for each part of TMK are shown in Figure 6.  
For small image sizes (\(\leq\)128 px), the overhead for kernel launches is significant. Even though much of the tree merging is performed in shared memory, the overall computational effort outweighs the possible savings in memory transfer time.  
For medium image sizes (256 px to 1024 px), the TMK performs best due an increase in possible memory transfer savings whilst processing large portions of the tree merging in shared memory.  
For large image sizes (\(\geq\)2048 px), much of the tree merging must be performed using global memory. This significantly slows down execution. In total, the additional computation time required for the global memory merging outweighs the increased savings in memory transfer time.  
Figure 4: Comparison of execution time (System A) vs. density for different granularities g for images with 256 \(\times\) 256 pixels and 2048 \(\times\) 2048 pixels. Solid lines indicate total execution time (including cudaMemcpy). Dashed lines show the respective cudaMemcpy time for the feature array (device to host). Erobars are omitted for clarity (standard deviation \(<\) 3% in all cases).