# Parallel Algorithm for Connected-Component Analysis Using CUDA
## 5 Discussion  
Our investigations have shown that the proposed tree merge kernel (TMK) reduces overall execution times for connected component analysis when taking into account transfer times between device and host. It performs best for medium image sizes (256 px to 1024 px). For larger images, total execution time is similar to HA4 due to TMKs increasing dependency on global memory accesses. Still, required memory bandwith is drastically reduced when compared to naively transferring the (typically sparse) object features array from the device. This advantage is even more pronounced for images with larger granularity, i.e., less objects in total. Contrary, mere feature calculation using TMK is slower than HA4 for most cases, with noteworthy exceptions for image densities around the percolation threshold.  
Figure 5: Mean total execution time for different image sizes. Mean is computed by averaging the total execution time for images with densities from 10% to 90% and granularity 1. Errorbars are omitted for clarity (standard deviation < 3% in all cases).  
Figure 6: Fraction of kernel execution time for different image resolutions. Respective execution times are extracted using nsys. Overhead is calculated as remaining time between the sum of kernel execution times and total execution time, i.e., from start of the first kernel to the end of the final memcpy.  
For future work, it may be worthwhile combining the advantages of both approaches in an algorithm which can quickly perform CCA (e.g., HA4) followed by compression of the features array before transfer to the host.  
Conceptualization, D.W. and C.K.; methodology, D.W. and C.K.; software, D.W. and C.K.; validation, D.W. and C.K.; formal analysis, D.W.; investigation, D.W.; resources, G.J. and A.B.; data curation, D.W.; writing--original draft preparation, D.W.; writing--review and editing, A.B. and G.J.; visualization, D.W.; supervision, A.B.; project administration, D.W. and A.B.; funding acquisition, A.B. and G.J. All authors have read and agreed to the published version of the manuscript.  
This research was funded by Deutsche Forschungsgemeinschaft under grant number HA 3088/26-1.  
Publicly available software and data was analyzed in this study. The source code can be found here: [[https://codebase.helmholtz.cloud/risa](https://codebase.helmholtz.cloud/risa)]([https://codebase.helmholtz.cloud/risa](https://codebase.helmholtz.cloud/risa)) (accessed on 27 January 2023). The dataset used for the benchmarks (\"YACCLAB\") can be found here: [[https://github.com/prittt/YACCLAB](https://github.com/prittt/YACCLAB)]([https://github.com/prittt/YACCLAB](https://github.com/prittt/YACCLAB)) (accessed on 6 October 2022). The subset \"random/granularity\" was used for Figure 4. For analysis of 256 px images, only the top-left 256 \(\times\) 256 px region was used. The subset \"random/classical\" was used for Figures 5 and 6.  
The authors declare no conflict of interest.  
The following abbreviations are used in this manuscript:  
\begin{tabular}{l l} CCA & Connected-Component Analysis \\ CUDA & Compute Unified Device Architecture \\ FPS & Frames Per Second \\ GPU & Grapical Processing Unit \\ HA4 & Hardware Accelerated 4-connected \\ OPS & Object Feature Struct \\ RISA & Real-time Image Stream Algorithms \\ TMK & Tree Merge Kernel \\ UFXCT & Ultrafast electron beam X-ray Computed Tomography \\ \end{tabular}