Efficient K nearest neighbor algorithm implementations for throughput-oriented architectures

Jihyun Ryoo, Meena Arunachalam, Rahul Khanna, Mahmut T. Kandemir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Scores of emerging and domain-specific applications need the ability to acquire and augment new knowledge from offline training-sets and online user interactions. This requires an underlying computing platform that can host machine learning (ML) kernels. This in turn entails one to have efficient implementations of the frequently-used ML kernels on state-of-the-art multicores and many-cores, to act as high-performance accelerators. Motivated by this observation, this paper focuses on one such ML kernel, namely, K Nearest Neighbor (KNN), and conducts a comprehensive comparison of its behavior on two alternate accelerator-based systems: NVIDIA GPU and Intel Xeon Phi (both KNC and KNL architectures). More explicitly, we discuss and experimentally evaluate various optimizations that can be applied to both GPU and Xeon Phi, as well as optimizations that are specific to either GPU or Xeon Phi. Furthermore, we implement different versions of KNN on these candidate accelerators and collect experimental data using various inputs. Our experimental evaluations suggest that, by using both general purpose and accelerator specific optimizations, one can achieve average speedups ranging 0.49x-3.48x (training) and 1.43x-9.41x (classification) on Xeon Phi series, compared to 0.05x-0.60x (training), 1.61x-6.32x (classification) achieved by the GPU version, both over the standard host-only system.

Original languageEnglish (US)
Title of host publication2018 19th International Symposium on Quality Electronic Design, ISQED 2018
PublisherIEEE Computer Society
Pages144-150
Number of pages7
ISBN (Electronic)9781538612149
DOIs
StatePublished - May 9 2018
Event19th International Symposium on Quality Electronic Design, ISQED 2018 - Santa Clara, United States
Duration: Mar 13 2018Mar 14 2018

Publication series

NameProceedings - International Symposium on Quality Electronic Design, ISQED
Volume2018-March
ISSN (Print)1948-3287
ISSN (Electronic)1948-3295

Other

Other19th International Symposium on Quality Electronic Design, ISQED 2018
Country/TerritoryUnited States
CitySanta Clara
Period3/13/183/14/18

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Efficient K nearest neighbor algorithm implementations for throughput-oriented architectures'. Together they form a unique fingerprint.

Cite this