DOE OSTI · 1236322
Accelerating k-NN Algorithm with Hybrid MPI and OpenSHMEM
Abstract
Machine Learning algorithms are benefiting from the continuous improvement of programming models, including MPI, MapReduce and PGAS. k-Nearest Neighbors (k-NN) algorithm is a widely used machine learning algorithm, applied to supervised learning tasks such as classification. Several parallel implementations of k-NN have been proposed in the literature and practice. However, on high-performance computing systems with high-speed interconnects, it is important to further accelerate existing designs of the k-NN algorithm through taking advantage of scalable programming models. To improve the performance of k-NN on large-scale environment with InfiniBand network, this paper proposes several alternative hybrid MPI+OpenSHMEM designs and performs a systemic evaluation and analysis on typical workloads. The hybrid designs leverage the one-sided memory access to better overlap communication with computation than the existing pure MPI design, and propose better schemes for efficient buffer management. The implementation based on k-NN program from MaTEx with MVAPICH2-X (Unified MPI+PGAS Communication Runtime over InfiniBand) shows up to 9.0% time reduction for training KDD Cup 2010 workload over 512 cores, and 27.6% time reduction for small workload with balanced communication and computation. Experiments of running with varied number of cores show that our design can maintain good scalability.
Keep this discovery
Explore connections, maps & timelines
Lin, Jian, Hamidouche, Khaled, Zheng, Jie, Lu, Xiaoyi, Vishnu, Abhinav, Panda, Dhabaleswar. 2015-08-05. Accelerating k-NN Algorithm with Hybrid MPI and OpenSHMEM. https://doi.org/10.1007/978-3-319-26428-8. https://searchnasa.com/record/osti%3A1236322/accelerating-k-nn-algorithm-with-hybrid-mpi-and-openshmem
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.