Geodesic
A parallel algorithm of Euclidean distance matrix computation for the Intel Xeon Phi Knights Landing many-core processor
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 3, pp. 65-82 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Computation of a Euclidean distance matrix (EDM) is a typical task in a wide spectrum of problems connected with data mining. Currently, many parallel algorithms for this task have been developed for graphical processors. These developments, however, cannot be directly applied to the Intel Many Integrated Core systems. In this paper, we suggest a parallel algorithm for EDM computation on Intel Xeon Phi Knights Landing processor in the case when the input data fit into the main memory. The algorithm exploits block-oriented scheme of computations that allows for the efficient utilization of Intel Xeon Phi vectorization abilities. In the algorithm, we also apply apply a sophisticated data layout to store data points in main memory so as to reduce the number of processor cache misses during EDM computations. Experimental evaluation of the algorithm on real-world and synthetic datasets shows that it is highly scalable and outruns analogues in the case of rectangular matrices with low-dimensional data points.
Keywords: OpenMP, Intel Xeon Phi, Knights Landing, data layout, vectorization.
Mots-clés : Euclidean distance matrix 
@article{VYURV_2018_7_3_a4,
     author = {T. V. Rechkalov and M. L. Zymbler},
     title = {A parallel algorithm of {Euclidean} distance matrix computation for the {Intel} {Xeon} {Phi} {Knights} {Landing} many-core processor},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {65--82},
     year = {2018},
     volume = {7},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2018_7_3_a4/}
}
TY  - JOUR
AU  - T. V. Rechkalov
AU  - M. L. Zymbler
TI  - A parallel algorithm of Euclidean distance matrix computation for the Intel Xeon Phi Knights Landing many-core processor
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2018
SP  - 65
EP  - 82
VL  - 7
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURV_2018_7_3_a4/
LA  - ru
ID  - VYURV_2018_7_3_a4
ER  - 
%0 Journal Article
%A T. V. Rechkalov
%A M. L. Zymbler
%T A parallel algorithm of Euclidean distance matrix computation for the Intel Xeon Phi Knights Landing many-core processor
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2018
%P 65-82
%V 7
%N 3
%U http://geodesic.mathdoc.fr/item/VYURV_2018_7_3_a4/
%G ru
%F VYURV_2018_7_3_a4
T. V. Rechkalov; M. L. Zymbler. A parallel algorithm of Euclidean distance matrix computation for the Intel Xeon Phi Knights Landing many-core processor. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 3, pp. 65-82. http://geodesic.mathdoc.fr/item/VYURV_2018_7_3_a4/

[1] A. S. Arefin, C. Riveros, R. Berretta, P. Moscato, “Computing Large-scale Distance Matrices on GPU”, Proceedings of the 7th International Conference on Computer Science and Education, ICCSE 2012 (July 14–17, 2012, Melbourne, Australia), IEEE Computer Society, 2012, 576–580 | DOI

[2] D. Chang, N. A. Jones, D. Li, M. Ouyang, R. K. Ragade, “Compute Pairwise Euclidean Distances of Data Points with GPUs”, Proceedings of the IASTED International Symposium on Computational Biology and Bioinformatics, CBB’2008 (November 16–18, 2008, Orlando, Florida, USA), IASTED, 2008, 278–283

[3] G. Chrysos, “Intel Xeon Phi Coprocessor (Codename Knights Corner)”, Proceedings of the 2012 IEEE Hot Chips 24th Symposium (HCS), (Cupertino, CA, USA, August 27–29), 2012, 1–31 | DOI

[4] D. Dembélé, P. Kastner, “Fuzzy c-Means Method for Clustering Microarray Data”, Bioinformatics, 19:8 (2003), 973–980 | DOI

[5] I. Dokmanic, R. Parhizkar, J. Ranieri, M. Vetterli, “Euclidean Distance Matrices: Essential Theory, Algorithms, and Applications”, IEEE Signal Processing Magazine, 32:6 (2015), 12–30 | DOI

[6] J. M. Engreitz, B. J. Daigle, J. J. Marshall, R. B. Altman, “Independent Component Analysis: Mining Microarray Data for Fundamental Human Gene Expression Modules”, Journal of Biomedical Informatics, 43:6 (2010), 932–944 | DOI

[7] J. Foote, “An Overview of Audio Information Retrieval”, Multimedia Systems, 7:1 (1999), 2–10 | DOI

[8] Q. F. Hassan, Innovative Research and Applications in Next-generation High Performance computing, IGI Global, 2016 | DOI

[9] M. Jaros, P. Strakos, T. Karásek, et al., “Implementation of k-Means Segmentation Algorithm on Intel Xeon Phi and GPU: Application in Medical Imaging”, Advances in Engineering Software, 103 (2017), 21–28 | DOI

[10] S. Kim, M. Ouyang, “Compute Distance Matrices with GPU”, Proceedings of the 3rd Annual International Conference on Advances in Distributed and Parallel Computing, ADPC’2012 (17–18 September, 2012, Bali, Indonesia) | DOI

[11] P. Kostenetskiy, A. Safonov, “SUSU Supercomputer Resources”, PCT’2016, International Scientific Conference on Parallel Computational Technologies (Arkhangelsk, Russia, March 29–31, 2016), v. 1576, CEUR Workshop Proceedings, 2016, 561–573

[12] S. Lee, W. Liao, A. Agrawal, N. Hardavellas, A. N. Choudhary, “Evaluation of k-Means Data Clustering Algorithm on Intel Xeon Phi”, Proceedings of the 2016 IEEE International Conference on Big Data, BigData 2016 (Washington DC, USA, December 5–8, 2016), IEEE Computer Society, 2016, 2251–2260 | DOI

[13] Q. Li, V. Kecman, R. Salman, “A Chunking Method for Euclidean Distance Matrix Calculation on Large Dataset Using Multi-GPU”, Proceedings of the 9th International Conference on Machine Learning and Applications, ICMLA 2010 (Washington, DC, USA, 12–14 December 2010), IEEE Computer Society, 2010, 12–14 | DOI

[14] C. Meek, B. Thiesson, D. Heckerman, “The Learning-Curve Sampling Method Applied to Model-Based Clustering”, Journal of Machine Learning Research, 2 (2002), 397–418

[15] V. Melnykov, W. C. Chen, R. Maitra, “MixSim: An R Package for Simulating Data to Study Performance of Clustering Algorithms”, Journal of Statistical Software, 51:12 (2012), 1–25 | DOI

[16] R. Narayanan, B. Ozisikyilmaz, J. Zambreno, G. Memik, A. N. Choudhary, “MineBench: A Benchmark Suite for Data Mining Workloads”, Proceedings of the 2006 IEEE International Symposium on Workload Characterization, IISWC 2006 (October 25–27, 2006, San Jose, California, USA), IEEE Computer Society, 2006, 182–188 | DOI

[17] T. V. Rechkalov, M. L. Zymbler, “Accelerating Medoids-based Clustering with the Intel Many Integrated Core Architecture”, Proceedings of the 9th International Conference on Application of Information and Communication Technologies, AICT’2015 (October 14–16, 2015, Rostov-on-Don, Russia), IEEE Computer Society, 2015, 413–417 | DOI

[18] A. Sodani, “Knights Landing (KNL): 2nd Generation Intel Xeon Phi Processor”, Proceedings of the 2015 IEEE Hot Chips 27th Symposium, HCS (Cupertino, CA, USA, August 22–25, 2015), IEEE Computer Society, 2015, 1–24 | DOI

[19] G. Valenzise, L. Gerosa, M. Tagliasacchi, F. Antonacci, A. Sarti, “Scream and Gunshot Detection and Localization for Audio-surveillance Systems”, Proceedings of the 4th IEEE International Conference on Advanced Video and Signal Based Surveillance, AVSS 2007 (5–7 September, 2007, Queen Mary, University of London, London, United Kingdom), IEEE Computer Society, 2007, 21–26 | DOI

[20] F. Wu, Q. Wu, Y. Tan, L. Wei, L. Shao, L. Gao, “A Vectorized k-Means Algorithm for IntelMany Integrated Core Architecture”, Proceedings of the 10th International Symposium onAdvanced Parallel Processing Technologies, APPT 2013, Revised Selected Papers (Stockholm, Sweden, August 27–28, 2013), v. 8299, Lecture Notes in Computer Science, Springer, 2013, 277–294 | DOI

[21] J. Zou, L. Chen, C. L. Chen, “Ensemble Fuzzy c-Means Clustering Algorithms Based on KL-Divergence for Medical Image Segmentation”, Proceedings of the 2013 IEEE International Conference on Bioinformatics and Biomedicine (Shanghai, China, December 18–21, 2013), IEEE Computer Society, 2013, 291–296 | DOI