Almost optimal column-wise prefix-sum computation on the GPU
Almost optimal column-wise prefix-sum computation on the GPU
复制标题
DOI：
10.1007/s11227-018-2242-8
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Hiroki Tokura;Toru Fujita;K. Nakano;Yasuaki Ito;J. Bordim
中科院分区：
文献类型：
--
作者：
Hiroki Tokura;Toru Fujita;K. Nakano;Yasuaki Ito;J. Bordim
矩阵的行和列前缀和计算在图像处理领域有许多应用，例如求和面积表和欧氏距离图的计算。众所周知，一维数组的前缀和可以在GPU上高效地计算。因此，矩阵的逐行前缀和也可以在GPU上通过对每行并行执行该前缀和算法来高效地计算。然而，由于执行对全局存储器的低效步幅存储器访问，相同的方法不能很好地用于计算列式前缀和。本文的主要贡献是提出了一个几乎最优的列前缀和算法在GPU上。令人惊讶的是，使用NVIDIA TITAN X的实验结果表明，我们的列前缀和算法运行速度仅比矩阵复制慢2-6%。因此，我们的列前缀和算法几乎是最优的。
Row-wise and column-wise prefix-sum computation of a matrix has many applications in the area of image processing such as computation of the summed area table and the Euclidean distance map. It is known that the prefix-sums of a one-dimensional array can be computed efficiently on the GPU. Hence, row-wise prefix-sums of a matrix can also be computed efficiently on the GPU by executing this prefix-sum algorithm for every row in parallel. However, the same approach does not work well for computing column-wise prefix-sums due to inefficient stride memory access to the global memory is performed. The main contribution of this paper is to present an almost optimal column-wise prefix-sum algorithm on the GPU. Quite surprisingly, experimental results using NVIDIA TITAN X show that our column-wise prefix-sum algorithm runs only 2–6% slower than matrix duplication. Thus, our column-wise prefix-sum algorithm is almost optimal.