An Optimal Parallel Algorithm for Computing the Summed Area Table on the GPU
Yutaro Emoto, Shunji Funasaka, Hiroki Tokura, Takumi Honda, Koji Nakano, Yasuaki Ito · 2018
The summed area table (SAT) of a matrix is a data structure frequently used in the area of computer vision, which can be obtained by computing the column-wise prefix-sums and then the row-wise prefix-sums. The main contribution of this paper is to present a very efficient parallel algorithm for computing the SAT of a matrix stored in the global memory of the GPU. Our new parallel algorithm uses two techniques, single kernel soft synchronization and look back techniques to compute the SAT efficiently. It performs approximately one read and one write operations per element to the global memory. Since all elements in the matrix must be read once, and those in the resulting SAT must be written, any SAT computation cannot be faster than duplication of the matrix in the global memory. Thus, our algorithm is theoretically optimal in terms of global memory access. We have implemented our parallel algorithm and previously published algorithms for computing the SAT to run on NVIDIA TITAN V GPU. Our parallel SAT algorithm runs faster than all previous algorithms for matrices of sizes from256× 256 to 32K× 32K. Also, the overhead ratio over matrix duplication can be only 5.7%, so it is also practically optimal.