Article

Algorithmic transformations in the implementation of K- means clustering on reconfigurable hardware

Authors:

Mike Estlick,

Miriam Leeser,

James Theiler,

John J. SzymanskiAuthors Info & Claims

FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays

Pages 103 - 110

https://doi.org/10.1145/360276.360311

Published: 01 February 2001 Publication History

Get Access

Abstract

In mapping the k-means algorithm to FPGA hardware, we examined algorithm level transforms that dramatically increased the achievable parallelism. We apply the k-means algorithm to multi-spectral and hyper-spectral images, which have tens to hundreds of channels per pixel of data. K-means is an iterative algorithm that assigns assigns to each pixel a label indicating which of K clusters the pixel belongs to.

K-means is a common solution to the segmentation of multi-dimensional data. The standard software implementation of k-means uses floating-point arithmetic and Euclidean distances. Floating point arithmetic and the multiplication-heavy Euclidean distance calculation are fine on a general purpose processor, but they have large area and speed penalties when implemented on an FPGA. In order to get the best performance of k-means on an FPGA, the algorithm needs to be transformed to eliminate these operations. We examined the effects of using two other distance measures, Manhattan and Max, that do not require multipliers. We also examined the effects of using fixed precision and truncated bit widths in the algorithm.

It is important to explore algorithmic level transforms and tradeoffs when mapping an algorithm to reconfigurable hardware. A direct translation of the standard software implementation of k-means would result in a very inefficient use of FPGA hardware resources. Analysis of the algorithm and data is necessary for a more efficient implementation. Our resulting implementation exhibits approximately a 200 times speed up over a software implementation.

References

[1]

P. Banerjee et al. A MATLAB compiler for distributed, heterogeneous, reconfigurable computing systems. In IEEE Symposium on FPGAs for Custom Computing Machines, 2000.

Digital Library

Google Scholar

[2]

V. Castelli and T. M. Cover. On the exponential value of labeled samples. Pattern Recognition Lett., 16:105-111, 1995.

Digital Library

Google Scholar

[3]

B. Draper et al. Compiling and optimizing image processing algorithms for FPGAs. In Workshop on Computer Architecture for Machine Performance, 2000.

Digital Library

Google Scholar

[4]

C. Funk, J. Theiler, D. A. Roberts, and C. C. Borel. Clustering to improve matched-filter detection of weak gas plumes in hyperspectral imagery. Technical Report LA-UR 00-3673, Los Alamos National Laboratory, 2000.

Google Scholar

[5]

M. B. Gokhale, J. M. Stone, J. Arnold, and M. Kalinowski. Streams-oriented FPGA computing in the Streams-C high level language. In IEEE Symposium on FPGAs for Custom Computing Machines, 2000.

Digital Library

Google Scholar

[6]

P.-F. Hsieh and D. Landgrebe. Statistics enhancement in hyperspectral data analysis using spectral-spatial labeling, the EM algorithm, and the leave-one-out covariance estimator. Proc. SPIE, 3438:183-190, 1999.

Google Scholar

[7]

P. M. Kelly and J. M. White. Preprocessing remotely-sensed data for effcient analysis and classification. In U. M. Fayyad and R. Uthurusamy, editors, Artificial Intelligence 1993:Knowledge-Based Systems in Aerospace and Industry, volume 1963, pages 24-30, 1993.

Google Scholar

[8]

NASA, 1999. http://makalu.jpl.nasa.gov/avaris.html.

Google Scholar

[9]

R. A. Schowengerdt. Techniques for Image Processing and Classification in Remote Sensing. Academic Press, Orlando, 1983.

Google Scholar

[10]

J. Theiler, M. Leeser, M. Estlick, and J. J. Szymanski. Design issues for hardware implementation of an algorithm for segmenting hyperspectral imagery. In M. R. Descour and S. S. Shen, editors, Imaging Spectrometry VI, volume 4132, 2000.

Crossref

Google Scholar

Cited By

View all

Zeng RQin YSong Y(2024)A non-iterative capsule network with interdependent agreement routingExpert Systems with Applications10.1016/j.eswa.2023.122284238(122284)Online publication date: Mar-2024
https://doi.org/10.1016/j.eswa.2023.122284
Chen JXi ZLv ZLiu XWu M(2023)Coal Maceral Groups Segmentation Using Multi-scale Residual NetworkProceedings of 2023 Chinese Intelligent Automation Conference10.1007/978-981-99-6187-0_60(610-617)Online publication date: 23-Sep-2023
https://doi.org/10.1007/978-981-99-6187-0_60
Alsayat A(2022)Customer decision-making analysis based on big social data using machine learning: a case study of hotels in MeccaNeural Computing and Applications10.1007/s00521-022-07992-x35:6(4701-4722)Online publication date: 28-Oct-2022
https://doi.org/10.1007/s00521-022-07992-x
Show More Cited By

Index Terms

Algorithmic transformations in the implementation of K- means clustering on reconfigurable hardware
1. Hardware

Recommendations

High speed c-means clustering in reconfigurable hardware

A novel hardware architecture for c-means clustering is presented in this paper. Our architecture is fully pipelined for both the partitioning and centroid computation operations so that multiple training vectors can be concurrently processed. A simple ...
Hyperspectral Images Clustering on Reconfigurable Hardware Using the K-Means Algorithm
SBCCI '03: Proceedings of the 16th symposium on Integrated circuits and systems design

Unsupervised clustering is a powerful technique for understanding multispectral and hyperspectral images, being k-means one of the most used iterative approaches. It is a simple though computationally expensive algorithm, particularly for clustering ...
Fast Fuzzy C-Means Clustering Based on Low-Cost High-Performance VLSI Architecture in Reconfigurable Hardware
CSE '10: Proceedings of the 2010 13th IEEE International Conference on Computational Science and Engineering

This paper presents a novel low-cost and high-performance VLSI architecture for fuzzy c-means clustering. In the architecture, the operations at both the centroid and data levels are pipelined to attain high computational speed while consuming low ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays

February 2001

200 pages

ISBN:1581133413

DOI:10.1145/360276

Chairman:
Scott Hauck
Univ. of Washington, Seattle
,
Editors:
Martine Schlag
Univ. of California, Santa Cruz
,
Russell Tessier
Univ. of Massachusetts, Amherst

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: 01 February 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

FPGA01

Sponsor:

SIGDA

FPGA01: ACM/SIGDA International Symposium on Field Programmable Gate Arrays

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

100
Total Citations
View Citations
1,240
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zeng RQin YSong Y(2024)A non-iterative capsule network with interdependent agreement routingExpert Systems with Applications10.1016/j.eswa.2023.122284238(122284)Online publication date: Mar-2024
https://doi.org/10.1016/j.eswa.2023.122284
Chen JXi ZLv ZLiu XWu M(2023)Coal Maceral Groups Segmentation Using Multi-scale Residual NetworkProceedings of 2023 Chinese Intelligent Automation Conference10.1007/978-981-99-6187-0_60(610-617)Online publication date: 23-Sep-2023
https://doi.org/10.1007/978-981-99-6187-0_60
Alsayat A(2022)Customer decision-making analysis based on big social data using machine learning: a case study of hotels in MeccaNeural Computing and Applications10.1007/s00521-022-07992-x35:6(4701-4722)Online publication date: 28-Oct-2022
https://doi.org/10.1007/s00521-022-07992-x
Arias-Garcia JMafra AGade LCoelho FCastro CTorres LBraga A(2021)Enhancing Performance of Gabriel Graph-Based Classifiers by a Hardware Co-Processor for Embedded System ApplicationsIEEE Transactions on Industrial Informatics10.1109/TII.2020.298732917:2(1186-1196)Online publication date: Feb-2021
https://doi.org/10.1109/TII.2020.2987329
He ZKorolija DAlonso G(2021)EasyNet: 100 Gbps Network for HLS2021 31st International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL53798.2021.00040(197-203)Online publication date: Aug-2021
https://doi.org/10.1109/FPL53798.2021.00040
Gupta N(2021)Introduction to hardware accelerator systems for artificial intelligence and machine learningHardware Accelerator Systems for Artificial Intelligence and Machine Learning10.1016/bs.adcom.2020.07.001(1-21)Online publication date: 2021
https://doi.org/10.1016/bs.adcom.2020.07.001
Choudhury RAhamed SGuha P(2021)Efficient Hardware Implementation of Decision Tree Training AcceleratorSN Computer Science10.1007/s42979-021-00748-92:5Online publication date: 26-Jun-2021
https://doi.org/10.1007/s42979-021-00748-9
He ZWang ZAlonso GNeuendorffer SShannon L(2020)BiS-KM: Enabling Any-Precision K-Means on FPGAsProceedings of the 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3373087.3375316(233-243)Online publication date: 23-Feb-2020
https://dl.acm.org/doi/10.1145/3373087.3375316
Choudhury RAhamed SGuha P(2020)Efficient Hardware Implementation of Decision Tree Training Accelerator2020 IEEE International Symposium on Smart Electronic Systems (iSES) (Formerly iNiS)10.1109/iSES50453.2020.00055(212-215)Online publication date: Dec-2020
https://doi.org/10.1109/iSES50453.2020.00055
Andrade Maciel LAlcantara Souza MCota de Freitas H(2020)Reconfigurable FPGA-Based K-Means/K-Modes Architecture for Network Intrusion DetectionIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2019.293982667:8(1459-1463)Online publication date: Aug-2020
https://doi.org/10.1109/TCSII.2019.2939826
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

Index Terms

Recommendations

High speed c-means clustering in reconfigurable hardware

Hyperspectral Images Clustering on Reconfigurable Hardware Using the K-Means Algorithm

Fast Fuzzy C-Means Clustering Based on Low-Cost High-Performance VLSI Architecture in Reconfigurable Hardware