Design Trade-offs in Configurable FPGA Architectures
for K-Means Clustering

Alexandru AMARICAI
University Politehnica Timisoara,
2 Vasile Parvan Blvd, Timisoara, Romania.
alexandru.amaricai@cs.upt.ro

ABSTRACT: K-Means clustering is a popular technique for data partitioning, frequently used in data mining. The simple control flow, and high degree of parallelism, makes it a good candidate for FPGA acceleration. We propose a highly configurable architecture, based on Euclidean distance computation. It can be tuned by the following parameters: number of dimensions, dimension width, dimension based parallelism degree, number of centroids and centroid based parallelism degree. We study their impact on different K-Means components, such as the distance computation, distance comparison, accumulation, division, or the memory modules within the accelerator. Furthermore, for the aforementioned parameters we investigate the performance/cost trade-offs of the proposed K-Means accelerator implementation.

KEYWORDS: K-Means clustering, FPGA, parallelization.

>>FULL TEXT: PDF

CITE THIS PAPER AS:
Alexandru AMARICAI, Design Trade-offs in Configurable FPGA Architectures for K-Means Clustering, Studies in Informatics and Control, ISSN 1220-1766, vol. 26(1), pp. 43-48, 2017. https://doi.org/10.24846/v26i1y201705

REFERENCES

Choi, Y. M., & So, H. K., (2014) Map reduce processing of K-Means algorithm with FPGA based computer cluster, Proceedings 25^th International Conference on Application-Specific Systems, Architectures and Processors (ASAP) (pp. 9-16).

Elkan C. (2003) Using the triangle inequality to accelerate the K-Means, Proceedings 20^th International Conference on Machine Learning (ICML) (pp. 362-365).
Hussain, H. M., Benkrid, K., Seker, K. H. & A. T. Erdogan (2011), FPGA implementation of K-Means algorithm for bioinformatics application: An accelerated approach to clustering microarray data, Proceedings 2011 NASA/ESA Conference on Adaptive Hardware and Systems (AHS) (pp. 248-255).
Hussain, H. M., Benkrid, K., Erdogan, A. T. & Seker, H. (2011) Highly parameterized K-Means Clustering on FPGA: Comparative results with GPPs and GPUs, Proceedings 2011 NASA/ESA Conference on Adaptive Hardware and Systems (AHS) (pp. 248-255).
Kutty, J. S. S., Boussaid, F., & Amira, A. (2013) A high speed configurable FPGA architecture for K-Means clustering, (2013) 2013 IEEE International Symposium on Circuits and Systems (ISCAS) (pp. 1801-1804).
Lin, Z., Lo, C. & Chow, P., (2012) Application K-means implementation on FPGA for high-dimensional data using triangle, Proceedings 22^nd International Conference on Field Programmable Logic and Applications (pp. 437-442).
Luca, R. (2016) Clustering-based Human Locomotion Parameters for Motion Type Classification Studies in Informatics and Control, 25 (3), 353-362.
Wang, W., & Lesser, M., (2007) K-means clustering for multispectral images using floating-point divide, Proceedings 15^th Annual IEEE Symp. On Field Programmable Custom Computing Machines (FCCM) (pp. 151-162).
Winterstein, F., Bayliss S. & Constantinides, G. (2013) High-level synthesis of dynamic data structures: A case study using Vivado HLS Proceedings 2013 International Conference on Field Programmable Technology (FPT) (pp. 362-365).
Winterstein, F., Bayliss S. & Constantinides, G. (2013) FPGA based K-Means clustering using tree based data structures, Proceedings 23rd International Conference on Field Programmable Logic and Applications (pp. 1-6).