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

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {7},
     number = {3},
     year = {2018},
     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
PB  - mathdoc
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
%I mathdoc
%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/