Эффективная реализация ЕМ-алгоритма с использованием технологии 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

Полнотекстовый документSize
2013-5-5.pdf173.64 KB