Porównanie wydajności algorytmu k-means zaimplementowanego w języku X10 i środowisku C++/MPI

• Autorzy: Wyrzykowski R. , Karoń T.

Warianty tytułu

EN

Performance comparison of the k-means algorithm implemented in the X10 programming language and the C++/MPI environment

• Języki publikacji: PL

Abstrakty

PL

W pracy opisano algorytm k-średnich oraz sposób jego implementacji w języku X10. Dokonano porównania tego rozwiązania z implementacją w języku C++11 z wykorzystaniem standardu MPI. Stwierdzono, że implementacja w języku X10 jest szybsza przy większej liczbie procesorów realizujących obliczenia niż implementacja w środowisku C++/MPI. Kod zapisany w języku X10 jest o 59% krótszy od kodu dla kombinacji C++/MPI.

EN

In this work the k-means algorithm and the way of its implementation in the X10 programming language are described. The achieved results are compared with the implementation of the same algorithm in the C++11 programming language using the MPI standard. It was confirmed that the implementation in the X10 programming language is faster on a large number of processors than the implementation in the C++/MPI environment. Additionally, the X10 code is about 59% shorter than the code for the C++/MPI combination.

Słowa kluczowe

PL

algorytm k-średnich; język programowania X10; środowisko C++/MPI; porównanie

EN

k-means algorithm; X10 programming language; C++/MPI environment; comparison

• Wydawca: Warszawska Wyższa Szkoła Informatyki
• Czasopismo: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
• Rocznik: 2016
• Tom: nr 14
• Strony: 7--35
• Opis fizyczny: Bibliogr., 51 poz., rys., tab., wykr.

Twórcy

autor

Wyrzykowski R.

• Politechnika Częstochowska, Instytut Informatyki Teoretycznej i Stosowanej

autor

Karoń T.

• Politechnika Częstochowska, Instytut Informatyki Teoretycznej i Stosowanej

Bibliografia

• [1] Czech Z., Wprowadzenie do obliczeń równoległych, wyd. pierwsze,Warszawa 2010: Wydawnictwa Naukowe PWN
• [2] Dotsenko Y., Mellor-Crummey J., Cantonnet F., El-Ghazawi T., Mohanti A., Yao Y., Chavarría-Miranda D., Coarfa C., An evaluation of global address space languages: co-array fortran and unified parallel C, w: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, Chicago 2005
• [3] Callahan D., Zima H.P., Chamberlain B.L., Parallel programmability and the chapel language, “International Journal of High Performance Computing Applications” 2007, Vol. 21, No. 3
• [4] Colella P., Gay D., Graham S., Hilfinger P., Krishnamurthy A., Liblit B., Pike C.M., Semenzato G.L., Aiken A., Titanium: A high-performance Java dialect, ACM 1998 Workshop on Java for High-Performance Network Computing, 1997, http://pages.cs.wisc.edu/~liblit/titanium/titanium.pdf
• [5] Herta B., Cunningham D., Grove D., Kambadur P.n, Saraswat V., Shinnar A., M. Takeuchi, M. Vaziri, O. Tardieu, X10 and APGAS at Petascale, w: Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Orlando 2014
• [6] Bonachea D., Chen W., Colella P., Datta K., Duell J., Graham S.L., Hargrove P., Hilfinger P., Husbands P., Iancu C., Kamil A., Nishtala R., Su J., Welcome M., Wen T., Yelick K., Productivity and performance using partitioned global address space languages, w: Proceedings of the 2007 International Workshop on Parallel Symbolic Computation, Waterloo 2007
• [7] Almasi G., Bikshandi G., Cascaval C., Grove D., Cunningham D., Tardieu O., Peshansky I., Kodali S., Saraswat V., The Asynchronous Partitioned Global Address Space Model, w: Proceedings of The First Workshop on Advances in Message Passing, Toronto 2010
• [8] X10: Performance and Productivity at Scale, http://x10-lang.org/document ation/practical-x10-programming/performance-tuning.html
• [9] MPI: A Message - Passing Interface Standard version 2.2, http://www.mpi- forum.org/docs/mpi22-report.pdf
• [10] United States Census Bureau, ACS Public Use Microdata Sample (PUMS) File, http://www2.census.gov/acs2010_5yr/pums/csv_pus.zip
• [11] Larose D.T., Odkrywanie wiedzy z danych: wprowadzenie do eksploracji danych, Warszawa 2013: Wydawnictwo Naukowe PWN
• [12] Ranka S., Singh V., Alsabti K., An efficient k-means clustering algorithm, w: Proceedings of the 1st Workshop on High Performance Data Mining, Orlando 1998
• [13] Modha D.S., Dhillon I.S., A data - clustering algorithm on distributed memory multiprocessors, w: Large-Scale Parallel Data Mining, Berlin Heidelberg 2000: Springer
• [14] Fayyad U.M., Bradley P.S., Refining Initial Points for K-means Clustering, w: Proceedings of the Fifteenth International Conference on Machine Learning, San Francisco 1998: ICML
• [15] Elkan Ch., Using the triangle inequality to accelerate k-means, w: Twentieth International Conference on Machine Learning, Washington 2003
• [16] Moore A., Pelleg D., Accelerating exact k-means algorithms with geometric reasoning, w: Proceedings of the fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego 1999
• [17] Rebolledo D., Chan E., Campbell R.H., Farivar R., A Parallel Implementation of K-Means Clustering on GPUs, w: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas 2008
• [18] Meila M., The uniqueness of a good optimum for k-means, w: Proceedings of the 23rd International Conference on Machine Learning, New York 2006
• [19] Tajunisha S., Performance analysis of k-means with different initialization methods for high diemnsional data, “Interantional Journal of Artifical Intelligence & Applications” 2010, Vol. 1, No. 4
• [20] Kamber M., Pei J., Han J., Data Mining: Concepts and Techniques, Burlington 2006: Morgan Kaufmann
• [21] Dimov S.S., Nguyen C.D., Pham D.T., Selection of K in K-means clustering, Proceedings of the Institution of Mechanical Engineers, Part C, “Journal of Mechanical Engineering Science” 2005, Vol. 219, No. 1
• [22] Język programowania X10, http://x10-lang.org/home/introduction.html
• [23] X10 Programming Language, http://x10.sourceforge.net/documentation/ languagespec/x10-latest.pdf
• [24] Tardieu O., Cunningham D., Herta B., Peshansky I., Saraswat V., Grove D., A performance model for X10 applications: what's going on under the hood?, w: Proceedings of the 2011 ACM SIGPLAN X10 Workshop, San Jose 2011
• [25] Otto S., Huss-Lederman S., Walker D., Dongarra J., Snir M., MPI: The Complete Reference, Cambridge 1996: MIT Press
• [26] JTC1/SC22/WG21 - The C++ Standards Committee, http://www.open-std. org/JTC1/SC22/WG21/
• [27] Williams A., Język C++ i przetwarzanie współbieżne w akcji, Gliwice 2013: Wydawnictwo HELION
• [28] C++ Reference, http://www.cplusplus.com/reference/thread/thread/hardware _concurrency/
• [29] Kwiatkowski J., Parallel Applications Performance Evaluation Using the Concept of Granularity, LNCS 2014, Vol. 8385
• [30] Bisgin H., Parallel clustering algorithms with application to climatology, Informatics Institute, Istanbul 2008: Istambul Technical University
• [31] Woodall T.S., Graham R.L., Maccabe A.B., Bridges P.G., Shipman G.M., Infiniband scalability in Open MPI, w: 20th International Parallel and Distributed Processing Symposium, Rhodes Island 2006: IPDPS
• [32] Gopalakrishnan S., Hyun-Wook J., Panda D.K., Huang W., Scheduling of MPI-2 one sided operations over InfiniBand, w: Proceedings of the 19th IEEE Int. Parallel and Distributed Processing Symposium, Denver 2005
• [33] Jiuxing L., Hyun-Wook J., Panda D.K., Gropp W., Thakur R., Weihang J., High performance MPI-2 one-sided communication over InfiniBand, w: IEEE Int. Symposium on Cluster Computing and the Grid, Chicago 2004
• [34] Nieplocha J., Panda D., Tipparaju V., Fast collective operations using shared and remote memory access protocols on clusters, w: Proceedings of the Int. Symp. Parallel and Distributed Processing, Nice 2003
• [35] Komputery Dużej Mocy w ACK CYFRONET AGH, https://kdm.cyfronet.pl/ portal/Zeus
• [36] Specyfikacja procesora Intel® Xeon® Processor X5650, http://ark.intel.com /pl/products/47922/Intel-Xeon-Processor-X5650-12M-Cache-2_66-GHz-6_4 0-GTs-Intel-QPI#@specification
• [37] Infmiband Technology Specification, http://www.ieee802.org/3/
• [38] Karpusenko V., Yoo T., Vladimirov A., File I/O on Intel Xeon Phi Coprocessors: RAM disks, VirtIO, NFS and Lustre, http://hgpu.org, 2014
• [39] Oprogramowanie - Komputery Dużej Mocy w ACK CYFRONET AGH, https://kdm .cyfronet.pl/portal/Oprogramowanie
• [40] GCC 4.8.2 manuals - GNU Project - Free Software Foundation (FSF), https://gcc.gnu.org/onlinedocs/4.8.2/
• [41] Apache Ant, http://ant.apache.org/
• [42] Open MPI: Version 1.6.5, Open MPI Software, http://www.open-mpi. org/software/ompi/v1.6/
• [43] Kuah K., Motion Estimation with Intel® Streaming SIMD Extensions 4 (Intel® SSE4), https://software.intel.com/en-us/articles/motion-estimatio n-with-intel-streaming-simd-extensions-4-intel-sse4/?iid=2121 &wapkw=sse4
• [44] Using the GNU Compiler Collection (GCC), Optimize Options, https://gcc. gnu.org/onlinedocs/gcc/Optimize-Options.html
• [45] Anderson T.A., Liu H., Glew N., Petersen L., Measuring the Haskell gap, w: Proceedings of the Int. 25th Symposium on Implementation and Application of Functional Languages, Nijmegen 2013
• [46] United States Census Bureau, 2006 - 2010 ACSPUMSDATA DICTIONARY, http://www.census.gov/acs/www/Downloads/data_documentation/pums/Dat aDictZPUMS_Data_Dictionary_2006-2010.pdf
• [47] Źródła języka X10, http ://x10-lang.org/software/download-x10/release.html
• [48] Implementacje biblioteki X10RT, http://x10-lang.org/documentation/practic al-x10-programming/x10rt-implementations.html
• [49] Building X10 from source, http://x10-lang.org/X10-development/building-X 10-from-source.html
• [50] Li X.S., Bailey D.H., Hida Y., Algorithms for quad-double precision floating point arithmetic, http://www.escholarship.org/uc/item/69q5t2mj
• [51] Brezin J., Swart C.B., Halverson Ch.A., Richards J.T., A decade of progress in parallel programming productivity, “Communications of the ACM” 2014, Vol. 57, No. 11

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.