Ефективна реалізація ЕМ-алгоритму з використанням технології GPGPU

У статті розглядається модифікація алгоритму максимізації математичного сподівання (ЕМ-алгоритму) для підвищення його швидкодії за допомогою збільшення ступеня паралелізму при реалізації на графічному процесорі. Результат забезпечу-ється розв’язанням класичної задачі розділення суміші гауссових випадкових вели-чин. Реалізація алгоритму була виконана на одному і двох 8-ядерних процесорах, а також на графічному процесорі загального призначення. У всіх тестах графічний процесор за рахунок своїх значних можливостей з паралельних обчислень та через властивості виконуваного ЕМ-алгоритму виявився більш ефективним. А за великих обсягів вибірок (від 5 млн значень і більше) модифікований ЕМ-алгоритм на графічному процесорі показав практично в два рази швидше виконання, ніж на одному або двох універсальних процесорах. З урахуванням меншої вартості графічних процесорів підвищення паралелізму алгоритмів має важливе практичне значення.

Рік видання: 
2013
Номер: 
5
УДК: 
004.021
С. 35–39., укр., Іл. 5. Табл. 3. Бібліогр.: 11 назв.
Література: 

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

Список літератури у транслітерації: 

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

Текст статтіРозмір
2013-5-5.pdf173.64 КБ