Parallelization of Connected-Component Labeling on TILE64 Many-Core Platform

Many-core technology is considering as a key to improve the performance of recent computer systems. To obtain good performance for a many-core system, exploiting parallelism in arithmetic level is not enough and the parallelization strategy must apply to both of hardware architecture and software. Due to the contention of shared hardware resource, the speedup ratio of a many-core system is usually much lower than the number of processor units. In this paper, we take connected-component labeling (CCL) as a data-intensive application and take TILE64 as a many-core platform to perform a fast linear-time two-scan algorithm for labeling connected components in grayscale-level images. In the first scan, the data partition parallelism is applied and each core in the many-core system assigns provision labels (PLs) to the object pixels in a sub-image and collects equivalence information to several tables. Two parallel modes, the cascade path mode and tree path mode developed for the second scan, when the representative labels (RLs) with the help of equivalence information replace the PLs. According to the experimental results, the 10 times of speedup, compared with the performance of the single core scenario, it is can be achieved when 32 processor units is activated. The experimental results also demonstrate that the efficiency of our implementation with TILE64 is superior to that of other parallel labeling platforms.