Efficient Histogram Algorithms for NVIDIA CUDA Compatible Devices
Ramtin Shams, Rodney A. Kennedy · 2007
Abstract — We present two efficient histogram algorithms designed for NVIDIA’s compute unified device architecture (CUDA) compatible graphics processor units (GPUs). Our algorithm can be used for parallel computation of histograms on large data-sets and for thousands of bins. Traditionally histogram computation has been difficult and inefficient on the GPU. This often means that GPU-based implementation of the algorithms that require histogram calculation as part of their computation, require to transfer data between the GPU and the host memory, which can be a significant bottleneck. Our algorithms remove the need for such costly data transfers by allowing efficient histogram calculation on the GPU. We show that the speed of histogram calculations can be improved by up to 30 times compared to a CPU-based implementation. Index Terms — Histogram, Parallel processing, Compute unified device architecture (CUDA), Graphics processor unit (GPU) implementation of certain algorithms (even trivial ones) on the GPU may be difficult or may not be computationally justified. Histogram has been traditionally difficult to compute efficiently on the GPU [4]. Lack of an efficient histogram method on the GPU, often requires the programmer to move the data back from the device (GPU) memory to the host (CPU), resulting in costly data transfers and reduced efficiency. A simple histogram computation can indeed become the bottleneck of an otherwise efficient application. Currently, there is only one efficient histogram method available for CUDA compatible devices [4]. The histogram is limited to 64 bins, which is too small for many real-life applications. For example, 2D histogram calculations used in estimating the joint pdf of pixel intensities, commonly used in mutual information ([5])-based image registration methods (e.g. [6], [7], [8], [9], [10]), typically require in the order of 10, 000 bins. I.