Параллельный алгоритм вычисления матрицы Евклидовых расстояний для многоядерного процессора Intel Xeon Phi Knights Landing

Михаил Леонидович Цымблер, Тимофей Валерьевич Речкалов

Аннотация


Вычисление матрицы Евклидовых расстояний требуется в широком спектре задач, связанных с интеллектуальным анализом данных. В настоящее время большое количество параллельных алгоритмов решения этой задачи реализовано для графических процессоров. Однако данные разработки не могут быть просто перенесены на многоядерные системы архитектуры Intel Many Integrated Core. В статье предлагается параллельный алгоритм вычисления матрицы Евклидовых расстояний на многоядерном процессоре Intel Xeon Phi поколения Knights Landing для случая, когда входные данные могут быть размещены в оперативной памяти. Данный алгоритм использует блочно-ориентированную схему организации вычислений, которая позволяет эффективно использовать возможности векторизации вычислений Intel Xeon Phi. В алгоритме применена нетривиальная компоновка данных в оперативной памяти для уменьшения количества кэш-промахов процессора во время вычислений. Эксперименты на реальных и синтетических наборах данных показали, что предложенный алгоритм хорошо масштабируется и опережает аналоги в случае прямоугольных матриц с данными малой размерности.

Ключевые слова


матрица Евклидовых расстояний, OpenMP, Intel Xeon Phi, Knights Landing, компоновка данных в памяти, векторизация вычислений

Полный текст:

PDF

Литература


Arefin A.S., Riveros C., Berretta R., Moscato P. 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. pp. 576–580. DOI: 10.1109/ICCSE.2012.6295141.

Chang D., Jones N.A., Li D., Ouyang M., Ragade R.K. 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. pp. 278–283.

Chrysos G. Intel Xeon Phi Coprocessor (Codename Knights Corner). Proceedings of the 2012 IEEE Hot Chips 24th Symposium (HCS), Cupertino, CA, USA, August 27–29, 2012. pp. 1–31. DOI: 10.1109/HOTCHIPS.2012.7476487

Dembele D., Kastner P. Fuzzy c-Means Method for Clustering Microarray Data. Bioinformatics. 2003. vol. 19, no. 8. pp. 973–980. DOI: 10.1093/bioinformatics/btg119

Dokmanic I., Parhizkar R., Ranieri J., Vetterli M. Euclidean Distance Matrices: Essential Theory, Algorithms, and Applications. IEEE Signal Processing Magazine. 2015. vol. 32, no. 6. pp. 12–30. DOI: 10.1109/MSP.2015.2398954

Engreitz J.M., Daigle B.Jr., Marshall J.J., Altman R.B. Independent Component Analysis: Mining Microarray Data for Fundamental Human Gene Expression Modules. Journal of Biomedical Informatics. 2010. vol. 43, no. 6. pp. 932–944. DOI: 0.1016/j.jbi.2010.07.001

Foote J. An Overview of Audio Information Retrieval. Multimedia Systems. 1999. vol. 7, no. 1. pp. 2–10. DOI: 10.1007/s005300050106

Hassan Q.F. Innovative Research and Applications in Next-generation High Performance computing. IGI Global, 2016. DOI: 10.4018/978-1-5225-0287-6.

Jaros M., Strakos P., Karasek T., et al. Implementation of k-Means Segmentation Algorithm on Intel Xeon Phi and GPU: Application in Medical Imaging. Advances in Engineering Software. 2017. vol. 103. pp. 21–28. DOI: 10.1016/j.advengsoft.2016.05.008

Kim S., Ouyang M. 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: 10.5176/2251-1652_ADPC12.07

Kostenetskiy P., Safonov A. SUSU Supercomputer Resources. PCT’2016, International Scientific Conference on Parallel Computational Technologies, Arkhangelsk, Russia, March 29–31, 2016. CEUR Workshop Proceedings. vol. 1576, CEUR-WS.org, 2016. pp. 561–573.

Lee S., Liao W., Agrawal A., Hardavellas N., Choudhary A.N. 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. pp. 2251–2260. DOI: 10.1109/BigData.2016.7840856

Li Q., Kecman V., Salman R. 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. pp. 208–213. DOI: 10.1109/ICMLA.2010.38

Meek C., Thiesson B., Heckerman D. The Learning-Curve Sampling Method Applied to Model-Based Clustering. Journal of Machine Learning Research. 2002. vol. 2. pp. 397–418.

Melnykov V., Chen W.C., Maitra R. MixSim: An R Package for Simulating Data to Study Performance of Clustering Algorithms. Journal of Statistical Software. 2012. vol. 51, no. 12. pp. 1–25. DOI: 10.18637/jss.v051.i12

Narayanan R., Ozisikyilmaz B., Zambreno J., Memik G., Choudhary A.N. 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. pp. 182–188. DOI: 10.1109/IISWC.2006.302743

Rechkalov T.V., Zymbler M.L. 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. pp. 413–417. DOI: 10.1109/ICAICT.2015.7338591

Sodani A. 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. pp. 1–24. DOI: 10.1109/HOTCHIPS.2015.7477467

Valenzise G., Gerosa L., Tagliasacchi M., Antonacci F., Sarti A. 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. pp. 21–26. DOI: 10.1109/AVSS.2007.4425280

Wu F., Wu Q., Tan Y., Wei L., Shao L., Gao L. A Vectorized k-Means Algorithm for Intel Many Integrated Core Architecture. Proceedings of the 10th International Symposium on Advanced Parallel Processing Technologies, APPT 2013, Stockholm, Sweden, August 27–28, 2013, Revised Selected Papers. Lecture Notes in Computer Science. Springer, 2013. vol. 8299. pp. 277–294. DOI: 10.1007/978-3-642-45293-2_21

Zou J., Chen L., Chen C.L.P. 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. pp. 291–296. DOI: 10.1109/BIBM.2013.6732505




DOI: http://dx.doi.org/10.14529/cmse180305