K-means clustering on CGRA

In this paper we present a k-means clustering algorithm for the Versat architecture, a small and low power Coarse Grained Reconfigurable Array (CGRA). This algorithm targets ultra low energy devices where using a GPU or FPGA accelerator is out of the question. The Versat architecture has been enhanced with pointer support, the possibility of using the address generators for general purposes, and cumulative and conditional operations for the ALUs. The algorithm is based on two hardware datapaths for the two basic steps of the algorithm: the assignment and the update steps. The program is fully parameterizable with the number of datapoints, centroids, coordinates, and memory pointers for reading and writing the data. The execution time scales linearly with the number of datapoints, centers or dimensions. The results show that the new Versat core is 9.4x smaller than an ARM Cortex A9 core, runs the algorithm 3.8x faster and consumes 46.3x less energy.