Effective Implementation of the EM-algorithm using GPGPU

The problem of decreasing of running time for the data processing algorithms is very important especially when they are used in real time. For example, in real time image processing, process control systems, speech recognition, etc. The paper considers the possibility of decreasing running time of the expectation maximization (EM) algorithm using modern computing systems. The proposed modified EM-algorithm is aimed at better parallelism for the general purpose graphical processing unit (GPGPU).The experimental results are obtained with solving of the classical problem of Gaussian random variables mixture separation. The proposed implementation of the algorithm was performed on one and two 8-core processor (CPU) setup, as well as on the general purpose graphical processing unit. The graphics processor, because of its abilities for parallel computations and due to the properties of the EM-algorithm considered, showed substantially higher effectiveness in all the computational experiments. Besides, the modified EM-algorithm showed almost two times faster performance on GPGPU than on one or two CPU using large sample sizes (from 5 million values and higher). The lower price of graphics processor is an additional advantage of the approach proposed for such parallel algorithms and GPGPU usage.

Publication year: 
2013
Issue: 
5
УДК: 
004.021
С. 35–39., укр., Іл. 5. Табл. 3. Бібліогр.: 11 назв.
References: 

1. K. Mehlhorn and S. Thiel, “Faster algorithms for boundsconsistency of the sortedness and the alldifferent constraint”, in Proc. Principles and practice of constraint programming Int. Conf., San Francisco, 2000, pp. 306— 319.
2. R. Dechter, Constraint processing. San Francisco: Elsevier Science, 2003, 481 p.
3. Measurements, models, systems and design, J. Korbicz, Ed. Warszawa: Wydawnictwa Komunikacjii Lacznosci, 2007, 507 p.
4. W. Hu, “Calibration of multivariate generalized hyperbolic distributions using the EM algorithm”, Ph.D thesis, The Florida State University, 2005, 115 p.
5. F. Dellaert, “The expectation maximization algorithm”, College of Computing, Georgia Institute of Technology, 2002, 7 p.
6. Yan Shuicheng et al., “Sift-bag kernel for video event analysis”, in Proc. 16th ACM Int. Conf. on Multimedia, 2008, pp. 229—238.
7. S. Borman. The expectation maximization algorithm — a short tutorial [Online]. Avaliable: http://www.seanborman. com/publications/EM_algorithm.pdf
8. Ben-AriM. Principles of Concurrent and Distributed Programming. New York: Addison-Wesley, 2006, 384 p.
9. Kasitskyi O.V., Bidyuk P.I. Effective EM algorithm implementation for multicore CPU systems // Системні науки і кібернетика. — 2013. — 3, № 1. — C. 47—58.
10. B. Chapman et al., Using OpenMP: Portable Shared Memory Parallel Programming. Boston: The MIT Press, 2007, 378 p.
11. OpenCL Programming Guide for the CUDA Architecture (2009) [Online]. Avaliable: http://www.nvidia.com/content/ cudazone/download/OpenCL/NVIDIA_OpenCL_ProgrammingGuide. pdf

References [transliteration]: 

1. K. Mehlhorn and S. Thiel, “Faster algorithms for bounds-consistency of the sortedness and the alldifferent constraint”, in Proc. Principles and practice of constraint programming Int. Conf., San Francisco, 2000, pp. 306–319.
2. R. Dechter, Constraint processing. San Francisco: Elsevier Science, 2003, 481 p.
3. Measurements, models, systems and design, J. Korbicz, Ed. Warszawa: Wydawnictwa Komunikacjii Lacznosci, 2007, 507 p.
4. W. Hu, “Calibration of multivariate generalized hyperbolic distributions using the EM algorithm”, Ph.D thesis, The Florida State University, 2005, 115 p.
5. F. Dellaert, “The expectation maximization algorithm”, College of Computing, Georgia Institute of Technology, 2002, 7 p.
6. Yan Shuicheng et al., “Sift-bag kernel for video event analysis”, in Proc. 16th ACM Int. Conf. on Multimedia, 2008, pp. 229–238.
7. S. Borman. The expectation maximization algorithm – a short tutorial [Online]. Avaliable: http://www.seanborman.com/publications/EM_algorithm.pdf
8. Ben-AriM. Principles of Concurrent and Distributed Programming. New York: Addison-Wesley, 2006, 384 p.
9. Kasitskyi O.V., Bidyuk P.I. Effective EM algorithm implementation for multicore CPU systems // Systemni nauky i kibernetyka. – 2013. – 3, # 1. – S. 47–58.
10. B. Chapman et al., Using OpenMP: Portable Shared Memory Parallel Programming. Boston: The MIT Press, 2007, 378 p.
11. OpenCL Programming Guide for the CUDA Architecture (2009) [Online]. Avaliable: http://www.nvidia.com/content/cudazone/download/OpenCL/NVIDIA_OpenCL_ProgrammingGuide.pdf

AttachmentSize
2013-5-5.pdf173.64 KB

Тематичні розділи журналу

,