A novel multiprocessor architecture for k-means clustering algorithm based on network-on-chip

Abstract

The k-means clustering is one of the widely used algorithms in Data Mining and Machine Learning domains due to the simplicity, efficiency and scalability involved. The algorithm allocates N data-points or samples to k-clusters employing the minimum distances from respective cluster centroids. Distance calculation is intrinsically a computationally intensive task which is usually accelerated by using specific hardware platforms like Field Programmable Gate Arrays (FPGAs) and Graphic Processing Unit (GPUs) etc. Hardware implementations absolve k-means from these exhaustive computations by using the inherent parallelism of the k-means clustering technique. In this paper we propose a Multi-Processor based sequentially unfolded architecture for k-means clustering using N-tiles in a collaborative working environment. The tiles work independently in parallel and largely interchange data at the end of iteration. In proposed framework the exchange of data between titles is carried out using a Network-on-Chip (NoC) inter-connect to elevate communication bottleneck caused by concurrent working of tiles. The modularity of the proposed model permits scalability with respect to the number of working tiles. The performance evaluation of proposed architecture is done using Speed, Area and average Throughput.

Keywords Computer architecture, Clustering algorithms, Hardware, Field programmable gate arrays, Parallel processing