U.S. Department of Energy

Pacific Northwest National Laboratory

Accelerating k-NN Algorithm with Hybrid MPI and OpenSHMEM

Publish Date: 
Tuesday, September 15, 2015
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.
Lin J, K Hamidouche, J Zheng, X Lu, A Vishnu, and D Panda. 2015. "Accelerating k-NN Algorithm with Hybrid MPI and OpenSHMEM." In OpenSHMEM 2015: Second Workshop on OpenSHMEM and Related Technologies, August 4-6, 2015, Annapolis, Maryland, ed. G Venkata, et al, pp. 164-177. Springer, Berlin, Germany. doi:10.1007/978-3-319-26428-8
| Pacific Northwest National Laboratory