Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

Expectation-Maximization Algorithms for Gaussian Mixture Models Using Linear Algebra Libraries on Parallel Shared-Memory Systems

DOI: http://dx.doi.org/10.15439/2023F9859

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 1047–1052 ()

Full text

Abstract. In this paper the problem of parameter estimation of Gaussian mixture models using the expectation-maximization (EM) algorithm is considered. Four variants of the EM algorithm parallelized using the OpenMP standard are proposed. The main difference between the variants is the degree of usage of vendor-optimized linear algebra libraries. The computational experiments were performed using 25 large datasets on a system with two 12-core Intel Xeon processors. The results of experiments indicate that the EM variant using level 3 (matrix-matrix) operations and L3 cache blocking is the fastest one. It is 1.75-2.75 times faster than the naive version using level 2 (matrix-vector) operations. Its parallel efficiency relative to the sequential version is always greater than 83\%.

References

  1. G. McLachlan and D. Peel, Finite Mixture Models. New York: Wiley, 2000.
  2. A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. Royal Stat. Soc. Ser. B, vol. 39, no. 1, pp. 1–38, 1977.
  3. W. Kwedlo, “A parallel EM algorithm for Gaussian mixture models implemented on a NUMA system using OpenMP,” in Proceedings of the 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing PDP 2014. IEEE CPS, 2014, pp. 292–298.
  4. L. Blackford, J. Demmel, J. Dongarra, I. Duff, S.Hammarling, G. Henry, M. Heroux, L. Kaufman, A. Lumsdaine, A. Petitet, R. Pozo, K. Remington, and R. Whaley, “An updated set of basic linear algebra subprograms (BLAS),” ACM Transactions on Mathematical Software, vol. 28, no. 2, pp. 135–151, 2002.
  5. M. Kowarschik and C. Weiß, An overview of cache optimization techniques and cache-aware numerical algorithms, ser. Lecture Notes in Computer Science, vol 2625. Springer, 2003, pp. 213–232.
  6. G. McLachlan and T. Krishnan, The EM Algorithm and Extensions. New York: Wiley, 2008.
  7. R. A. Redner and H. F. Walker, “Mixture densities, maximum likelihood and the EM algorithm,” SIAM Rev., vol. 26, no. 2, pp. 195–239, 1984. [Online]. Available: https://www.jstor.org/stable/2030064
  8. G. H. Golub and C. F. van Loan, Matrix Computations. Baltimore, MD: Johns Hopkins, 1996.
  9. OpenMP Architecture Review Board, “OpenMP application program interface version 4.5,” http://www.openmp.org/wp-content/uploads/openmp-4.5.pdf, 2015.
  10. E. Chan, M. Heimlich, A. Purkayastha, and R. van de Geijn, “Collective communication: theory, practice, and experience,” Concurr. Comput. Pract. Exp., vol. 19, no. 13, pp. 1749–1783, 2007.
  11. R. Maitra and V. Melnykov, “Simulating data to study performance of finite mixture modeling and clustering algorithms,” J. Comput. Graph. Stat., vol. 19, no. 2, pp. 354–376, 2010. [Online]. Available: https://doi.org/10.1198/jcgs.2009.08054
  12. Message Passing Interface Forum, “MPI: A Message-Passing Interface Standard Version 3.1,” 2015. [Online]. Available: http://mpi-forum.org/docs/mpi-3.1/mpi31-report.pdf
  13. W. Kwedlo and P. J. Czochański, “A hybrid MPI/OpenMP parallelization of K-means algorithms accelerated using the triangle inequality,” IEEE Access, vol. 7, pp. 42 280–42 297, 2019.