Load Balancing versus Occupancy Maximization on Graphics Processing Units: The Generalized Hough Transform as a Case Study

Abstract

Programs developed under the Compute Unified Device Architecture obtain the highest performance rate, when the exploitation of hardware resources on a Graphics Processing Unit (GPU) is maximized. In order to achieve this purpose, load balancing among threads and a high value of processor occupancy, i.e. the ratio of active threads, are indispensable. However, in certain applications, an optimally balanced implementation may limit the occupancy, due to a greater need for registers and shared memory. This is the case of the Fast Generalized Hough Transform (Fast GHT), an image-processing technique for localizing an object within an image. In this work, we present two parallelization alternatives for the Fast GHT, one that optimizes the load balancing and another that maximizes the occupancy. We have compared them using a large amount of real images to test their strong and weak points and we have drawn several conclusions about under which conditions it is better to use one or the other. We have also tackled several parallelization problems related to sparse data distribution, divergent execution paths, and irregular memory access patterns in updating operations by proposing a set of generic techniques, including compacting, sorting, and memory storage replication. Finally, we have compared our Fast GHT with the classic GHT, both on a current GPU, obtaining an important speed-up.

Keywords

compute unified device architecture generalized Hough transform graphics processing unit load balancing occupancy

References

Ballard, D.H. ( 1981). Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognit. 13(2): 111-122.

Billeter, M. , Olsson, O. and Assarsson, U. ( 2009). Efficient stream compaction on wide SIMD many-core architectures . In Proceedings of Conference on High Performance Graphics (HPG’09), pp. 159-166.

Canny, J. ( 1986). A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8(6): 679-698.

Cudpp (2010). CUDA Data Parallel Primitives Library home page, http://code.google.com/p/cudpp

Dotsenko, Y. , Govindaraju, N.K. , Sloan, P.-P. , Boyd, C. and Manferdelli, J. ( 2008). Fast scan algorithms on graphics processors. In Proceedings of 22nd International Conference on Supercomputing (ICS’08), pp. 205-213.

Duda, R.O. and Hart, P.E. ( 1972). Use of the Hough transform to detect lines and curves in pictures. Commun. ACM 15(1): 11-15.

Gómez-Luna, J. , González-Linares, J.M. , Benavides, J.I. and Guil, N. ( 2009). Parallelization of a video segmentation algorithm on CUDA-enabled Graphics Processing Units. In Proceedings of 15th International Euro-Par Conference (Euro-Par’09) , pp. 924-935.

Green, S. ( 2007). CUDA particles, http://developer.nvidia.com/object/cuda_sdk_samples.html

Guil, N. , González-Linares, J.M. and Zapata, E.L. ( 1999). Bidimensional shape detection using an invariant approach . Pattern Recognit. 32(6): 1025-1038.

10.

Harris, M. ( 2007). Optimizing parallel reduction in CUDA, http://developer.nvidia.com/object/cuda_sdk_samples.html

11.

He, B. , Yang, K. , Fang, R. , Lu, M. , Govindaraju, N.K. , Luo, Q. and Sander, P. ( 2008). Relational joins on graphics processor. In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD’08), pp. 511-524.

12.

Hough, P.V.C. ( 1962). Method and means for recognizing complex patterns . U.S. Patent 3069654.

13.

Lucena, J. , Gómez-Luna, J. , González-Linares, J.M. and Guil, N. ( 2010). Parallelization of the classic GHT on GPU. UMA-DAC-10-01. University of Málaga, http://www.ac.uma.es/∼vip/publications/UMA-DAC-10-01.pdf

14.

Luo, Y. and Duraiswami, R. ( 2008). Canny edge detection on NVIDIA CUDA. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 1-8.

15.

Nvidia (2007a). NVIDIA CUDA home page, http://www.nvidia.com/cuda

16.

Nvidia (2007b). NVIDIA CUDA SDK , http://developer.nvidia.com/object/cuda_3_0_downloads.html

17.

Nvidia (2010a). NVIDIA CUDA C programming best practices guide version 3.0, http://developer.nvidia.com/object/cuda_3_0_downloads.html

18.

Nvidia (2010b). NVIDIA CUDA programming guide version 3.0, http://developer.nvidia.com/object/cuda_3_0_downloads.html

19.

Nvidia (2010c ). NVIDIA CUDA Visual Profiler, http://developer.nvidia.com/object/cuda_3_0_downloads.html

20.

OpenCL (2009). OpenCL home page, http://www.khronos.org/opencl

21.

Podlozhnyuk, V. ( 2007a). Histogram calculation in CUDA, http://developer.nvidia.com/object/cuda_sdk_samples.html

22.

Podlozhnyuk, V. ( 2007b). Image convolution with CUDA, http://developer.nvidia.com/object/cuda_sdk_samples.html

23.

Ryoo, S. , Rodrigues, C.I. , Stone, S.S. , Stratton, J.A. , Ueng, S.-Z. , Baghsorkhi, S.S. and Hwu, W. -m. W. (2008). Program optimization carving for GPU computing . J. Parallel Distrib. Comput. 68(10): 1389-1401.

24.

Sáez, E. , González-Linares, J.M. , Palomares, J.M. , Benavides, J.I. and Guil, N. ( 2003a). New edge-based feature extraction algorithm for video segmentation. In Proceedings of Image and Video Communications and Processing (SPIE’03), pp. 861-872.

25.

Sáez, E. , Palomares, J.M. , Benavides, J.I. and Guil, N. ( 2003b). Global motion estimation algorithm for video segmentation . In Proceedings of Image and Video Communications and Processing (SPIE’03), pp. 1540-1550.

26.

Sengupta, S. , Harris, M. and Garland, M. ( 2008). Efficient parallel scan algorithms for GPUs. NVR-2008-003 . NVIDIA.

27.

Shams, R. and Kennedy, R.A. ( 2007). Efficient histogram algorithms for NVIDIA CUDA compatible devices. In Proceedings of International Conference on Signal Processing and Communications Systems (ICSPCS’07) , pp. 418-422.

28.

Strzodka, R. , Ihrke, I. and Magnor, M. ( 2003). A graphics hardware implementation of the Generalized Hough Transform for fast object recognition, scale and 3D pose detection. In Proceedings of 12th International Conference on Image Analysis and Processing (ICIAP’03), pp. 188-195.

29.

Venkatasubramanian, S. and Vuduc, R.W. ( 2009). Tuned and widely asynchronous stencil kernels of hybrid CPU/GPU systems. In Proceedings of 23rd International Conference on Supercomputing (ICS’09), pp. 244-255.

30.

Volkov, V. and Demmel, J.W. ( 2008). Benchmarking GPUs to tune dense linear algebra . In Proceedings of the 2008 ACM/ IEEE Conference on Supercomputing (SC’08), pp. 1-11.