A novel approach to accelerate calibration process of a k-nearest neighbours classifier using GPU

作者：Singh Amreek^*; Deep Kusum; Grover Pallavi

来源：Journal of Parallel and Distributed Computing, 2017, 104: 114-129.

DOI：10.1016/j.jpdc.2017.01.003

• NVIDIA CUDA
• GPU
• SIMD
• ABC algorithm
• k-nearest neighbours
• Avalanche forecasting

General purpose data parallel computing with graphical processing unit (GPU) is much structured today with NVIDIA (R) CUDA and other parallel programming frameworks. Exploiting the CUDA programming framework, the present work proposes a novel methodology formulated around the GPU hardware architecture and memory hierarchy to accelerate the calibration process of a classification model named eNN10. Primarily developed for avalanche forecasting, eNN10 is based on brute force k-nearest neighbours (k-NN) approach and employs snow-meteorological variables to search for past days with similar conditions. The events associated with past similar days are then analysed to generate forecast. The model is required to be calibrated regularly to ensure higher degree of forecast accuracy in terms of Heidke skill score (HSS). The calibration of eNN10 is carried out by Artificial Bee Colony (ABC) algorithm, a swarm intelligence driven population based metaheuristic algorithm, and it requires thousands of HSS evaluations during the complete calibration process. A MATLAB sequential code for calibration runs for over 400 minutes and the proposed methodology delivered about 10 x acceleration in calibration process. The methodology combines primitives of parallel implementations of brute force k-NN algorithm with that of population based metaheuristic algorithms and is scalable to deal with other similar real-world problems. The major objective of this paper is to highlight the methodology and associated future research areas.

• 出版日期2017-6