2013 MassivelyParallelExpectationMax

• (Altinigneli et al., 2013) ⇒ Muzaffer Can Altinigneli, Claudia Plant, and Christian Böhm. (2013). “Massively Parallel Expectation Maximization Using Graphics Processing Units.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487628

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Massively+Parallel+Expectation+Maximization+Using+Graphics+Processing+Units
• http://dl.acm.org/citation.cfm?id=2487575.2487628&preflayout=flat#citedby

Quotes

Author Keywords

• Cuda; data mining; expectation maximization; fermi; graphics processing unit; graphics processors

Abstract

Composed of several hundreds of processors, the Graphics Processing Unit (GPU) has become a very interesting platform for computationally demanding tasks on massive data. A special hierarchy of processors and fast memory units allow very powerful and efficient parallelization but also demands novel parallel algorithms. Expectation Maximization (EM) is a widely used technique for maximum likelihood estimation. In this paper, we propose an innovative EM clustering algorithm particularly suited for the GPU platform on NVIDIA's Fermi architecture. The central idea of our algorithm is to allow the parallel threads exchanging their local information in an asynchronous way and thus updating their cluster representatives on demand by a technique called Asynchronous Model Updates (Async-EM). Async-EM enables our algorithm not only to accelerate convergence but also to reduce the overhead induced by memory bandwidth limitations and synchronization requirements. We demonstrate (1) how to reformulate the EM algorithm to be able to exchange information using Async-EM and (2) how to exploit the special memory and processor architecture of a modern GPU in order to share this information among threads in an optimal way. As a perspective Async-EM is not limited to EM but can be applied to a variety of algorithms.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 MassivelyParallelExpectationMax	Christian Böhm Claudia Plant Muzaffer Can Altinigneli			Massively Parallel Expectation Maximization Using Graphics Processing Units				10.1145/2487575.2487628		2013