research-article

An FPGA-Based Hardware Accelerator for K-Nearest Neighbor Classification for Machine Learning on Mobile Devices

Authors:

HEART '18: Proceedings of the 9th International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies

Article No.: 16, Pages 1 - 7

https://doi.org/10.1145/3241793.3241810

Published: 20 June 2018 Publication History

Get Access

Abstract

Machine learning has become one of the cornerstones of information technology. Many machine learning algorithms have found their way into mobile devices, which have stringent requirements. Also, machine learning algorithms, such as classification and clustering, are becoming complex, requiring high processing power, thus affecting the speedup. In this paper, we introduce unique, novel, and efficient hardware architecture to accelerate the K-nearest neighbor classifier on mobile devices, considering constraints associated with these devices. We evaluate the efficiency of our hardware architecture, in terms of speedup, space, and accuracy. Our design is generic, parameterized, and scalable. Our hardware design achieves 127 times speedup compared to its software counterpart, and can also achieve 100% classification accuracy.

References

[1]

Kotsiantis, S., "Supervised Machine Learning: A Review of Classification Techniques", in Proc. of Conf. on Emerging Artificial Intelligence Applications in Computer Engineering: Real Word AI Systems with Applications in eHealth, HCI, Information Retrieval and Pervasive Technologies, pp:3--24, July 2007.

Digital Library

Google Scholar

[2]

Larose, D., "Discovering Knowledge in Data: An Introduction to Data Mining", John Wiley & Sons, Inc. 2005.

Digital Library

Google Scholar

[3]

Amanpreet, S., et al, "A Review of Supervised Machine Learning Algorithms", in Proc. of Int. Conf. on Computing for Sustainable Global Development, Mar. 2016.

Google Scholar

[4]

Pu Y., J. et al, "An efficient K-NN algorithm implemented on FPGA based heterogeneous computing system using OpenCL", in Proc. of IEEE 23rd Int. Symp. on Field-Programmable Custom Computing Machines, May 2015.

Digital Library

Google Scholar

[5]

Hussain H., et al, "An adaptive FPGA implementation of multi-core K-nearest neighbor ensemble classifier using dynamic partial reconfiguration", in Proc. of 22nd Int. Conf. on Field Programmable Logic and Applications, Aug. 2012.

Google Scholar

[6]

Satyanarayana N., et al, "Survey of Classification Techniques in Data Mining", Int. Journal of Innovative Science, Engineering & Technology, vol. 1, no. 9, Nov. 2014.

Google Scholar

[7]

Stamoulis I. and E. Manolakos, "Parallel Architectures for the K-NN Classifier -- Design of Soft IP Cores and FPGA Implementations", ACM Transactions on Embedded Computing Systems Journal, vol. 13, no. 2, Sep. 2013.

Digital Library

Google Scholar

[8]

https://www.coursera.org/learn/machine-learning#ratings

Google Scholar

[9]

Perera, D.G. and K.F. Li, "FPGA-Based Reconfigurable Hardware for Compute Intensive Data Mining Applications," in Proc. of IEEE Int. Conf. on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC'11), pp. 100--108, Oct. 2011.

Digital Library

Google Scholar

[10]

https://archive.ics.uci.edu/ml/datasets/Iris

Google Scholar

[11]

https://archive.ics.uci.edu/ml/datasets/Statlog+(Heart)

Google Scholar

[12]

https://archive.ics.uci.edu/ml/datasets/User+Knowledge+Modeling

Google Scholar

[13]

Li Z., et al, "K-Nearest Neighbor Algorithm Implementation on FPGA Using High Level Synthesis", in Proc. of 13th IEEE Int. Conf. on Solid-State and Integrated Circuit Technology, pp. 600--602, Oct. 2016.

Google Scholar

Cited By

View all

Gorgin SNisar MLee J(2025)Efficient hardware accelerators for k-nearest neighbors classification using most significant digit first arithmeticThe Journal of Supercomputing10.1007/s11227-024-06466-281:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06466-2
Behera SPrathuri J(2024)FPGA-Based Acceleration of K-Nearest Neighbor Algorithm on Fully Homomorphic Encrypted DataCryptography10.3390/cryptography80100088:1(8)Online publication date: 27-Feb-2024
https://doi.org/10.3390/cryptography8010008
Mohsin MShahrouzi SPerera D(2024)Composing Efficient Computational Models for Real-Time Processing on Next-Generation Edge-Computing PlatformsIEEE Access10.1109/ACCESS.2024.336565212(24905-24932)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3365652
Show More Cited By

Recommendations

Reverse Nearest Neighbour by Region on Mobile Devices
AINA '14: Proceedings of the 2014 IEEE 28th International Conference on Advanced Information Networking and Applications

Reverse Nearest Neighbour queries is known for the heavyweight algorithm that makes it difficult to be implemented in mobile devices due to high computations needed to verify the objects. Since the rapid development of mobile devices' hardware and also ...
Modified nearest neighbour classifier for hyperspectral data classification

A modified k-nearest neighbour k-NN classifier is proposed for supervised remote sensing classification of hyperspectral data. To compare its performance in terms of classification accuracy and computational cost, k-NN and a back-propagation neural ...
A new general nearest neighbor classification based on the mutual neighborhood information

The nearest neighbor (NN) rule is effective for many applications in pattern classification, such as the famous k-nearest neighbor (kNN) classifier. However, NN-based classifiers perform a one-sided classification by finding the nearest neighbors simply ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

HEART '18: Proceedings of the 9th International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies

June 2018

125 pages

ISBN:9781450365420

DOI:10.1145/3241793

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

HEART 2018

HEART 2018: The 9th International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies

June 20 - 22, 2018

ON, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 22 of 50 submissions, 44%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
338
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)9

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gorgin SNisar MLee J(2025)Efficient hardware accelerators for k-nearest neighbors classification using most significant digit first arithmeticThe Journal of Supercomputing10.1007/s11227-024-06466-281:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06466-2
Behera SPrathuri J(2024)FPGA-Based Acceleration of K-Nearest Neighbor Algorithm on Fully Homomorphic Encrypted DataCryptography10.3390/cryptography80100088:1(8)Online publication date: 27-Feb-2024
https://doi.org/10.3390/cryptography8010008
Mohsin MShahrouzi SPerera D(2024)Composing Efficient Computational Models for Real-Time Processing on Next-Generation Edge-Computing PlatformsIEEE Access10.1109/ACCESS.2024.336565212(24905-24932)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3365652
El Bouazzaoui AHadjoudja AMouhib OCherkaoui N(2024)FPGA-based ML adaptive accelerator: A partial reconfiguration approach for optimized ML accelerator utilizationArray10.1016/j.array.2024.10033721(100337)Online publication date: Mar-2024
https://doi.org/10.1016/j.array.2024.100337
Samanta AHatai IMal A(2024)A Survey on Hardware Accelerator Design of Deep Learning for Edge DevicesWireless Personal Communications10.1007/s11277-024-11443-2Online publication date: 19-Jul-2024
https://doi.org/10.1007/s11277-024-11443-2
Chunduri RPerera D(2023)Neuromorphic Sentiment Analysis Using Spiking Neural NetworksSensors10.3390/s2318770123:18(7701)Online publication date: 6-Sep-2023
https://doi.org/10.3390/s23187701
K RAN DS LSP MM A(2023)Computational Framework for Prediction of Cardiac Disorders by analyzing ECG signals Using Machine Learning TechniqueInternational Journal for Multiscale Computational Engineering10.1615/IntJMultCompEng.2023050106Online publication date: 2023
https://doi.org/10.1615/IntJMultCompEng.2023050106
Ramadurgam SPerera D(2023)A Systolic Array Architecture for SVM Classifier for Machine Learning on Embedded Devices2023 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS46773.2023.10182159(1-5)Online publication date: 21-May-2023
https://doi.org/10.1109/ISCAS46773.2023.10182159
Graf JPerera D(2023)Optimizing Density-Based Ant Colony Stream Clustering Using FPGA-Based Hardware Accelerator2023 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS46773.2023.10181665(1-5)Online publication date: 21-May-2023
https://doi.org/10.1109/ISCAS46773.2023.10181665
Yen CYeh MChen M(2023)Integrated Multi-Ported Memory Distribution for Temporal-Multiplexing Workloads on FPGAs2023 International Conference on Field Programmable Technology (ICFPT)10.1109/ICFPT59805.2023.00028(209-216)Online publication date: 12-Dec-2023
https://doi.org/10.1109/ICFPT59805.2023.00028
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Reverse Nearest Neighbour by Region on Mobile Devices

Modified nearest neighbour classifier for hyperspectral data classification

A new general nearest neighbor classification based on the mutual neighborhood information