Przetwarzanie równoległe algorytmów analizy skupień w technologii CUDA

• Autorzy: Andrzej Dudek , Bartosz Kwaśniewski

Warianty tytułu

Parallel Processing of Clustering Algorithms in CUDA Technology

• Języki publikacji: PL

Abstrakty

W artykule scharakteryzowano podstawy metodologiczne i technologiczne przetwarzania równoległego danych w technologii CUDA (Compute Unified Device Architecture) oraz dokonano przeglądu możliwości wykorzystania przetwarzania równoległego w technologii CUDA dla najbardziej znanych algorytmów analizy skupień, w tym klasyfikacji spektralnej [Ng i in. 2001]. W pracy ponadto wskazano miejsca, w których zastosowanie przetwarzania równoległego znacznie przyśpieszy czas ich wykonywania. Całość jest zakończona porównaniem empirycznych charakterystyk czasu pracy i otrzymanych rezultatów równoległych wersji algorytmów analizy skupień z implementacjami tych algorytmów w popularnym środowisku statystycznym R i w języku C++.(abstrakt oryginalny)

EN

In this paper methodological and technological basis of parallel processing in CUDA (Compute Unified Device Architecture) technology are characterized along with an overview of its application possibilities for most known clustering algorithms including spectral classification [Ng et al. 2001]. Places for which parallel processing can drastically increase performance times are pointed. The paper is completed with empirical comparison of the characteristics of time and received results of the parallel version of the clustering algorithm with implementations of these algorithms from the popular statistical environment R and with C++ implementations.(original abstract)

Słowa kluczowe

PL

Analiza skupień; Przetwarzanie równoległe; Klasyfikacja

EN

Cluster analysis; Parallel processing; Classification

• Czasopismo: Prace Naukowe Uniwersytetu Ekonomicznego we Wrocławiu. Taksonomia
• Rocznik: 2013
• Tom: 20
• Numer: nr 278 Klasyfikacja i analiza danych - teoria i zastosowania
• Strony: 180--187

Twórcy

autor

Andrzej Dudek

• Uniwersytet Ekonomiczny we Wrocławiu

autor

Bartosz Kwaśniewski

• Nokia Siemens Networks

Bibliografia

• Agresti A. (2002), Categorical Data Analysis, John Wiley and Sons, New York.
• Anderson E., Bai Z., Bischof C., Blackford S., Demmel J., Dongarra J., Du Croz J., Greenbaum A., Hammarling A., McKenney A., Sorensen D. (1999), LAPACK User's Guide, Third Edition, SIAM, Philadelphia.
• Catanzaro B., Sundaram N., Keutzer K. (2008), Fast support vector machine training and classification on graphics processors, Proceedings of the 25th international conference on machine learning, New York.
• Dudek A. (2012), Classification of large datasets. Problems, methods, algorithms, Acta Universitatis Lodziensis, Folia Oeconomica (w druku).
• Farber R. (2011), CUDA Applications Design and Development, Morgan Kaufman, Amsterdam-Boston(...) Tokyo.
• Francis J.G.F. (1961), The QR transformation, I. "The Computer Journal", vol. 4, no. 3, s. 265-271.
• Gordon A.D. (1999), Classification, Chapman & Hall/CRC, London.
• Hong-tao B., Li-li H., Dan-tong O., Zhan-shan L., He L. (2009), K-Means on Commodity GPUs with CUDA, World Congress on Computer Science and Information Engineering, s. 651-655.
• Householder A.S. (1964), The Theory of Matrices in Numerical Analysis, Dover Publications, Inc., New York.
• Ingram S., Munzner T., Olano M. (2009), Glimmer: Multilevel MDS on the GPU, IEEE Transactions on Visualization and Computer Graphics, s. 249-261.
• Karatzoglou A. (2006), Kernel methods. Software, algorithms and applications, Rozprawa doktorska, Uniwersytet Techniczny we Wiedniu.
• Kaufman L., Rousseeuw P.J. (1990), Finding Groups in Data: an Introduction to Cluster Analysis, Wiley, New York.
• Kumar N., Satoor S., Buck I. (2009), Fast Parallel Expectation Maximization for Gaussian Mixture Models on GPUs Using CUDA. High Performance Computing and Communications, 2009, HPCC '09. Seoul, 103-109.
• Ma W., Agrawal G. (2009), A translation system for enabling data mining applications on GPUs, Proceedings of the 23rd international conference on Supercomputing, New York.
• Ng A., Jordan I., Weiss Y. (2001), On Spectral Clustering. Analysis and an Algorithm, Neural Information Processing Symposium.
• Shalom S.A., Dash M., Tue M. (2008), Efficient K-means Clustering Using Accelerated Graphics Processors, [w:] I.-Y. Song, J. Eder, T. Nguyen, Data Warehousing and Knowledge Discovery, Heidelberg, Springer Berlin, s. 166-175.
• Vapnik V. (1998), Statistical Learning Theory, John Wiley & Sons, New York.
• Walesiak M. (2009), Analiza skupień, [w:] M. Walesiak, E. Gatnar (red.), Statystyczna analiza danych z wykorzystaniem programu R, PWN, Warszawa, s. 407-433.
• Walesiak M., Dudek A. (2009), Odległość GDM dla danych porządkowych a klasyfikacja spektralna, Prace Naukowe UE we Wrocławiu nr 84, Wydawnictwo Uniwersytetu Ekonomicznego we Wrocławiu, Wrocław, s. 9-19.
• Wu R., Zhang B., Hsu M. (2009), Clustering billions of data points using GPUs, Proceedings of the combined workshops on UnConventional high performance computing workshop plus memory access workshop. ACM.