Implementations of a Parallel Algorithm for Computing Euclidean Distance Map in Multicore Processors and GPUs
Implementations of a Parallel Algorithm for Computing Euclidean Distance Map in Multicore Processors and GPUs
复制标题
计算欧氏距离图的并行算法在多核处理器和 GPU 上的实现
DOI：
10.15803/ijnc.1.2_260
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
K. Nakano
中科院分区：
文献类型：
--
作者：
Duhu Man;K. Uda;Hironobu Ueyama;Yasuaki Ito;K. Nakano
给定尺寸Na的2-D二进制图像，Euclidean距离图（EDM）是相同大小的2-D阵列，因此每个元素都将欧几里得距离存储到最近的黑色像素。算法可以计算O（N2）中的EDM，因此该算法也是最佳的，但已提出了共享存储器模型的最佳平行算法。在现有的共享存储器并行计算机中实现。具有四个Intel六核处理器的Linux服务器（Intel Xeon X7460 2.66GHz）。 Tesla C1060和GTX 480分别。实验结果表明，对于9216a -9216的输入二进制图像，我们在多核心系统中的实现可实现18在同一系统中，对于相同的输入二进制图像，我们对GPU的实现在顺序算法实现上实现了26个。
Given a 2-D binary image of size nA—n, Euclidean Distance Map (EDM) is a 2-D array of the same size such that each element is storing the Euclidean distance to the nearest black pixel. It is known that a sequential algorithm can compute the EDM in O(n2) and thus this algorithm is optimal. Also, work-time optimal parallel algorithms for shared memory model have been presented. However, the presented parallel algorithms are too complicated to implement in existing shared memory parallel machines. The main contribution of this paper is to develop a simple parallel algorithm for the EDM and implement it in two different parallel platforms: multicore processors and Graphics Processing Units (GPUs). We have implemented our parallel algorithm in a Linux server with four Intel hexad-core processors (Intel Xeon X7460 2.66GHz). We have also implemented it in the following two modern GPU systems, Tesla C1060 and GTX 480, respectively. The experimental results have shown that, for an input binary image with size of 9216A—9216, our implementation in the multicore system achieves a speedup factor of 18 over the performance of a sequential algorithm using a single processor in the same system. Meanwhile, for the same input binary image, our implementation on the GPU achieves a speedup factor of 26 over the sequential algorithm implementation.